Geodesic
An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Twelfth International Symposium on Graph Drawing, GD 2004 , Tome 9 (2005) no. 3, pp. 305-325.

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

Sugiyama's algorithm for layered graph drawing is very popular and commonly used in practical software. The extensive use of dummy vertices to break long edges between non-adjacent layers often leads to unsatisfying performance. The worst-case running-time of Sugiyama's approach is O(|V||E|log|E|) requiring O(|V||E|) memory, which makes it unusable for the visualization of large graphs. By a conceptually simple new technique we are able to keep the number of dummy vertices and edges linear in the size of the graph without increasing the number of crossings. We reduce the worst-case time complexity of Sugiyama's approach by an order of magnitude to O((|V|+|E|)log|E|) requiring O(|V|+|E|) space. 
@article{JGAA_2005_9_3_a1,
     author = {Markus Eiglsperger and Martin Siebenhaller and Michael Kaufmann},
     title = {An {Efficient} {Implementation} of {Sugiyama's} {Algorithm} for {Layered} {Graph} {Drawing}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {305--325},
     publisher = {mathdoc},
     volume = {9},
     number = {3},
     year = {2005},
     doi = {10.7155/jgaa.00111},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00111/}
}
TY  - JOUR
AU  - Markus Eiglsperger
AU  - Martin Siebenhaller
AU  - Michael Kaufmann
TI  - An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing
JO  - Journal of Graph Algorithms and Applications
PY  - 2005
SP  - 305
EP  - 325
VL  - 9
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00111/
DO  - 10.7155/jgaa.00111
LA  - en
ID  - JGAA_2005_9_3_a1
ER  - 
%0 Journal Article
%A Markus Eiglsperger
%A Martin Siebenhaller
%A Michael Kaufmann
%T An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing
%J Journal of Graph Algorithms and Applications
%D 2005
%P 305-325
%V 9
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00111/
%R 10.7155/jgaa.00111
%G en
%F JGAA_2005_9_3_a1
Markus Eiglsperger; Martin Siebenhaller; Michael Kaufmann. An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Twelfth International Symposium on Graph Drawing, GD 2004
					, Tome 9 (2005) no. 3, pp. 305-325. doi : 10.7155/jgaa.00111. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00111/

Cité par Sources :