Counterexamples show some edges must flip in plane spanning trees
Counterexamples to the Happy Edge Conjecture in Plane Spanning Trees
Computational Geometry
Summary
This paper looks at how to change one drawing of a connected network of points into another by swapping edges without crossings. A common belief was that edges shared by the start and end drawings would never need to be changed in the shortest path to transform one into the other. The authors found examples with 16 and 30 points that prove this belief false, showing that even shared edges might have to be flipped for an efficient change. This challenges previous assumptions in the study of these geometric networks.
What this means in practice
- •For graph drawing engineers: Avoid assuming shared edges are fixed when computing efficient transitions between plane spanning trees in visualization software.
- •For computational geometry developers: Refine algorithms for reconfiguring planar graphs by accounting for cases where common edges must be flipped in shortest sequences.
A theory result. No direct application yet.
Authors
Oswin Aichholzer, Joseph Dorfer, Peter Kramer, Christian Rieck, Birgit Vogtenhuber
Abstract
We study the problem of reconfiguring plane, straight-line spanning trees on point sets in the plane. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set $P$, the flip graph has a vertex for each plane spanning tree on $P$, and an edge between any two trees that differ by a single flip. The folklore happy edge conjecture suggests that any edge shared by both the initial and the target tree (a happy edge) is never flipped in a shortest flip sequence. This conjecture was computationally verified for up to 10 points in convex position. In this paper, we disprove this conjecture both on general point sets and on point sets in convex position by providing two counterexamples on $16$ and $30$ points, respectively. The counterexample for point sets in general position also holds for compatible flips, while the happy edge property holds for compatible flips in convex point sets as shown by Aichholzer, Dorfer, and Vogtenhuber [GD 2025].