Geodesic
New Approximation to the One-sided Radial Crossing Minimization
Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 179-196.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In this paper, we study a crossing minimization problem in a radial drawing of a graph. Radial drawings have strong application in social network visualization, for example, displaying centrality indices of actors []. The main problem of this paper is called the one-sided radial crossing minimization between two concentric circles, named orbits, where the positions of vertices in the outer orbit are fixed. The main task of the problem is to find the vertex ordering of the free orbit and edge routing between two orbits in order to minimize the number of edge crossings. The problem is known to be NP-hard [], and the first polynomial time 15-approximation algorithm was presented in []. In this paper, we present a new 3α-approximation algorithm for the case when the free orbit has no leaf vertex, where α represents the approximation ratio of the one-sided crossing minimization problem in a horizontal drawing. Using the best known result of α = 1.4664 [], our new algorithm can achieve 4.3992-approximation. 
@article{JGAA_2009_13_2_a5,
     author = {Seok-Hee Hong and Hiroshi Nagamochi},
     title = {New {Approximation} to the {One-sided} {Radial} {Crossing} {Minimization}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {179--196},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2009},
     doi = {10.7155/jgaa.00182},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00182/}
}
TY  - JOUR
AU  - Seok-Hee Hong
AU  - Hiroshi Nagamochi
TI  - New Approximation to the One-sided Radial Crossing Minimization
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 179
EP  - 196
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00182/
DO  - 10.7155/jgaa.00182
LA  - en
ID  - JGAA_2009_13_2_a5
ER  - 
%0 Journal Article
%A Seok-Hee Hong
%A Hiroshi Nagamochi
%T New Approximation to the One-sided Radial Crossing Minimization
%J Journal of Graph Algorithms and Applications
%D 2009
%P 179-196
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00182/
%R 10.7155/jgaa.00182
%G en
%F JGAA_2009_13_2_a5
Seok-Hee Hong; Hiroshi Nagamochi. New Approximation to the One-sided Radial Crossing Minimization. Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 179-196. doi : 10.7155/jgaa.00182. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00182/

Cité par Sources :