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
140Kb

Abstract

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
ID Code:17
Alternative Locations:http://e-archive.informatik.uni-koeln.de/368/

Available Versions of this Item

Repository Staff Only: item control page

References

AGD - a library of algorithms for graph drawing. http://www.mpi-sb.mpg.de/AGD.

Brandenburg, F. J. and Jünger, M. and Mutzel, P. (1997) Algorithmen zum automatischen Zeichnen von Graphen. Informatik-Spektrum 20, pp. 199-207. .

Di Battista, G. and Eades, P. and Tamassia, R. and Tollis, I. G. (1994) Algorithms for drawing graphs: an annotated bibliography, 1994. Via ftp from wilma.cs.brown.edu,file/pub/papaers/compgeo/gdbiblio.ps.Z.

Eades, P. and Lin, X. (1991) Notes on layer assignment problem for drawing directed graphs. In: Proc. 14th Australian Computer Science Conference.

Eades, P. and Mckay, B. D. and Wormland, N. C. (1986) On an edge crossing problem. In: Proc. 9th Australian Computer Science Conference, pp. 327-334.

Garey, M. R. and Johnson, D. S. (1983) Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4 (3) 312-316.

Gansner, E. R. and Koutsofios, E. and North, S. C. and Vo, K. P. (1993) A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19 (3) 214-230.

Jünger, M. and Mutzel, P. (1997) 2-layer straight line crossing minimization: perfomance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications, 1 1-25.

Sugiyama, K. and Tagawa, S. and Toda, M. (1981) Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11 109-125.

Sugiyama, K. (1984) A readability requirement on drawing digraphs: Level assignment and edge removal for reducing the total lenght of lines. International Institute for Advanced Study of Social Information Science.