Column-Based Graph Layouts

Abstract

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.