Topological Decomposition of Directed Graphs

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 Article type: Regular paper Communicated by: G. Liotta