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 , pp. 88-100(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_12).

Full text not available from this repository.

Abstract

In 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.

Item Type:	Conference Paper
Additional Information:	10.1007/978-3-540-77537-9_12
Classifications:	M Methods > M.900 Tree G Algorithms and Complexity > G.070 Area / Edge Length
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/831

Actions (login required)

View Item