**O. Aichholzer, F. Aurenhammer, and F. Hurtado**

Let be a set of points in the Euclidean plane. Consider the set of all non-crossing spanning trees of . A *tree graph*
is the graph that has as its vertex set and
that connects vertex (tree) to vertex iff
, where
is some operation that exchanges two tree edges following a
specific rule. The existence of a path between two vertices in
means transformability of the corresponding trees into each
other by repeated application of the operation . The length of a
shortest path corresponds to the distance between the two trees with respect
to the operation . Distances of this kind provide a measure of
similarity between trees. We prove new results on
for
two classical operations , namely the (improving and crossing-free)
*edge move* and the (crossing-free) *edge slide*. Applications to
morphing of trees and to the continuous deformation of sets of line segments
seem reasonable. Our results mainly rely on a fact of interest in its own
right: Let and be the minimum spanning tree and the Delaunay
triangulation of , respectively. Then any pair , for
and being constrained Delaunay triangulation, can
be transformed into the pair
via a canonical
tree/triangulation sequence.