Column-Based Graph Layouts

Betz, Gregor and Doll, Christoph and Gemsa, Andreas and Rutter, Ignaz and Wagner, Dorothea (2013) Column-Based Graph Layouts. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 236-247 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_21).

Full text not available from this repository.

Abstract

We consider orthogonal upward drawings of directed acyclic graphs (DAGs) 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 [10]. However, to avoid drawbacks of the Sugiyama framework we use the layer-free upward crossing minimization algorithm suggested by Chimani et al. and integrate it into the topology-shape-metric (TSM) framework introduced by Tamassia [11]. This in combination with an algorithm by Biedl and Kant [2] 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 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 justify our approach by an experimental evaluation based on real-world examples.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_21
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.800 Topology-shape-metrics
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.840 Upward
ID Code:1313

Repository Staff Only: item control page

References

Betz, G.: Theorie dialektischer Strukturen. Klostermann (2010)

Biedl, T., Kant, G.: A Better Heuristic for Orthogonal Graph Drawings. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 24–35. Springer, Heidelberg (1994)

Chimani, M., Gutwenger, C., Mutzel, P., Wong, H.M.: Layer-free upward crossing minimization. Journal of Experimental Algorithmics 15 (2010)

Chimani, M., Gutwenger, C., Mutzel, P., Wong, H.M.: Upward planarization layout. Journal of Graph Algorithms and Applications 15(1), 127–155 (2011)

Di Battista, G., Didimo, W., Patrignani, M., Pizzonia, M.: Orthogonal and Quasi-upward Drawings with Vertices of Prescribed Size. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 297–310. Springer, Heidelberg (1999)

Doll, C.: Automatic Layout Generation for Argument Maps. Master’s thesis, Karlsruhe Institute of Technology (February 2012)

Eades, P., Tamassia, R.: Algorithms for drawing graphs: An annotated bibliography. Tech. rep., Brown University, Providence, RI, USA (1988)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing 31, 601–625 (2002)

Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: IEEE Pacific Visualization Symposium, PacificVIS 2008, pp. 41–46 (2008)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics 11(2), 109–125 (1981)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing 16, 421–444 (1987)