OP-00888 Open

Connectivity of plane spanning-path reconfiguration

Let $P \subset \mathbb{R}^2$ be a finite set of at least three points, no three collinear. The flip graph $\mathcal{F}(P)$ has as vertices the non-crossing straight-line Hamiltonian paths on $P$, viewed as undirected edge sets; two are adjacent if one is obtained from the other by deleting one edge and inserting one edge. Endpoints may change, and the deleted and inserted edges may cross each other. Akl, Islam and Meijer proved that $\mathcal{F}(P)$ is connected when $P$ is in convex position and when $|P| \le 8$. Aichholzer, Knorr, Mulzer, Obenaus, Paul and Vogtenhuber proved it for point sets with exactly one interior point and for generalized double circles, and Kleist, Kramer and Rieck for point sets with at most two convex layers.

Problem. Is $\mathcal{F}(P)$ connected for every such point set $P$?

Source: Akl, Islam and Meijer (2007), as a conjecture; see Aichholzer, Knorr, Mulzer, Obenaus, Paul and Vogtenhuber (2023), Conjecture 1.

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: MG
Keywords: AIM Open Applied Problems, flip graphs, plane spanning paths, reconfiguration

References

@article{akl2007,
  author  = {Akl, Selim G. and Islam, Md. Kamrul and Meijer, Henk},
  title   = {On planar path transformation},
  journal = {Inform. Process. Lett.},
  volume  = {104},
  number  = {2},
  year    = {2007},
  pages   = {59--64},
  doi     = {10.1016/j.ipl.2007.05.009},
}
@inproceedings{aichholzer2023,
  author        = {Aichholzer, Oswin and Knorr, Kristin and Mulzer, Wolfgang and Obenaus, Johannes and Paul, Rosna and Vogtenhuber, Birgit},
  title         = {Flipping plane spanning paths},
  booktitle     = {WALCOM: Algorithms and Computation},
  editor        = {Lin, Chun-Cheng and Lin, Bertrand M. T. and Liotta, Giuseppe},
  series        = {Lecture Notes in Comput. Sci.},
  volume        = {13973},
  publisher     = {Springer},
  address       = {Cham},
  year          = {2023},
  pages         = {49--60},
  doi           = {10.1007/978-3-031-27051-2_5},
  eprint        = {2202.10831},
  archivePrefix = {arXiv},
}
@inproceedings{kleist2025,
  author        = {Kleist, Linda and Kramer, Peter and Rieck, Christian},
  title         = {On the connectivity of the flip graph of plane spanning paths},
  booktitle     = {Graph-Theoretic Concepts in Computer Science (WG 2024)},
  editor        = {Kr{\'a}{\v{l}}, Daniel and Milani{\v{c}}, Martin},
  series        = {Lecture Notes in Comput. Sci.},
  volume        = {14760},
  publisher     = {Springer},
  address       = {Cham},
  year          = {2025},
  pages         = {327--342},
  doi           = {10.1007/978-3-031-75409-8_23},
  eprint        = {2407.03912},
  archivePrefix = {arXiv},
}
@misc{aim-plane-spanning-path-connectivity,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Connectivity of plane spanning-path reconfiguration}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/594-plane-spanning-path-connectivity.md},
  note         = {Entry 594 at commit 24edaad, 2026-10-15},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00888, "Connectivity of plane spanning-path reconfiguration", clopen.solutions.