2023/03/14 by Nicolás Bousquet, Bousquet, Nicolas, Valentin Gledel +5 · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2303.07710
openalex publication_date 2023/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.