Level Planar Embedding in linear Time

Jünger, Michael and Leipert, Sebastian (2002) Level Planar Embedding in linear Time. [Journal (On-line/Unpaginated)]

This is the latest version of this item.

[img] PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
537Kb

Abstract

A level graph G = (V,E,lev) is a directed acyclic graph with a mapping lev : V -> {1,2,dots,k}, k >= 1, that partitions the vertex set V as V = V1 u V2 u...u Vk, Vj = lev^{-1}(j), Vi n Vj = 0 for i != j, such that lev(v) >= lev(u) + 1 for each edge (u,v) in E. The level planarity testing problem is to decide if G can be drawn in the plane such that for each level Vi, all v in Vi are drawn on the line l_i = {(x,k-i) | x in R}, the edges are drawn monotonically with respect to the vertical direction, and no edges intersect except at their end vertices. In order to draw a level planar graph without edge crossings, a level planar embedding of the level graph has to be computed. Level planar embeddings are characterized by linear orderings of the vertices in each Vi (1 <= i <= k). We present an order(|V|) time algorithm for embedding level planar graphs. This approach is based on a level planarity test by Jünger, Leipert, Mutzel 1999.

Item Type:Journal (On-line/Unpaginated)
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.480 Layered
P Styles > P.540 Planar
ID Code:33

Available Versions of this Item

Repository Staff Only: item control page

References

Booth, K. and Luecker, G. (1976) Testing for consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13 335-379.

Chiba, N. and Nishizeki, T. and Abe, S. and Ozawa, T. (1985) A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 30 54-76.

Di Battista, G. and Tamassia, R. (1988) Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61 175-198.

Di Battista, G. and Tamassia, R. and Tollis, I. G. (1992) Constrained visibility representations of graphs. Information Processing Letters, 41 1-7.

Even, S. and Tarjan, R. E. (1976) Computing and st-numbering. Theoretical Computer Science, 2 339-344.

Fulkerson, D. R. and Gross, O. A. (1965) Incidence matrices and interval graphs. Pacific J. Mathematics, 15 835-855.

Heath, L. S. and Pemmaraju, S. V. (1995) Recognizing leveled-planar dags in linear time. In: F. J. Brandenburg (ed.) Proc. Graph Drawing 95, volume 1027 of Lecture Notes in Computer Science, Springer Verlag, pp. 300-311.

Heath, L. S. and Pemmaraju, S. V. (1996) Stack and queue layouts of directed acyclic graphs: Part II. Technical report, Department of Computer Science, Virginia Polytechnic Institute & State University.

Jünger, M. and Leipert, S. and Mutzel, P. (1998) Level planarity testing in linear time. In: S. Whitesides (ed.) Graph Drawing 98, volume 1547 of Lecture Notes in Computer Science, Springer Verlag, pp. 224-237.

Jünger, M. and Leipert, S. and Mutzel, P. (1999) Level planarity testing in linear time (full version). Technical report, Institut für Informatik, Universität zu Köln. # Kant, G. (1993) A more compact visibility representation. In: J. van Leeuwen, (ed.) Proc. 19th International Workshop on Graph-Theoreticaal Concepts in Computer Science, Lecture Notes in Computer Science. Springer Verlag.

Leipert, S. (1998) Level Planarity Testing and Embedding in Linear Time. PhD thesis, Universität zu Köln.

Luccio, F. and Mazzone, S. and Wong, C. (1987) A note on visibilitiy graphs. Discrete Mathematics, 64 209-219.

Rosenstiehl, P. and Tarjan, R. E. (1986) Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete and Computational Geometry, 1 343-353.

Tamassia, R. and Tollis, I. G. (1986) A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1 321-341.

Tamassia, R. and Tollis, I. G. (1989) Tesselation representations of planar graphs. In: Proc. 27th Allerton Conf. Communication Control Computing, pp. 48-57.