Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910042440073216 |
|---|---|
| author | Aichholzer, Oswin Dorfer, Joseph Kramer, Peter Rieck, Christian Vogtenhuber, Birgit |
| author_facet | Aichholzer, Oswin Dorfer, Joseph Kramer, Peter Rieck, Christian Vogtenhuber, Birgit |
| contents | We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding again a plane spanning tree. The flip distance between two trees is then the minimum number of flips needed to transform one tree into the other. We study structural properties of shortest flip sequences.
The folklore happy edge conjecture suggests that any edge shared by both the initial and target tree is never flipped in a shortest flip sequence. The more recent parking edge conjecture, which would have implied the happy edge conjecture, states that there exist shortest flip sequences which use only edges of the start and target tree, and edges in the convex hull of the point set. Finally, another conjecture that is implicit in the literature is the reparking conjecture which states that no edge is flipped more than twice. Essentially all recent flip algorithms respect these three conjectures and the properties they imply. We study cases in which the latter two conjectures hold and disprove them for the general setting.
(Shortened abstract due to arXiv restrictions.) |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05205 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees Aichholzer, Oswin Dorfer, Joseph Kramer, Peter Rieck, Christian Vogtenhuber, Birgit Computational Geometry Discrete Mathematics We study the reconfiguration of plane spanning trees on point sets in the plane in convex position, where a reconfiguration step (flip) replaces one edge with another, yielding again a plane spanning tree. The flip distance between two trees is then the minimum number of flips needed to transform one tree into the other. We study structural properties of shortest flip sequences. The folklore happy edge conjecture suggests that any edge shared by both the initial and target tree is never flipped in a shortest flip sequence. The more recent parking edge conjecture, which would have implied the happy edge conjecture, states that there exist shortest flip sequences which use only edges of the start and target tree, and edges in the convex hull of the point set. Finally, another conjecture that is implicit in the literature is the reparking conjecture which states that no edge is flipped more than twice. Essentially all recent flip algorithms respect these three conjectures and the properties they imply. We study cases in which the latter two conjectures hold and disprove them for the general setting. (Shortened abstract due to arXiv restrictions.) |
| title | Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2603.05205 |