On the area requirements of Euclidean minimum spanning trees
(2011) WADS — Location: New York, NY (15.August.2011)
Files
document.pdf
Restricted Access - Adobe PDF
- 297.37 KB
Details
- Authors
- Abstract
- In their seminal paper on Euclidean minimum spanning trees [Discrete & Computational Geometry, 1992], Monma and Suri proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that cn × cn area is sometimes required to embed an n-vertex tree of maximum degree 5 as a Euclidean minimum spanning tree, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees. © 2011 Springer-Verlag.
- Affiliations
Citations
Angelini, P., Bruckdorfer, T., Chiesa, M., Frati, F., Kaufmann, M., & Squarcella, C. (2011). On the area requirements of Euclidean minimum spanning trees. WADS, New York, NY.