Minimum Level Nonplanar Patterns for Trees

Fowler, J. Joseph and Kobourov, Stephen G. (2008) Minimum Level Nonplanar Patterns for Trees. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 69-75 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_10).

Full text not available from this repository.

Abstract

Minimum lvel 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.

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

Repository Staff Only: item control page

References

Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet 18(6), 1035-1046 (1998)

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)