On the area requirements of Euclidean minimum spanning trees

In their seminal paper on Euclidean minimum spanning trees, Monma and Suri (1992) 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 there exist n  -vertex trees of maximum degree 5 that require cn×cncn×cn area to be embedded as Euclidean minimum spanning trees, for some constant c>1c>1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.