The convex-drawing extension conjecture for plane Hamiltonian cycles

About 3 years old · traced to

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 2n−32n-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 n≤10n\leq 10, 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

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.