Flipping Non-Crossing Spanning Trees
Håvard Bakke Bjerkevik, Linda Kleist, Torsten Ueckerdt, Birgit Vogtenhuber · Society for Industrial and Applied Mathematics eBooks · 2025
For a set P of n points in general position in the plane, the flip graph F (P ) has a vertex for each noncrossing 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 and 2n - 4, with no improvement for 25 years. For points P in convex position, diam(F (P )) lies between 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 ).