TOPICS
Search

Plane Spanning Tree Flip Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The plane spanning tree flip graph of a finite set of planar points has one graph vertex for each spanning tree drawn on the points by line segments that meet only at shared endpoints. Two such trees are adjacent when deleting one graph edge and inserting another transforms one tree into the other (Aichholzer et al. 2024, 2026). This operation is called a flip. The flip distance between two trees is their graph distance in the flip graph.

The happy edge conjecture asked whether two plane spanning trees always have a shortest path in the flip graph that preserves all their shared edges. The conjecture is false (Aichholzer et al. 2026).

See also

Graph Distance, Happy Edge Conjecture, Plane Graph, Spanning Tree

Explore with Wolfram|Alpha

References

Aichholzer, O.; Ballinger, B.; Biedl, T.; Damian, M.; Demaine, E. D.; Hesterberg, A.; Korman, M.; Lubiw, A.; Lynch, J.; Tkadlec, J.; and Uno, Y. "Reconfiguration of Non-Crossing Spanning Trees." J. Comput. Geom. 15, 224-253, 2024. https://doi.org/10.20382/jocg.v15i1a9.Aichholzer, O.; Dorfer, J.; Kramer, P.; Rieck, C.; and Vogtenhuber, B. "Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees." 3 Nov 2026. https://arxiv.org/abs/2611.05300.

Cite this as:

Weisstein, Eric W. "Plane Spanning Tree Flip Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PlaneSpanningTreeFlipGraph.html

Subject classifications