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 , pp. 236-247(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item