Geodesic
Using a Significant Spanning Tree to Draw a Directed Graph
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 6th Asia-Pacific Symposium on Visualisation, APVIS 2007 , Tome 12 (2008) no. 3, pp. 293-317.

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

A directed graph can model any ordered relationship between objects. However, visualizing such graphs can be a challenging task. If the graph is undirected, a popular strategy is to choose a significant spanning tree, nominate a vertex as the root, for example the vertex whose distance from all other vertices is minimal, hang the significant spanning subtrees from this root and add in the remaining edges in some unobtrusive manner [,,,]. In the directed case the spanning tree is a tree DAG and not simply a directed tree with one appropriate root. It may have multiple sources that all warrant root status and so the undirected approach must be modified somewhat. In this paper, we present a method of drawing directed graphs that emphasizes a significant spanning tree. It combines two steps of the Sugiyama framework [] (leveling and crossing minimization) by finding, in linear time, a leveling of the graph that is level planar with respect to some spanning tree and restricting the permutations of the vertices on each level to those that constitute a level planar embedding of this subgraph. The edges of the spanning tree will therefore not cross each other. Using a globally oriented Fiedler vector we choose permutations of the vertices on each level that reduce the number of edge crossings between the remaining edges. 
@article{JGAA_2008_12_3_a2,
     author = {Martin Harrigan and Patrick Healy},
     title = {Using a {Significant} {Spanning} {Tree} to {Draw} a {Directed} {Graph}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {293--317},
     publisher = {mathdoc},
     volume = {12},
     number = {3},
     year = {2008},
     doi = {10.7155/jgaa.00168},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00168/}
}
TY  - JOUR
AU  - Martin Harrigan
AU  - Patrick Healy
TI  - Using a Significant Spanning Tree to Draw a Directed Graph
JO  - Journal of Graph Algorithms and Applications
PY  - 2008
SP  - 293
EP  - 317
VL  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00168/
DO  - 10.7155/jgaa.00168
LA  - en
ID  - JGAA_2008_12_3_a2
ER  - 
%0 Journal Article
%A Martin Harrigan
%A Patrick Healy
%T Using a Significant Spanning Tree to Draw a Directed Graph
%J Journal of Graph Algorithms and Applications
%D 2008
%P 293-317
%V 12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00168/
%R 10.7155/jgaa.00168
%G en
%F JGAA_2008_12_3_a2
Martin Harrigan; Patrick Healy. Using a Significant Spanning Tree to Draw a Directed Graph. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 6th Asia-Pacific Symposium on Visualisation, APVIS 2007
					, Tome 12 (2008) no. 3, pp. 293-317. doi : 10.7155/jgaa.00168. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00168/

Cité par Sources :