Column-Based Graph Layouts

详细信息    查看全文

• 作者：Gregor Betz (18)
  Christoph Doll (18)
  Andreas Gemsa (18)
  Ignaz Rutter (18)
  Dorothea Wagner (18)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7704
• 期：1
• 页码：248-259
• 全文大小：213KB
• 参考文献：1. Betz, G.: Theorie dialektischer Strukturen. Klostermann (2010)
  2. Biedl, T., Kant, G.: A Better Heuristic for Orthogonal Graph Drawings. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.聽855, pp. 24鈥?5. Springer, Heidelberg (1994) CrossRef
  3. Chimani, M., Gutwenger, C., Mutzel, P., Wong, H.M.: Layer-free upward crossing minimization. Journal of Experimental Algorithmics 15 (2010)
  4. Chimani, M., Gutwenger, C., Mutzel, P., Wong, H.M.: Upward planarization layout. Journal of Graph Algorithms and Applications聽15(1), 127鈥?55 (2011) CrossRef
  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鈥?10. Springer, Heidelberg (1999) CrossRef
  6. Doll, C.: Automatic Layout Generation for Argument Maps. Master鈥檚 thesis, Karlsruhe Institute of Technology (February 2012)
  7. Eades, P., Tamassia, R.: Algorithms for drawing graphs: An annotated bibliography. Tech. rep., Brown University, Providence, RI, USA (1988)
  8. Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing聽31, 601鈥?25 (2002) CrossRef
  9. Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: IEEE Pacific Visualization Symposium, PacificVIS 2008, pp. 41鈥?6 (2008)
  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鈥?25 (1981) CrossRef
  11. Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing聽16, 421鈥?44 (1987) CrossRef
  
• 作者单位：Gregor Betz (18)
  Christoph Doll (18)
  Andreas Gemsa (18)
  Ignaz Rutter (18)
  Dorothea Wagner (18)
  
  18. Karlsruhe Institute of Technology (KIT), Germany
  
• ISSN：1611-3349

文摘

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.