Using SAT to study plane Hamiltonian substructures in simple drawings

MaRDI QIDQ6436823zbMATH OpenFDO

Authors Helena Bergold, Stefan Felsner, Meghana M. Reddy, Manfred Scheucher

Publication date 16 May 2023

Has companion code repository https://github.com/manfredscheucher/supplemental-rafla

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Discrete geometry (52Cxx)

Abstract: In 1988 Rafla conjectured that every simple drawing of a complete graph $K_n$ contains a plane, i.e., non-crossing, Hamiltonian cycle. The conjecture is far from being resolved. The lower bounds for plane paths and plane matchings have recently been raised to $(logn{)}^{1-o(1)}$ and $Omega(sqrtn)$, respectively. We develop a SAT framework which allows the study of simple drawings of $K_n$. Based on the computational data we conjecture that every simple drawing of $K_n$ contains a plane Hamiltonian subgraph with $2n-3$ edges. We prove this strengthening of Rafla's conjecture for convex drawings, a rich subclass of simple drawings. Our computer experiments also led to other new challenging conjectures regarding plane substructures in simple drawings of complete graphs.

This page was built for publication: Using SAT to study plane Hamiltonian substructures in simple drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436823)