Transforming spanning trees and pseudo-triangulations
O. Aichholzer, F. Aurenhammer, C. Huemer, and H. Krasser
be the set of all crossing-free straight line spanning trees of a
. Consider the graph
where two members
are adjacent if
only in points
or in common edges. We prove that the diameter of
denotes the number of convex layers of
. Based on
this result, we show that the flip graph
(where two pseudo-triangulations are adjacent if
they differ in exactly one edge - either by replacement or by removal) has a
. This sharpens a known
be the induced subgraph of pointed
. We present an example showing that the
distance between two nodes in
is strictly larger than
the distance between the corresponding nodes in
Reference: O. Aichholzer, F. Aurenhammer, C. Huemer, and H. Krasser.
Transforming spanning trees and pseudo-triangulations.
In Proc. European Workshop on Computational Geometry EuroCG
'05, pages 81-84, Eindhoven, The Netherlands, 2005.