Characterization of Unlabeled Level Planar (ULP) Trees

Estrella-Balderrama, Alejandro and Fowler, J. Joseph and Kobourov, Stephen G. (2007) Characterization of Unlabeled Level Planar (ULP) Trees. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 367-379 (Official URL:

Full text not available from this repository.


Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line $\ell_j = \{(x, j) \,|\, x \in \BB{R}\}$. The bijection $\phi$ that maps the set of n vertices V to a set of distinct horizontal lines $\ell_j$\isTR{ for $j\in \{1,2,\ldots,n\}$ forms a labeling of the vertices. Such a graph G with the labeling $\phi$ is called an n-level graph and is said to be n-level planar if it can be drawn with straight-line edges and no crossings while keeping each vertex on its own level. In this paper, we consider the class of trees that are n-level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are three-fold. First, we provide a complete characterization of ULP trees in terms of a pair of forbidden subtrees. Second, we show how to draw ULP trees in linear time. Third, we provide a linear time recognition algorithm for ULP trees.n

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_35
Classifications:Z Theory > Z.750 Topology
M Methods > M.900 Tree
ID Code:792

Repository Staff Only: item control page


C. Bachmaier, F. J. Brandenburg, and M. Forster. Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl., 9(1):53-97, 2005.

P. Brass, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell. On simultaneous graph embedding. In 8th

Workshop on Algorithms and Data Structures, pages 243-255, 2003.

G. Di Battista and E. Nardelli. Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet., 18(6):1035-1046 (1989), 1988.

P. Eades, Q. Feng, X. Lin, and H. Nagamochi. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica, 44(1):1-32, 2006.

A. Estrella-Balderrama, J. J. Fowler, and S. G. Kobourov. Characterization of ulabeled planar trees. Technical Report TR06-03, University of Arizona, 2006.

P. Healy, A. Kuusik, and S. Leipert. A characterization of level planar graphs. Discrete Math., 280(1-3):51-63, 2004.

L. S. Heath and S. V. Pemmaraju. Recognizing leveled-planar dags in linear time. In 4th Symposium on Graph Drawing (GD), pages 300-311. 1996.

L. S. Heath and S. V. Pemmaraju. Stack and queue layouts of directed acyclic graphs. II. SIAM J. Comput., 28(5):1588-1626, 1999.

L. S. Heath and A. L. Rosenberg. Laying out graphs using queues. SIAM J. Comput., 21(5):927-958, 1992.

M. Jünger and S. Leipert. Level planar embedding in linear time. J. Graph Algorithms Appl., 6:no. 1, 67-113, 2002.

M. Jünger, S. Leipert, and P. Mutzel. Level planarity testing in linear time. In 6th Symposium on Graph Drawing (GD), pages 224-237. 1998.

C. Kuratowski. Sur les probl`emes des courbes gauches en Topologie. Fundamenta Mathematicae, 15:271-283, 1930.