Level Planar Embedding in Linear Time

Jünger, Michael and Leipert, Sebastian (1999) Level Planar Embedding in Linear Time. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 72-81 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_7).

WarningThere is a more recent version of this item available.

Full text not available from this repository.


In a level directed acyclic graph G=(V,E) the vertex set V is partitioned into k \le |V| levels V^1, V^2,..., V^k such that for each edge (u,v) \in E with u \in V^i and v \in V^j we have i<j. The level planarity testing problem is to decide if G can be drawn in the plane such that for each level V^i, all v \in V^i 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 expect 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 V^i (1 \le i \le k). We present an O(|V|) time algorithm for embedding level planar graphs. This approach is based on a level planarity test by Jünger, Leipert, and Mutzel [6].

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_7
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.480 Layered
ID Code:273

Available Versions of this Item

Repository Staff Only: item control page


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

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

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

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

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

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

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