Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Column-Based Graph Layouts

  • Conference paper
Graph Drawing(GD 2012)

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 7704))

Included in the following conference series:

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 generatecolumn-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.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

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

    Google Scholar 

  2. 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)

    Chapter  Google Scholar 

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

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  5. 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)

    Chapter  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article MathSciNet  Google Scholar 

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

    Google Scholar 

  10. 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)

    Article MathSciNet  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Karlsruhe Institute of Technology (KIT), Germany

    Gregor Betz, Christoph Doll, Andreas Gemsa, Ignaz Rutter & Dorothea Wagner

Authors
  1. Gregor Betz

    You can also search for this author inPubMed Google Scholar

  2. Christoph Doll

    You can also search for this author inPubMed Google Scholar

  3. Andreas Gemsa

    You can also search for this author inPubMed Google Scholar

  4. Ignaz Rutter

    You can also search for this author inPubMed Google Scholar

  5. Dorothea Wagner

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dip. di Ingegneria Elettronica e dell’Informazione, Perugia University, Italy

    Walter Didimo

  2. Dip. Informatica e Automazione, Università degli Studi Roma Tre, Via della Vasca Navale, 79, 00146, Rome, Italy

    Maurizio Patrignani

Rights and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Betz, G., Doll, C., Gemsa, A., Rutter, I., Wagner, D. (2013). Column-Based Graph Layouts. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_21

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp