Flipping Non-Crossing Spanning Trees

For a set P of n points in general position in the plane, the flip graph F(P ) has a vertex for each non-crossing spanning tree on P and an edge between any two spanning trees that can be transformed into each other by one edge flip, i.e., the deletion and addition of exactly one edge. The diameter diam(F(P )) of this flip graph is subject of intensive study. For points P in general position, it is between ⌊ 3 /2 ⋅ n⌋ -5 and 2n -4, with no improvement for 25 years. For points P in convex position, diam(F(P )) lies between ⌊ 3 /2 ⋅ n⌋ -5 and ≈ 1.95n, where the lower bound was conjectured to be tight up to an additive constant and the upper bound is a very recent breakthrough improvement over several previous bounds of the form 2n -o(n).

In this work, we provide new upper and lower bounds on the diameter of F(P ) by mainly focusing on points P in convex position. We improve the lower bound even for this restricted case to diam(F(P )) ≥ 14 /9 ⋅ n -O(1). This disproves the conjectured upper bound of 3 /2 ⋅ n for convex position, while also improving the long-standing lower bound for point sets in general position. In particular, we provide pairs T, T ′ of trees with flip distance dist(T, T ′ ) ≥ 14 /9 ⋅ n -O(1); in these examples, both trees T, T ′ have three boundary edges. We complement this by showing that if one of T, T ′ has at most two boundary edges, then dist(T,

| is the number of edges in one tree that are not in the other. This bound is tight up to additive constants.

Secondly, we significantly improve the upper bound on diam(F(P )) for n points P in convex position from ≈ 1.95n to 5 /3 ⋅ n -3. To prove both our lower and upper bound improvements, we introduce a new tool. Specifically, we convert the flip distance problem for given T, T ′ to the problem of a largest acyclic subset in an associated conflict graph H(T, T ′

). In fact, this method is powerful enough to give an equivalent formulation of the diameter of F(P ) for points P in convex position up to lower-order terms. As such, conflict graphs are likely the key to a complete resolution of this and possibly also other reconfiguration problems.