The convex-drawing extension conjecture for plane Hamiltonian cycles
Let be a convex drawing of the complete graph , and let be a plane Hamiltonian cycle in . A plane Hamiltonian subdrawing is a crossing-free subdrawing spanning all vertices.
Convex-drawing extension conjecture. Every plane Hamiltonian cycle in can be extended to a plane Hamiltonian subdrawing on edges.
The conjecture asks whether every prescribed plane Hamiltonian cycle in a convex drawing can be enlarged to the target-size subdrawing. The paper reports that this holds computationally for convex drawings with , while the analogous assertion fails for general simple drawings.
References
Primary source
Helena Bergold, Stefan Felsner, Meghana M. Reddy and Manfred Scheucher, “Using SAT to study plane Hamiltonian substructures in simple drawings”, arXiv:2305.09432 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.