Drawing a tree as a minimum spanning tree approximation

摘要

We introduce and study (1+ε)-EMST drawings, i.e., planar straight-line drawings of trees such that, for any fixed ε>0, the distance between any two vertices is at least 11+ε the length of the longest edge in the path connecting them. (1+ε)-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+ε)-EMST drawing for any given ε>0. We also present drawing algorithms that compute (1+ε)-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.