A Fast Layout Algorithm for k-Level Graphs

Buchheim, Christoph and J√ľnger, Michael and Leipert, Sebastian (2001) A Fast Layout Algorithm for k-Level Graphs.
Published In: Graph drawing : 8th international symposium, GD 2000, Colonial Williamsburg, VA, USA, September 20 - 23, 2000 ; proceedings, Lecture Notes in Computer Science. 1984 Springer 2001, pp. 86-89.


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.

Download: [img] Postscript - Preprinted Version
Download (501kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik1999-368
Depositing User: Christoph Buchheim
Date Deposited: 12 Apr 2002 00:00
Last Modified: 12 Jan 2012 13:05
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/368