The parking edge conjecture for plane spanning trees

From papers

Let SS be a convex point set, and let TinT_{\text{in}} and TtarT_{\text{tar}} be plane spanning trees on SS. A parking edge is an edge appearing in a flip sequence that is not contained in TinTtarT_{\text{in}}\cup T_{\text{tar}}. Parking edge conjecture. There is a shortest flip sequence from TinT_{\text{in}} to TtarT_{\text{tar}} that only uses parking edges from the boundary of the convex hull of SS. The conjecture restricts temporary edges in shortest flip sequences to the convex-hull boundary; the supplied text states that a compatible-flip analogue is proved, but does not state that this original unrestricted-flip conjecture is resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Oswin Aichholzer, Joseph Dorfer and Birgit Vogtenhuber, “Constrained Flips in Plane Spanning Trees”, arXiv:2508.15520 (2025).

Solutions 0

No solutions have been posted yet.