TY - GEN
T1 - Efficiently drawing a significant spanning tree of a directed graph
AU - Harrigan, Martin
AU - Healy, Patrick
PY - 2007
Y1 - 2007
N2 - 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 [18, 19, 25, 13]. In the directed case the spanning tree is a tree DAG (a directed graph without any undirected cycles) and not simply a directed tree with one appropriate root. It may have multiple sources (vertices with indegree equal to zero) 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 can be considered a variation of the Sugiyama framework [23] in that it combines two steps of the framework (leveling and crossing minimisation) 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 the globally oriented Fiedler vector we choose permutations of the vertices on each level that reduce the number of crossings between the remaining edges.
AB - 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 [18, 19, 25, 13]. In the directed case the spanning tree is a tree DAG (a directed graph without any undirected cycles) and not simply a directed tree with one appropriate root. It may have multiple sources (vertices with indegree equal to zero) 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 can be considered a variation of the Sugiyama framework [23] in that it combines two steps of the framework (leveling and crossing minimisation) 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 the globally oriented Fiedler vector we choose permutations of the vertices on each level that reduce the number of crossings between the remaining edges.
KW - Fiedler vector
KW - Graph drawing
KW - Level planarity
KW - Significant spanning tree
UR - http://www.scopus.com/inward/record.url?scp=34547306713&partnerID=8YFLogxK
U2 - 10.1109/APVIS.2007.329275
DO - 10.1109/APVIS.2007.329275
M3 - Conference contribution
AN - SCOPUS:34547306713
SN - 1424408083
SN - 9781424408085
T3 - Asia-Pacific Symposium on Visualisation 2007, APVIS 2007, Proceedings
SP - 53
EP - 59
BT - Asia-Pacific Symposium on Visualisation 2007, APVIS 2007, Proceedings
T2 - 6th Asia-Pacific Symposium on Visualisation 2007, APVIS 2007
Y2 - 5 February 2007 through 7 February 2007
ER -