Sequences of spanning trees and a fixed tree theorem

AbstractLet TS be the set of all crossing-free spanning trees of a planar n-point set S. We prove that TS contains, for each of its members T, a length-decreasing sequence of trees T0,…,Tk such that T0=T, Tk=MST(S), Ti does not cross Ti−1 for i=1,…,k, and k=O(logn). Here MST(S) denotes the Euclidean minimum spanning tree of the point set S.As an implication, the number of length-improving and planar edge moves needed to transform a tree T∈TS into MST(S) is only O(nlogn). Moreover, it is possible to transform any two trees in TS into each other by means of a local and constant-size edge slide operation. Applications of these results to morphing of simple polygons are possible by using a crossing-free spanning tree as a skeleton description of a polygon