The convex-drawing extension conjecture for plane Hamiltonian cycles

Let DD be a convex drawing of the complete graph KnK_n, and let CC be a plane Hamiltonian cycle in DD. A plane Hamiltonian subdrawing is a crossing-free subdrawing spanning all vertices.

Convex-drawing extension conjecture. Every plane Hamiltonian cycle CC in DD can be extended to a plane Hamiltonian subdrawing on 2n32n-3 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 n10n\leq 10, 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

Never refreshed

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.