Unlabeled Level Planar Trees and Graphs
Alejandro Estrella-Balderrama,
J. Joseph Fowler, and
Stephen G. Kobourov
Department of Computer Science, The University of Arizona
Consider a graph G in which each of the n vertices from vertex set V is assigned a number from the set {1, . . . , k} for some positive integer k. This assignment forms a labeling if all k numbers are used. If adjacent vertices are not assigned the same label, then this forms a leveling that partitions V into k levels. If G has a planar drawing in which the y-coordinate of all vertices match their labels and edges are composed of strictly y-monotone line segments, then G is level planar.
We consider the class of level trees and graphs that are level planar regardless of their labeling. We call such trees or graphs unlabeled level planar (ULP).
A planar graph cannot contain a subgraph homeomorphic to either of the Kuratowski forbidden graphs, K5 or K3,3. Analogously, a level planar graph cannot contain a subgraph matching a minimum level nonplanar (MLNP) pattern. One outcome to the characterization of the set of ULP trees and graphs is in determining the full set of MLNP patterns for trees and graphs.