In this note we show that deciding the existence of a Hamiltonian cycle in a cubic plane graph is equivalent to the problem of the existence of an associated cubic plane multi-3-gonal graph with a Hamiltonian cycle which takes alternately left and right edges at each successive vertex, i.e\. it is also a Petrie cycle. The Petrie Hamiltonian cycle in an $n$-vertex plane cubic graph can be recognized by an $O(n)$-algorithm.
@article{118681,
author = {Jaroslav Ivan\v co and Stanislav Jendro\v l and Michal Tk\'a\v c},
title = {Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {35},
year = {1994},
pages = {413-417},
zbl = {0807.05044},
mrnumber = {1286589},
language = {en},
url = {http://dml.mathdoc.fr/item/118681}
}
Ivančo, Jaroslav; Jendroľ, Stanislav; Tkáč, Michal. Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 35 (1994) pp. 413-417. http://gdmltest.u-ga.fr/item/118681/
Regular Polytopes, MacMillan London (1948). (1948) | MR 0151873 | Zbl 0031.06502
Eulerian graphs and related topics, Part 1, Vol. 1, North-Holland Amsterdam (1990). (1990) | MR 1055084
The plane Hamiltonian problem is NP-complete, SIAM J. Comput. 5 (1968), 704-714. (1968) | MR 0444516
Convex Polytopes, Interscience New York (1967). (1967) | MR 0226496
The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Comb. Theory B 45 (1988), 305-319. (1988) | MR 0969251 | Zbl 0607.05051
Polytopal graphs, Selected topics in graph theory III L.W. Beineke and R.J. Wilson Academic Press London (1988), 169-188. (1988) | MR 1205401 | Zbl 0678.05015