Characterization of Level Non-Planar Graphs by Minimal Patterns
Healy, Patrick and Kuusik, Ago and Leipert, Sebastian
(2000)
Characterization of Level Non-Planar Graphs by Minimal Patterns.
Published In:
Computing and combinatorics : COCOON 2000 ; 6th annual international conference ; proceedings, Lecture notes in computer science. 1858 Springer 2000, pp. 74-84.
Abstract
A level graph G = (V,E,phi) is a directed acyclic graph with a mapping phi:V ->{1,2,...,k}, k >= 1, that partitions the vertex set V as V = V1 u V2 u...u Vk, Vj = phi -1 (j) , V n Vj = Ø for i != j, such that phi(v) = phi(u) + 1 for each edge (u,v) in E. The graph G is level planar if it 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 monotonically with respect to the vertical direction, and no edges intersect except at their end vertices. In this paper we give a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar subgraph patterns (MLNP). We show that a MLNP is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations. These characterizations are an important first step towards attacking the NP-hard k-level planarization problem.
Download: |
Postscript
- Preprinted Version
Download (333kB) | Preview |
---|---|
Editorial actions: | View Item (Login required) |
Item Type: | Proceedings article |
---|---|
Citations: | 16 (Google Scholar) | 1 (Web of Science) |
Uncontrolled Keywords: | level graphs maximum level planar subgraph minimal non-planarity |
Subjects: | |
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
ZAIK Number: | zaik2000-382 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 21 Jan 2002 00:00 |
Last Modified: | 16 Jan 2012 13:37 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/382 |