Polynomial Area Bounds for MST embeddings of treesKaufmann, Michael (2008) Polynomial Area Bounds for MST embeddings of trees. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 88-100(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_12). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_12
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.
Actions (login required)
|