An algorithm for finding Hamiltonian Cycles in Cubic Planar Graphs
Bohao Yao, Charl Ras, Hamid Mokhtar · arXiv (Cornell University) · 2015
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^n)$.