Paper Info
Title
Polynomial area bounds for MST embeddings of trees
Abstract
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(2k2 × 2k2) for trees of height k and conjectured that an improvement below cn × cn 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.
Year
DOI
Venue
2007
10.1016/j.comgeo.2011.05.005
Graph Drawing
Keywords
Field
DocType
constant c,seminal paper,maximal degree,polynomial area bound,euclidean plane,area bound,arbitrary tree,height k,geometric minimum,???,mst embeddings,maximum degree,minimum spanning tree
Discrete mathematics,Combinatorics,Minimum degree spanning tree,Polynomial,k-minimum spanning tree,Euclidean minimum spanning tree,Spanning tree,Shortest-path tree,Conjecture,Mathematics,Minimum spanning tree
Conference
Volume
Issue
ISSN
44
9
Computational Geometry: Theory and Applications
ISBN
Citations 
PageRank 
3-540-77536-6
6
0.46
References 
Authors
10
1
Name
Order
Citations
PageRank
Michael Kaufmann136125.45