Transition operations over plane trees.

The operation of transforming one spanning tree into another by replacing an edge
has been considered widely, both for general and planar straight-line graphs. For the
latter, several variants have been studied (e.g., edge slides and edge rotations). In a
transition graph on the set T (S) of noncrossing straight-line spanning trees on a finite
point set S in the plane, two spanning trees are connected by an edge if one can be
transformed into the other by such an operation. We study bounds on the diameter of
these graphs, and consider the various operations on point sets in both general position
and convex position. In addition, we address variants of the problem where operations
may be performed simultaneously or the edges are labeled. We prove new lower and
upper bounds for the diameters of the corresponding transition graphs and pose open
problems.