  Whitney proved in 1931 that 4-connected planar triangulations are
Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured in 1979 that if $G$
is a 4-connected planar triangulation with $n$ vertices then $G$ contains at
least $2(n-2)(n-4)$ Hamiltonian cycles, with equality if and only if $G$ is a
double wheel. On the other hand, a recent result of Alahmadi, Aldred, and
Thomassen states that there are exponentially many Hamiltonian cycles in
5-connected planar triangulations. In this paper, we consider 4-connected
planar $n$-vertex triangulations $G$ that do not have too many separating
4-cycles or have minimum degree 5. We show that if $G$ has $O(n/{\log}_2 n)$
separating 4-cycles then $G$ has $\Omega(n^2)$ Hamiltonian cycles, and if
$\delta(G)\ge 5$ then $G$ has $2^{\Omega(n^{1/4})}$ Hamiltonian cycles. Both
results improve previous work. Moreover, the proofs involve a "double wheel"
structure, providing further evidence to the above conjecture.
