Article ID Journal Published Year Pages File Type
415709 Computational Geometry 2011 15 Pages PDF
Abstract

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(2n2)×O(2n2) and the authors conjectured that an improvement below cn×cncn×cn is not possible, for some constant c>0c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,