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 $\frac{1}{1 + \varepsilon}$ 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.
Drawing a Tree as a Minimum Spanning Tree Approximation
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe;
2010
Abstract
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 $\frac{1}{1 + \varepsilon}$ 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
