Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00168
Using a Significant Spanning Tree to Draw a Directed Graph
Vol. 12, no. 3, pp. 293317, 2008. Regular paper.
Abstract 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.

Submitted: July 2007.
Reviewed: September 2007.
Revised: January 2008.
Accepted: March 2008.
Final: July 2008.
Published: October 2008.
Communicated by
SeokHee Hong
