Geodesic
Column-Based Graph Layouts
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 5, pp. 677-708.

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

We consider orthogonal upward drawings of directed acyclic graphs with nodes of uniform width but node-specific height. One way to draw such graphs is to use a layering technique as provided by the Sugiyama framework [K. Sugiyama, S. Tagawa, M. Toda. IEEE Transactions on Systems, Man and Cybernetics, 1981.]. To overcome one of the drawbacks of the Sugiyama Framework, namely, unnecessary edge crossings caused by an unfortunate layer assignment of the nodes, Chimani et al. integrated their layer-free upward crossing minimization algorithm [M. Chimani, C. Gutwenger, P. Mutzel, and H.-M. Wong, Journal of Experimental Algorithmics, 2010.] into the Sugiyama framework [M. Chimani, C. Gutwenger, P. Mutzel, and H.-M. Wong, Journal of Graph Algorithms and Applications, 2011]. However, one drawback of the Sugiyama framework still remains. If the heights of the nodes are non-uniform, the result of the approach can be a non-compact layout. In contrast, we avoid both of these drawbacks by integrating layer-free upward crossing minimization into the topology-shape-metrics (TSM) framework introduced by Tamassia [R. Tamassia, SIAM Journal on Computing, 1987]. Our approach, in combination with an algorithm by Biedl and Kant [T. Biedl and G. Kant, Computational Geometry, 1998.] lets us generate column-based layouts, i.e., layouts where the plane is divided into uniform-width columns and every node is assigned to a column. We study the complexity of the individual steps of the layout process systematically and propose efficient algorithms with provable guarantees. We show that our column-based approach allows to generate visually appealing, compact layouts with few edge crossing and at most four bends per edge. Furthermore, the resulting layouts exhibit a high degree of symmetry and implicitly support edge bundling. We evaluate our approach by applying it to several real-world examples.
DOI : 10.7155/jgaa.00341
Keywords: topology-shape-metric framework, orthogonal edges, column-based graph layouts, compact layouts 
@article{JGAA_2014_18_5_a1,
     author = {Gregor Betz and Andreas Gemsa and Christof Mathies and Ignaz Rutter and Dorothea Wagner},
     title = {Column-Based {Graph} {Layouts}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {677--708},
     publisher = {mathdoc},
     volume = {18},
     number = {5},
     year = {2014},
     doi = {10.7155/jgaa.00341},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00341/}
}
TY  - JOUR
AU  - Gregor Betz
AU  - Andreas Gemsa
AU  - Christof Mathies
AU  - Ignaz Rutter
AU  - Dorothea Wagner
TI  - Column-Based Graph Layouts
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 677
EP  - 708
VL  - 18
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00341/
DO  - 10.7155/jgaa.00341
LA  - en
ID  - JGAA_2014_18_5_a1
ER  - 
%0 Journal Article
%A Gregor Betz
%A Andreas Gemsa
%A Christof Mathies
%A Ignaz Rutter
%A Dorothea Wagner
%T Column-Based Graph Layouts
%J Journal of Graph Algorithms and Applications
%D 2014
%P 677-708
%V 18
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00341/
%R 10.7155/jgaa.00341
%G en
%F JGAA_2014_18_5_a1
Gregor Betz; Andreas Gemsa; Christof Mathies; Ignaz Rutter; Dorothea Wagner. Column-Based Graph Layouts. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 5, pp. 677-708. doi : 10.7155/jgaa.00341. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00341/

Cité par Sources :