
doi: 10.7155/jgaa.00341
Summary: 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. To overcome one of the drawbacks of the Sugiyama Framework, namely, unnecessary edge crossings caused by an unfortunate layer assignment of the nodes, \textit{M. Chimani} et al. integrated their layer-free upward crossing minimization algorithm [ACM J. Exp. Algorithm. 15, Spec. Iss. 1, Article No. 2.2, 27 p. (2010; Zbl 1284.05277)] into the Sugiyama framework [\textit{M. Chimani} et al., J. Graph Algorithms Appl. 15, No. 1, 127--155 (2011; Zbl 1217.05070)]. 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 \textit{R.Tamassia} [SIAM J. Comput. 16, 421--444 (1987; Zbl 0654.68090)]. Our approach, in combination with an algorithm by \textit{T. Biedl} and \textit{G. Kant} [SIAM J. Comput. 16, 421--444 (1987; Zbl 0654.68090)], 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.
directed acyclic graphs, Graph representations (geometric and intersection representations, etc.), Directed graphs (digraphs), tournaments, orthogonal upward drawings
directed acyclic graphs, Graph representations (geometric and intersection representations, etc.), Directed graphs (digraphs), tournaments, orthogonal upward drawings
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
