Jünger, Michael, Leipert, Sebastian and Mutzel, Petra ORCID: 0000-0001-7621-971X (1999). Level Planarity Testing in Linear Time (Full Version). Working Paper.


Download (418kB) | Preview


A level graph G = (V,E,lev) is a directed acyclic graph with a mapping lev : V -> {1,2,...,k}, k >= 1, that partitions the vertex set V as V = V1 u V u...u Vk, V = lev -1 (j), Vi n Vj = Ø 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 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(|V|) time by an algorithm of DiBattista 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 (1995, 1996) to test level planarity of level 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 (1995, 1996).

Item Type: Preprints, Working Papers or Reports (Working Paper)
CreatorsEmailORCIDORCID Put Code
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
URN: urn:nbn:de:hbz:38-548498
Date: 1999
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54849


Downloads per month over past year


Actions (login required)

View Item View Item