Adventures in Abstraction: Reachability in Hierarchical Drawings
This work addresses the challenge of clearly displaying and efficiently storing transitivity information in large graphs and databases, representing an incremental improvement over existing methods.
The paper tackles the problem of visualizing reachability in directed graphs by customizing path and channel decomposition algorithms to reduce visual complexity and memory usage for storing transitivity information, achieving almost linear time complexity of O(kn+m).
We present algorithms and experiments for the visualization of directed graphs that focus on displaying their reachability information. Our algorithms are based on the concepts of the path and channel decomposition as proposed in the framework presented in GD 2018 (pp. 579-592) and focus on showing the existence of paths clearly. In this paper we customize these concepts and present experimental results that clearly show the interplay between bends, crossings and clarity. Additionally, our algorithms have direct applications to the important problem of showing and storing transitivity information of very large graphs and databases. Only a subset of the edges is drawn, thus reducing the visual complexity of the resulting drawing, and the memory requirements for storing the transitivity information. Our algorithms require almost linear time, $O(kn+m)$, where $k$ is the number of paths/channels, $n$ and $m$ is the number of vertices and edges, respectively. They produce progressively more abstract drawings of the input graph. No dummy vertices are introduced and the vertices of each path/channel are vertically aligned.