Exact algorithms for the Hamiltonian cycle problem in planar graphs

We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs with worst case time complexity O(cn), where c   is some fixed constant that does not depend on the instance. Furthermore, we show that under the exponential time hypothesis, the time complexity cannot be improved to O(co(n)).