Level Planarity Testing and Embedding in Linear Time

S. Leipert
PhD-Thesis, Universität zu Köln (1998)

My PhD-Thesis on Level Planarity Testing and Embedding in Linear Time is available as a compressed (with `gzip') 600 dpi Postscript file (1256K) or as a compressed 300 dpi PostScript file (1171K).

Abstract

In a level graph G = (V,E) the vertex set V is partitioned into $k \le \vert V\vert$ levels $V^1,V^2,\ldots,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ⁱ, all $v \in V^i$ are drawn on the line $l_i = \{(x,k-i) \mid x \in \R\}$ , the edges are drawn monotone with respect to the vertical direction, and no edges intersect except at their end vertices. If G has a single source, the test can be performed in $\order(\vert V\vert)$ time by an algorithm of Di Battista and Nardelli (1988) that uses the PQ-tree data structure introduced by Booth and Lueker (1976). PQ-trees have also been proposed by Heath and Pemmaraju (1996) to test level planarity of leveled directed acyclic graphs with several sources and sinks. We show that this algorithm is not correct in the sense that it does not state correctly level planarity of every level planar graph.

We have developed a correct $\order(\vert V\vert\log \vert V\vert)$ time level planarity testing algorithm that is based on two main new techniques that replace the incorrect crucial parts of the algorithm of Heath and Pemmaraju. Furthermore we succeeded in improving the level planarity test to $\order(\vert V\vert)$ time. An implementation of the level planarity test is also provided in C++.

Based on our linear time level planarity test we have developed a linear time level planar embedding algorithm. A level embedding consists of a permutation of vertices of V^j for every $j \in \{1,2,\dots,k\}$ with respect to a level drawing. In order to compute a level planar embedding of a level planar graph G = (V,E) the graph G is augmented to a planar st-graph G_st = (V_st,E_st) with $V_{st} = V \uplus \{s,t\}$ and $E \subset E_{st}$ . An st-graph is a directed acyclic graph with a single source s, a single sink t, and an edge (s,t). The graph G_st is planar embedded with the edge (s,t) on the boundary of the outer face using the algorithm of Chiba et al. (1985). We proved that due to the properties of the chosen augmentation and the algorithm of Chiba et al. (1985), the planar embedding of G_st implies a level planar embedding of its subgraph G. The level planar embedding of G therefore can be obtained by a simple depth first search approach from the planar embedding of the st-graph G_st.

The augmentation of a level graph G to an st-graph G_st is divided into two phases. In the first phase an outgoing edge is added to every sink of G applying a modification of our level planar test. Using the same algorithmic concept as in the first phase, an incoming edge is added to every source of G in the second phase.

In order to add an outgoing edge for every sink of G without destroying level planarity, we need to determine the position of a sink $v \in V^j$ , $j \in \{1,2,\dots,k-1\}$ in the PQ-trees. This is done by inserting a so called sink indicator as a leaf into the PQ-trees. The indicator is ignored throughout the application of the level planarity test and will be removed either with the leaves corresponding to the incoming edges of some vertex $w \in V^l$ , $l \ge j$ , or it can be found in the final PQ-tree.

Using some extra information that is computed by our level planar embedding algorithm, we produce a level drawing of the graph G by drawing the st-graph G_st, remove afterwards all edges and the vertices s and t that are not contained in G. We found that suitable approaches for drawing the st-graph G_st have been presented by Di Battista and Nardelli (1988) and Di Battista, Nardelli, and Tollis (1992).

...back to Leipert's Home Page

Dec-29-1998