A Fast Layout Algorithm for k-Level Graphs

Buchheim, Christoph and Jünger, Michael and Leipert, Sebastian (1999) A Fast Layout Algorithm for k-Level Graphs. [Preprint]

WarningThere is a more recent version of this item available.
[img] Other
Download (143kB)


In this paper, we present a fast layout algorithm for k-level graphs with given permutations of the vertices on each level. The algorithm can be used in particular as a third phase of the Sugiyama algorithm (1981). The Sugiyama algorithm computes a layout for an arbitrary graph by (1) converting it into a k-level graph, (2) reducing the number of edge crossings by permuting the vertices on the levels, and (3) assigning y-coordinates to the levels and x-coordinates to the vertices. In the layouts generated by our algorithm, every edge will have at most two bends, and will be drawn vertically between these bends.

Item Type: Preprint
Classifications: M Methods > M.500 Layered
P Styles > P.480 Layered
G Algorithms and Complexity > G.210 Bends
URI: http://gdea.informatik.uni-koeln.de/id/eprint/17

Available Versions of this Item

Actions (login required)

View Item View Item