Two New Classes of Hamiltonian Graphs: (Extended Abstract)

We prove that a triangular grid without local cuts is (almost) always Hamiltonian. This suggests an efficient scheme for rendering triangulated manifolds by graphics hardware. We also show that the Hamiltonian Cycle problem is NP-Complete for planar subcubic graphs of arbitrarily high girth. As a by-product we prove that there exist tri-Hamiltonian planar subcubic graphs of arbitrarily high girth.