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

03/14/2023
by   Nicolas Bousquet, et al.
0

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-Ω(1) upper bound stood for 25 years until a recent breakthrough from Aichholzer et al. yielding a 2n-Ω(log n) bound. We improve their result with a 2n-Ω(√(n)) upper bound, and we strengthen and shorten the proofs of several of their results.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset