Abstract
Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line ℓ j = {(x, j) | x ∈ ℝ}. The bijection φ that maps the set of n vertices V to a set of distinct horizontal lines ℓ j forms a labeling of the vertices. Such a graph G with the labeling φ 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 (\(\sf{ULP}\)). Our contributions are three-fold. First, we provide a complete characterization of \(\sf{ULP}\) trees in terms of a pair of forbidden subtrees. Second, we show how to draw \(\sf{ULP}\) trees in linear time. Third, we provide a linear time recognition algorithm for \(\sf{ULP}\) trees.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bachmaier, C., Brandenburg, F.J., Forster, M.: Radial level planarity testing and embedding in linear time. J. Graph Algorithms Appl. 9(1), 53–97 (2005)
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. In: 8th Workshop on Algorithms and Data Structures, pp. 243–255 (2003)
Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet. 18(6), 1035–1046 (1988)
Eades, P., Feng, Q.-W., 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 ulabeled planar trees. Technical Report TR06-03, University of Arizona (2006)
Healy, P., Kuusik, A., Leipert, S.: A characterization of level planar graphs. Discrete Math. 280(1-3), 51–63 (2004)
Heath, L.S., Pemmaraju, S.V.: Recognizing leveled-planar dags in linear time. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 300–311. Springer, Heidelberg (1997)
Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs. II. SIAM J. Comput. 28(5), 1588–1626 (1999)
Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927–958 (1992)
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
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G. (2007). Characterization of Unlabeled Level Planar Trees. In: Kaufmann, M., Wagner, D. (eds) Graph Drawing. GD 2006. Lecture Notes in Computer Science, vol 4372. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70904-6_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-70904-6_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70903-9
Online ISBN: 978-3-540-70904-6
eBook Packages: Computer ScienceComputer Science (R0)