On Finding Hamiltonian Cycles in Barnette Graphs

Article type: Research Article

Authors: Bagheri Gh., Behrooz^{a; *; †} | Feder, Tomas^b | Fleischner, Herbert^{c; *} | Subi, Carlos^d

Affiliations: [a] Algorithms and Complexity Group, Vienna University of Technology, Favoritenstrasse 9-11, 1040 Vienna, Austria. behrooz@ac.tuwien.ac.at | [b] Computer Science Department, Stanford University, Stanford, California 94305, USA. tomas@theory.stanford.edu | [c] Algorithms and Complexity Group, Vienna University of Technology, Favoritenstrasse 9-11, 1040 Vienna, Austria. fleischner@ac.tuwien.ac.at | [d] carlos.subi@hotmail.com

Correspondence: [†] Address for correspondence: Algorithms and Complexity Group, Vienna University of Technology, Favoritenstrasse 9-11, 1040 Vienna, Austria.

Note: [*] Research supported in part by FWF Project P27615-N25.

Abstract: In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2–factor 𝒬 via (quasi) spanning trees of faces in G/𝒬 and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette’s Conjecture is false, then hamiltonicity in 3–connected planar cubic bipartite graphs is an NP-complete problem.

Keywords: Barnette’s Conjecture, eulerian plane graph, hamiltonian cycle, spanning tree of faces, A–trail

DOI: 10.3233/FI-222139

Journal: Fundamenta Informaticae, vol. 188, no. 1, pp. 1-14, 2022