Level Planarity Testing in Linear Time

Jünger, Michael and Leipert, Sebastian and Mutzel, Petra (1998) Level Planarity Testing in Linear Time. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 224-237 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_17).

This is the latest version of this item.

Full text not available from this repository.


In a leveled 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 Vi, all v \in V_i are drawn on the line l_i={(x,k-i)|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 O(|V|) 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 (1996a,b) to test level planarity of leveled directed acyclic graphs with several sources and sinks. It has been shown in Jünger, Leipert, and Mutzel (1997) that this algorithm is not correct in the sense that it does not state correctly level planarity of every level planar graph. In this paper, we present a correct linear 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 (1996a,b).

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_17
Classifications:G Algorithms and Complexity > G.700 Layering
M Methods > M.600 Planar
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:265

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 E. Nardelli. Hirarchies and Planarity Theory. IEEE Transactions on Systems, Man and Cybernetics 18 (1988) 1035-1046.

Heath, L.S. and S.V. Pemmaraju: Recognizing leveled-planar DAGs in linear time. LNCS 1027, in: F. Brandenburg (ed.), Proc. on Graph Drawing '95, Passau (1996a) 300-311.

L.S. Heath and S.V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part II. Technical Report, Dept. of Comp. Sci., Virginia Polytechnic Institute & State University, 1996b.

M. Jünger, S. Leipert, and P. Mutzel. Pitfalls of using PQ-trees in Automatic Graph Drawing. In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 193-204. Springer Verlag, 1997.