Abstract
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.
Chapter PDF
Similar content being viewed by others
References
Brandes, U., Erten, C., Fowler, J.J., Frati, F., Geyer, M., Gutwenger, C., Hong, S., Kaufmann, M., Kobourov, S.G., Liotta, G., Mutzel, P., Symvonis, A.: Colored simultaneous geometric embeddings. In: COCOON 2007. LNCS, vol. 4598, pp. 254–263. Springer, Heidelberg (2007)
Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous graph embedding. Computational Geometry: Theory and Applications 36(2), 117–130 (2007)
Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Transactions on Systems, Man, and Cybernetics 18(6), 1035–1046 (1988)
Eades, P., Feng, Q., Lin, X., Nagamochi, H.: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Algorithmica 44(1), 1–32 (2006)
Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 367–369. Springer, Heidelberg (2007)
Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled planar graphs. Technical Report TR06-04, University of Arizona (2006), ftp://ftp.cs.arizona.edu/reports/2006/TR06-04.pdf
Geyer, M., Kaufmann, M., Vrto, I.: Two trees which are self-intersecting when drawn simultaneously. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 201–210. Springer, Heidelberg (2006)
Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Math. 280(1-3), 51–63 (2004)
Jünger, M., Leipert, S.: Level planar embedding in linear time. J. Graph Algorithms Appl. 6(1), 67–113 (2002)
Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224–237. Springer, Heidelberg (1999)
Kuratowski, C.: Sur les problèmes des courbes gauches en Topologie. Fundamenta Mathematicae 15, 271–283 (1930)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fowler, J.J., Kobourov, S.G. (2008). Characterization of Unlabeled Level Planar Graphs. In: Hong, SH., Nishizeki, T., Quan, W. (eds) Graph Drawing. GD 2007. Lecture Notes in Computer Science, vol 4875. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77537-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-77537-9_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77536-2
Online ISBN: 978-3-540-77537-9
eBook Packages: Computer ScienceComputer Science (R0)