Characterization of unlabeled level planar trees

AbstractConsider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1,…,k} for some positive integer k. This assignment ϕ is a labeling if all k numbers are used. If ϕ does not assign adjacent vertices the same label, then ϕ 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 drawn strictly y-monotone, then G is level planar. In this paper, we consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are three-fold. First, we describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. Second, we characterize ULP trees in terms of forbidden subtrees so that any other tree must contain a subtree homeomorphic to one of these. Third, we provide a linear-time recognition algorithm for ULP trees