**O. Aichholzer, F. Aurenhammer, C. Huemer, and H. Krasser**

Let be the set of all crossing-free straight line spanning trees of a
planar -point set . Consider the graph where two members
and of are adjacent if intersects only in points
of or in common edges. We prove that the diameter of is
, where denotes the number of convex layers of . Based on
this result, we show that the flip graph of
pseudo-triangulations of (where two pseudo-triangulations are adjacent if
they differ in exactly one edge - either by replacement or by removal) has a
diameter of . This sharpens a known bound.
Let
be the induced subgraph of pointed
pseudo-triangulations of . We present an example showing that the
distance between two nodes in
is strictly larger than
the distance between the corresponding nodes in .