2026-07-20T06:22:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24992 2026-02-09T07:52:34Z ddc:004 open_access

Approximating Barnette’s Conjecture Bekos, Michael A. Kaufmann, Michael Pfister, Maximilian Barnette’s Conjecture Subhamiltonicity Book embeddings A well-known conjecture, named after David W. Barnette, asserts that every 3-regular, 3-connected, bipartite, planar graph (for short, Barnette graph) is Hamiltonian. As another step towards addressing Barnette’s conjecture positively, we show that every n-vertex Barnette graph admits a subhamiltonian cycle containing 5n/6 edges, improving upon the previous bound of 2n/3. Equivalently, every Barnette graph admits a 2-page book embedding in which at least 5n/6 consecutive vertex pairs along the spine are connected by edges. As a byproduct, we present a simple proof for a known result that guarantees the existence of Hamiltonian cycles in a certain subclass of Barnette graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael A. Bekos and Michael Kaufmann and Maximilian Pfister 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.6 urn:nbn:de:0030-drops-249927 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode