A New Framework for Hierarchical Drawings

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).