Abstract
minimum Level Nonplanar (MLNP) patterns play the role for level planar graphs that the forbidden Kuratowksi subdivisions K 5 and K 3,3 play for planar graphs. We add two (MLNP) patterns for trees to the previous set of tree patterns given by Healy et al. [4]. Neither of these patterns match any of the previous patterns. We show that this new set of patterns completely characterizes level planar trees.
Chapter PDF
Similar content being viewed by others
References
Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet 18(6), 1035–1046 (1988)
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.: Minimum level nonplanar patterns for trees. Technical Report TR07-04, University of Arizona (2007), ftp://ftp.cs.arizona.edu/reports/2007/TR07-04.pdf
Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Math. 280(1-3), 51–63 (2004)
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). Minimum Level Nonplanar Patterns for Trees. 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_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-77537-9_10
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)