Papers › Reconfiguration of plane trees in convex geometric graphs
Reconfiguration of plane trees in convex geometric graphs
Nicolas Bousquet, Lucas De Meyer, Théo Pierron, Alexandra Wesolek
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most 2n-4 between any pair of non-crossing spanning trees (where n denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least 3/2 n. Two recent results of Aichholzer et al. and Bousquet et al. improved the Avis and Fukuda upper bound by proving that there always exists a flip sequence of length respectively at most 2n - logn and 2n - √(n). We improve the upper bound by a linear factor for the first time in 25 years by proving that there always exists a flip sequence between any pair of non-crossing spanning trees T₁,T₂ of length at most c n where c ≈1.95. Our result is actually stronger since we prove that, for any two trees T₁,T₂, there exists a flip sequence from T₁ to T₂ of length at most c |T₁ ∖T₂|. We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees T₁,T₂ such that a minimal flip sequence has length 5/3 |T₁ ∖T₂|, improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices. We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and rotations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections