Level Planarity Testing in Linear Time
Jünger, Michael and Leipert, Sebastian and Mutzel, Petra
(1998)
Level Planarity Testing in Linear Time.
Published In:
Graph drawing : 6th international symposium ; proceedings / GD '98, Montréal, Canada, August 13 - 15, 1998, Lecture notes in computer science. 1547 Springer 1998, pp. 224-237.
Abstract
In a leveled directed acyclic graph G = (V,E) the vertex set V is partitioned into k <= |V| levels V1,V2,...,Vk such that for each edge (u,v) in E with u in Vi and v in Vj 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 Vi are drawn on the line li = {(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 [Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet. 18 (1988), no. 6, 1035--1046] that uses the PQ-tree data structure introduced by Booth and Lueker [Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13 (1976), no. 3, 335--379]. PQ-trees have also been proposed by Heath and Pemmaraju (1996a,1996b) 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,1996b).
Download: |
Postscript
- Preprinted Version
Download (488kB) | Preview |
---|---|
Editorial actions: | View Item (Login required) |
Item Type: | Proceedings article |
---|---|
Citations: | 49 (Google Scholar) | |
Uncontrolled Keywords: | level planarity PQ-trees |
Subjects: | |
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
ZAIK Number: | zpr98-321 |
---|---|
Depositing User: | Prof. Dr. Michael Jünger |
Date Deposited: | 08 May 2003 00:00 |
Last Modified: | 16 Jan 2012 15:44 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/321 |