  A graph is hypohamiltonian if it is non-Hamiltonian, but the deletion of
every single vertex gives a Hamiltonian graph. Until now, the smallest known
planar hypohamiltonian graph had 40 vertices, a result due to Jooyandeh, McKay,
\"Osterg{\aa}rd, Pettersson, and Zamfirescu. That result is here improved upon
by two planar hypohamiltonian graphs on 34 vertices. We exploited a special
subgraph contained in two graphs of Jooyandeh et al., and modified it to
construct the two 34-vertex graphs and six planar hypohamiltonian graphs on 37
vertices. Each of the 34-vertex graphs has 26 cubic vertices, improving upon
the result of Jooyandeh et al. that planar hypohamiltonian graphs have 30 cubic
vertices. We use the 34-vertex graphs to construct hypohamiltonian graphs of
order 34 with crossing number 1, improving the best-known bound of 36 due to
Wiener. Whether there exists a planar hypohamiltonian graph on 41 vertices was
an open question. We settled this question by applying an operation introduced
by Thomassen to the 37-vertex graphs to obtain several planar hypohamiltonian
graphs on 41 vertices. The 25 planar hypohamiltonian graphs on 40 vertices of
Jooyandeh et al. have no nontrivial automorphisms. The result is here improved
upon by six planar hypohamiltonian graphs on 40 vertices with nontrivial
automorphisms.
