Loading...
Please wait, while we are loading the content...
Similar Documents
Level Planarity Testing in Linear Time ( Extended Abstract )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Michael, J. Ungera Sébastian Petra, Leipertb Mutzelca |
| Copyright Year | 1998 |
| Abstract | In a leveled directed acyclic graph G = (V; E) the vertex set V is partitioned into k jV j levels V1; V2; : : : ; V k such that for each edge (u; v) 2 E with u 2 Vi and v 2 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 2 Vi are drawn on the line li = f(x; k ? i) j x 2 Rg, 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(jV j) time by an algorithm of Di Battista and Nardelli 1988] that uses the P Q-tree data structure introduced by Booth and Lueker 1976]. P Q-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 unger, 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]. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
