Polynomial Area Bounds for MST embeddings of trees
Kaufmann, Michael (2008) Polynomial Area Bounds for MST embeddings of trees. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 88-100 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_12).
Full text not available from this repository.
In their seminal paper on geometric minimum spanning trees, Monma and Suri  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