Special Issue on Selected Papers from the Twelfth International Symposium on Graph Drawing, GD 2004
An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing
Markus Eiglsperger, Martin Siebenhaller, and Michael Kaufmann
Vol. 9, no. 3, pp. 305-325, 2005. Regular paper.
Abstract 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.
Submitted: November 2004.
Revised: July 2005.
Communicated by Emden Gansner and János Pach
article (PDF)