Geodesic
Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1027-1038.

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

One of the most popular hierarchical graph drawing frameworks - the Sugiyama, Tagawa, and Toda (STT) framework - often introduces dummy vertices to the given directed acyclic graph as part of its methodology to produce the final drawing. The inclusion of dummy vertices increases the size of the input graph and consequently inflates the run time of the subsequent algorithms. Given that most graph drawing problems are NP-hard, good layering algorithms or efficient post-processing - which produces a minimal number of dummy vertices - restrain the increased run time. Many layering or layering post-processing algorithms have quadratic or cubic run time. Here we introduce Root Demotion, a linear time post-processing algorithm for the layering produced by the Longest-Path algorithm that reduces the number of dummy vertices required compared to current post-processing algorithms, consequently shortening the remaining run time of the STT framework.
DOI : 10.7155/jgaa.00448
Keywords: graph drawing, layered drawing, heirachical drawing 
@article{JGAA_2017_21_6_a2,
     author = {Daniel Summer Magruder and Stefan Bonn},
     title = {Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1027--1038},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2017},
     doi = {10.7155/jgaa.00448},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00448/}
}
TY  - JOUR
AU  - Daniel Summer Magruder
AU  - Stefan Bonn
TI  - Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 1027
EP  - 1038
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00448/
DO  - 10.7155/jgaa.00448
LA  - en
ID  - JGAA_2017_21_6_a2
ER  - 
%0 Journal Article
%A Daniel Summer Magruder
%A Stefan Bonn
%T Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing
%J Journal of Graph Algorithms and Applications
%D 2017
%P 1027-1038
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00448/
%R 10.7155/jgaa.00448
%G en
%F JGAA_2017_21_6_a2
Daniel Summer Magruder; Stefan Bonn. Root demotion: efficient post-processing of layered graphs to reduce dummy vertices for hierarchical graph drawing. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 6, pp. 1027-1038. doi : 10.7155/jgaa.00448. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00448/

Cité par Sources :