{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:27:11Z","timestamp":1777645631863,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2022,12,27]]},"abstract":"<jats:p>In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2\u2013factor \ud835\udcac via (quasi) spanning trees of faces in G\/\ud835\udcac and study the algorithmic complexity of finding such (quasi) spanning trees of faces. Moreover, we show that if Barnette\u2019s Conjecture is false, then hamiltonicity in 3\u2013connected planar cubic bipartite graphs is an NP-complete problem.<\/jats:p>","DOI":"10.3233\/fi-222139","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T11:34:03Z","timestamp":1672140843000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Finding Hamiltonian Cycles in Barnette Graphs"],"prefix":"10.1177","volume":"188","author":[{"given":"Behrooz","family":"Bagheri Gh.","sequence":"first","affiliation":[{"name":"Algorithms and Complexity Group, Vienna University of Technology, Favoritenstrasse 9-11, 1040 Vienna, Austria."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomas","family":"Feder","sequence":"additional","affiliation":[{"name":"Computer Science Department, Stanford University, Stanford, California 94305, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herbert","family":"Fleischner","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, Vienna University of Technology, Favoritenstrasse 9-11, 1040 Vienna, Austria."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Subi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2022,12,27]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-222139","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-222139","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:32:48Z","timestamp":1777444368000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-222139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12,27]]}},"alternative-id":["10.3233\/FI-222139"],"URL":"https:\/\/doi.org\/10.3233\/fi-222139","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,27]]}}}