Geodesic
Global k-Level Crossing Reduction
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010) , Tome 15 (2011) no. 5, pp. 631-659.

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

Directed graphs are commonly drawn by a four phase framework introduced by Sugiyama et al.in 1981. The vertices are placed on parallel horizontal levels. The edge routing between consecutive levels is computed by solving one-sided 2-level crossing minimization problems, which are repeated in up and down sweeps over all levels. Crossing minimization problems are generally NP-hard. We introduce a global crossing reduction, which at any particular time considers all crossings between all levels. Our approach is based on the sifting technique. It yields an improvement of 5 - 10% in the number of crossings over the level-by-level one-sided 2-level crossing reduction heuristics. In addition, it avoids type 2 conflicts which are crossings between edges whose endpoints are dummy vertices. This helps straightening long edges spanning many levels. Finally, the global crossing reduction approach can directly be extended to cyclic, radial, and clustered level graphs achieving similar improvements. The running time is quadratic in the size of the input graph, whereas the common level-by-level approaches are faster but operate on larger graphs with many dummy vertices for long edges. 
@article{JGAA_2011_15_5_a3,
     author = {Christian Bachmaier and Franz Brandenburg and Wolfgang Brunner and Ferdinand H\"ubner},
     title = {Global {k-Level} {Crossing} {Reduction}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {631--659},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2011},
     doi = {10.7155/jgaa.00242},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00242/}
}
TY  - JOUR
AU  - Christian Bachmaier
AU  - Franz Brandenburg
AU  - Wolfgang Brunner
AU  - Ferdinand Hübner
TI  - Global k-Level Crossing Reduction
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 631
EP  - 659
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00242/
DO  - 10.7155/jgaa.00242
LA  - en
ID  - JGAA_2011_15_5_a3
ER  - 
%0 Journal Article
%A Christian Bachmaier
%A Franz Brandenburg
%A Wolfgang Brunner
%A Ferdinand Hübner
%T Global k-Level Crossing Reduction
%J Journal of Graph Algorithms and Applications
%D 2011
%P 631-659
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00242/
%R 10.7155/jgaa.00242
%G en
%F JGAA_2011_15_5_a3
Christian Bachmaier; Franz Brandenburg; Wolfgang Brunner; Ferdinand Hübner. Global k-Level Crossing Reduction. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
					, Tome 15 (2011) no. 5, pp. 631-659. doi : 10.7155/jgaa.00242. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00242/

Cité par Sources :