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.

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
ID Code:831

Repository Staff Only: item control page

References

Di Battista, G., Eades P., Tamassia R. and I. G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.

Di Battista, G., and Liotta G., Computing proximity drawings of trees in the 3-dimensioanl space, 4th Int. Workshop on Algorithms and Data Structures, LNCS 955, 239-250, 1995.

Eades P., and Whitesides S.: The Realization Problem for Euclidean Minimum Spanning Trees in NP-Hard. Algorithmica 16(1): 60-82 (1996) 1-15.

Cheng H., Liu Q., and Jia X.: Heuristic algorithms for real-time data aggregation in wireless sensor networks, Proceedings of the 2006 International Conference on Communications and Mobile Computing, 2006.

King, J., Realization of Degree 10 Minimum Spanning Trees in 3-Space , Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG'06), 39-42, 2006.

Clyde L. Monma C.L., and Suri S.: Transitions in Geometric Minimum Spanning Trees. Discrete & Computational Geometry 8: 265-293, 1992