All-pairs plane Hamiltonian path conjecture for simple drawings

Let KnK_n be drawn simply in the plane, and let a,ba,b be two vertices. A path is plane if no two of its edges cross. All-pairs Hamiltonian-path conjecture. For every simple drawing of KnK_n and every choice of two vertices a,ba,b, there is a plane Hamiltonian path from aa to bb. The conjecture is verified for n10n\leq 10 in simple drawings and for n13n\leq 13 in generalized twisted drawings, and is proved for several subclasses; the general case remains open.

Sources & referencesView supporting material

Primary source

Helena Bergold and Manfred Scheucher, “Investigating Simple Drawings of K_n using SAT”, arXiv:2504.02650 (2025).

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.