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. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 229-240 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_22).

This is the latest version of this item.

Full text not available from this repository.

Abstract

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 [8]. In the generated layouts, every edge has at most two bends and is drawn vertically between these bends. The total length of short edges is minimized levelwise.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_22
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.210 Bends
P Styles > P.480 Layered
ID Code:365

Available Versions of this Item

Repository Staff Only: item control page

References

F. J. Brandenburg, M. Jünger, and P. Mutzel. Algorithmen zum automatischen Zeichnen von Graphen. Informatik-Specktrum 20, pages 199-207, 1997.

C. Buchheim, M. Jünger, and S. Leipert. A fast layout algorithm for k- level graphs. Technical report, Institut für Informatik, Universität zu Köln, 1999.

E.R. Gansner, E. Koutsofios, S. C. North, and K.-P. Vo. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 19(3):214-230, 1993.

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

M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. Journal of Graph Algorithms and Applications, 1:1-25, 1997.

Petra Mutzel et al. A library of algorithms for graph drawing. In S. H. Whitesides, editor, Graph Drawing '98, volume 1547 of Lecture Notes in Computer Science, pages 456-457. Springer Verlag, 1998.

G. Sander. A fast heuristic for hierarchical Manhattan layout. In F. J. Brandenburg, editor, Graph Drawing '95, volume 1027 of Lecture Notes in Computer Science, pages 447-458. Springer Verlag, 1996.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for viesual understanding of hierarchical systems. IEEE Transactions on Systems, Man and Cybernetics, 11(2):109-125, 1981.