## Polynomial Area Bounds for MST embeddings of trees
Kaufmann, Michael
(2008)
Full text not available from this repository. ## AbstractIn their seminal paper on geometric minimum spanning trees, Monma and Suri [6] gave a method to embed any tree of maximal degree 5 as a minimum spanning tree in the Euclidean plane. They derived area bounds of $O(2^k^2 times 2^k^2)$ for trees of height $k$ and conjectured that an improvement below $c^n times c^n$ is not possible for some constant $c >0$. We partially disprove this conjecture by giving polynomial area bounds for arbitrary trees of maximal degree 3 and 4.
Repository Staff Only: item control page References |