Home Issues About JGAA Instructions for Authors
 
 
Special issue on Selected papers from the Twenty-sixth International Symposium on Graph Drawing and Network Visualization, GD 2018
DOI: 10.7155/jgaa.00502
A New Framework for Hierarchical Drawings
Giacomo Ortali and Ioannis G. Tollis
Vol. 23, no. 3, pp. 553-578, 2019. Regular paper.
Abstract We present a new approach to visualize directed graphs and their hierarchies that departs from the classical four-phase framework of Sugiyama and computes readable hierarchical visualizations that focus on the reachability information of a directed acyclic graph. Additionally, our approach has the feature that a few transitive edges are not drawn in the drawing, thus reducing the visual complexity of the resulting drawing. Furthermore, the problems involved in our framework require only polynomial time. The channel decomposition is a partition of the vertex set of the graph into channels, where a channel is a relaxed path. Our framework offers a suite of solutions depending upon the requirements, and it consists of only two steps: (a) the cycle removal step (if the directed graph contains cycles) and (b) the channel decomposition and hierarchical drawing step. Our framework does not introduce any dummy vertices and it keeps the vertices of a path/channel vertically aligned. The time complexity of the main drawing algorithms of our framework is $O(km)$, where $k$ is the number of paths/channels, typically much smaller than $n$ (the number of vertices).
Submitted: November 2018.
Reviewed: February 2019.
Revised: June 2019.
Reviewed: July 2019.
Revised: July 2019.
Accepted: July 2019.
Final: July 2019.
Published: September 2019.
Communicated by Therese Biedl and Andreas Kerren
article (PDF)
BibTeX