Polynomial area bounds for MST embeddings of trees ?
In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n22)O(n22) O ( 2 n 2 )  O ( 2 n 2 ) and the authors conjectured that an improvement below cncn c n  c n is not possible, for some constant c>0 c > 0 . In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.
area bounds minimum spanning trees geometric embedding