The convex-drawing extension conjecture for plane Hamiltonian cycles
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.