An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing

Eiglsperger, Markus and Siebenhaller, Martin and Kaufmann, Michael (2004) An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 155-166(Official URL:

Full text not available from this repository.


Sugiyama's algorithmic framework for layered graph drawing is commonly used in practical software. The extensive use of dummy vertices to break long edges between non-adjacent layers often leads to unsatisfactorial performance. The worst-case running-time of Sugiyamarsquos 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 and hence reduce the worst-case time complexity of Sugiyamarsquos approach by an order of magnitude to O((|V|+|E|)\log|E|) requiring O(|V|+|E|) space. This work has partially been supported by the DFG-grant Ka512/8-2. It has been performed when the first author was with the Universität Tübingen.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_17
Classifications: M Methods > M.500 Layered
P Styles > P.480 Layered

Actions (login required)

View Item View Item