Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00111 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.
|
Revised: July 2005. Submitted: November 2004. Communicated by Emden Gansner and János Pach |
| Journal of Graph Algorithms and Applications |