Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00431
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
|
Journal Supporters
|