Abstract
We consider characterizations of level planar trees. Healy et al. [8] characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov [7] later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite.
This work was supported in part by NSF grant CCF-0545743.
Chapter PDF
Similar content being viewed by others
References
Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Computational Geometry: Theory and Applications 36(2), 117–130 (2007)
Chimani, M., Gutwenger, C., Mutzel, P., Wong, H.-M.: Layer-free upward crossing minimization. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 55–68. Springer, Heidelberg (2008)
Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Transactions on Systems, Man, and Cybernetics 18(6), 1035–1046 (1989)
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.: Simultaneous Embedding and Level Planarity. PhD thesis, Department of Computer Science, University of Arizona (2009)
Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Computational Geometry: Theory and Applications 42(7), 704–721 (2009)
Fowler, J.J., Kobourov, S.G.: Minimum level nonplanar patterns for trees. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 69–75. Springer, Heidelberg (2008)
Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Mathematics 280(1-3), 51–63 (2004)
Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs. II. SIAM Journal on Computing 28(5), 1588–1626 (1999)
Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs. I. SIAM Journal on Computing 28(4), 1510–1539 (1999)
Jünger, M., Lee, E.K., Mutzel, P., Odenthal, T.: A polyhedral approach to the multi-layer crossing minimization problem. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 13–24. Springer, Heidelberg (1997)
Jünger, M., Leipert, S.: Level planar embedding in linear time. Journal of Graph Algorithms and Applications 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)
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G. (2010). On the Characterization of Level Planar Trees by Minimal Patterns. In: Eppstein, D., Gansner, E.R. (eds) Graph Drawing. GD 2009. Lecture Notes in Computer Science, vol 5849. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11805-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-11805-0_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11804-3
Online ISBN: 978-3-642-11805-0
eBook Packages: Computer ScienceComputer Science (R0)