On the Characterization of Level Planar Trees by Minimal Patterns

Estrella-Balderrama, Alejandro and Fowler, J. Joseph and Kobourov, Stephen G. (2010) On the Characterization of Level Planar Trees by Minimal Patterns. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009 , pp. 69-80(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_9).

Full text not available from this repository.

Abstract

We consider characterizations of level planar trees. Healy et al. characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov 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.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-642-11805-0_9
Classifications:	M Methods > M.600 Planar G Algorithms and Complexity > G.700 Layering G Algorithms and Complexity > G.770 Planarity Testing
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1085

Actions (login required)

View Item