An algorithm for finding Hamiltonian Cycles in Cubic Planar Graphs

2015/12/04 by Bohao Yao, Yao, Bohao, Charl Ras +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1512.01324

openalex publication_date 2015/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We first prove a one-to-one correspondence between finding Hamiltonian cycles in a cubic planar graphs and finding trees with specific properties in dual graphs. Using this information, we construct an exact algorithm for finding Hamiltonian cycles in cubic planar graphs. The worst case time complexity of our algorithm is O(2ⁿ).

Related

• On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs
• Hamiltonian cubic bipartite graphs
• Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
• Algorithmic proof of Barnette's Conjecture
• Hamiltonian cycles in some family of cubic 3-connected plane graphs