Geodesic
Topological Decomposition of Directed Graphs
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 589-630.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00431
Keywords: topological decomposition, directed graphs 
@article{JGAA_2017_21_4_a9,
     author = {Ala Abuthawabeh and Dirk Zeckzer},
     title = {Topological {Decomposition} of {Directed} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {589--630},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00431},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00431/}
}
TY  - JOUR
AU  - Ala Abuthawabeh
AU  - Dirk Zeckzer
TI  - Topological Decomposition of Directed Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 589
EP  - 630
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00431/
DO  - 10.7155/jgaa.00431
LA  - en
ID  - JGAA_2017_21_4_a9
ER  - 
%0 Journal Article
%A Ala Abuthawabeh
%A Dirk Zeckzer
%T Topological Decomposition of Directed Graphs
%J Journal of Graph Algorithms and Applications
%D 2017
%P 589-630
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00431/
%R 10.7155/jgaa.00431
%G en
%F JGAA_2017_21_4_a9
Ala Abuthawabeh; Dirk Zeckzer. Topological Decomposition of Directed Graphs. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 589-630. doi : 10.7155/jgaa.00431. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00431/

Cité par Sources :