Topological Decomposition of Directed Graphs
Ala Abuthawabeh and Dirk Zeckzer
Vol. 21, no. 4, pp. 589-630, 2017. Regular paper.
Abstract The analysis of directed graphs is important in application areas like software engineering, bioinformatics, or project management. Distinguishing between topological structures such as cyclic and hierarchical subgraphs provides the analyst with important information. However, until now, graph drawing algorithms draw the complete directed graph either hierarchically or cyclic. Therefore, we introduced new algorithms for decomposing the input graph into cyclic subgraphs, directed acyclic subgraphs, and tree subgraphs. For all of these subgraphs, optimized layout algorithms exist. We developed and presented a new algorithm for drawing the complete graph based on the decomposition using and combining these layouts. In this paper, we focus on the algorithms for the topological decomposition. We describe them on an intermediate level complementing the previous descriptions on the high and the low level. Besides the motivation, illustrative examples of all cases that need to be considered by the algorithm, standard as well as more complex ones, are given. We complement this description by a complexity analysis of all algorithms.
Submitted: December 2016.
Reviewed: January 2017.
Revised: February 2017.
Accepted: April 2017.
Final: April 2017.
Published: April 2017.
Communicated by Giuseppe Liotta
article (PDF)