A note on the flip distance between non-crossing spanning trees

Abstract

We consider spanning trees of $n$ points in convex position whose edges are pairwise non-crossing. Applying a flip to such a tree consists in adding an edge and removing another so that the result is still a non-crossing spanning tree. Given two trees, we investigate the minimum number of flips required to transform one into the other. The naive $2n-\Omega (1)$ upper bound stood for 25 years until a recent breakthrough from Aichholzer et al. yielding a $2n-\Omega (\log n)$ bound. We improve their result with a $2n-\Omega (\sqrt{n})$ upper bound, and we strengthen and shorten the proofs of several of their results.