Can I read Using SAT to study plane Hamiltonian substructures in simple drawings on EtoBox?

Using SAT to study plane Hamiltonian substructures in simple drawings by Bergold, Helena; Felsner, Stefan; Reddy, Meghana M.; Scheucher, Manfred is a scholarly article available to read on EtoBox.

What is Using SAT to study plane Hamiltonian substructures in simple drawings about?

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 $(\log n)^{1-o(1)}$ and $\Omega(\sqrt{n})$, 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.

Author

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

Published

2023

Language

EN