Drawing a Tree as a Minimum Spanning Tree Approximation - Giacomo, Emilio Di; Didimo, Walter; Liotta, Giuseppe; Meijer, Henk (ISAAC'10: Proceedings of the International Symposium on Algorithms and Computations, 2010)
We introduce and study (1+e)-EMST drawings, i.e. planar straight-line drawings of trees such that, for any fixed e>0, the distance between any two vertices is at least 1/1+e the length of the longest edge in the path connecting them. (1+e)-EMST drawings are good approximations of Euclidean minimum spanning trees. While it is known that only trees with bounded degree have a Euclidean minimum spanning tree realization, we show that every tree T has a (1+e)-EMST drawing for any given e>0. We also present drawing algorithms that compute (1+e)-EMST drawings of trees with bounded degree in polynomial area. As a byproduct of one of our techniques, we improve the best known area upper bound for Euclidean minimum spanning tree realizations of complete binary trees.