P. Healy, A. Kuusik, S. Leipert
Published in:
D.-Z. Du, P. Eades, V. Estivill-Castro, X. Lin, A. Sharma, Editors, Computing and Combinatorics COCOON 2000, volume 1858; Lecture Notes in Computer Science, Springer Verlag (2000), 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.