Characterization of Unlabeled Level Planar Graphs

Fowler, J. Joseph and Kobourov, Stephen G. (2008) Characterization of Unlabeled Level Planar Graphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 37-49 (Official URL:

Full text not available from this repository.


We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of n vertices, for any of the n! possible mappings. These graphs are equivalent to the set of unlabeled level planar (ULP) graphs that are level planar over all possible labelings. Our contributions are twofold. First, we provide linear time drawing algorithms for ULP graphs. Second, we provide a complete characterization of ULP graphs by showing that any other graph must contain a subgraph homeomorphic to one of seven forbidden graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_7
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
ID Code:827

Repository Staff Only: item control page


U. Brandes, C. Erten, J. Fowler, F. Frati, M. Geyer, C. Gutwenger, S. Hong, M. Kaufmann, S. Kobourov, G. Liotta, P. Mutzel, and A. Symvonis. Colored simultaneous geometric embeddings. In 13th Computing and Combinatorics Conference (COCOON) 2007. LNCS, vol. 4598, pp. 254–263. Springer, Heidelberg (2007).

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. Computational Geometry: Theory and Applications, 36(2):117-130, 2007.

G. Di Battista and E. Nardelli. Hierarchies and planarity theory. IEEE Transactions on Systems, Man, and Cybernetics, 18(6):1035-1046, 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 unlabeled level planar trees. In Kaufmann and Wagner, editors, 14th Symposium on Graph Drawing (GD), volume 4372 of Lecture Notes in Computer Science, pages 367-369, 2006.

J. J. Fowler and S. G. Kobourov. Characterization of unlabeled planar graphs. Technical Report TR06-04, University of Arizona, 2006.

M. Geyer, M. Kaufmann, and I. Vrto. Two trees which are self-intersecting when drawn simultaneously. In 13th Symposium on Graph Drawing, pages 201-210, 2005.

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

M. Jünger and S. Leipert. Level planar embedding in linear time. J. Graph Algorithms Appl., 6(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èmes des courbes gauches en Topologie. Fundamenta Mathematicae, 15:271-283, 1930.