Not being (super)thin or solid is hard: A study of grid Hamiltonicity

We give a systematic study of Hamiltonicity of grids - the graphs induced by finite subsets of vertices of the tilings of the plane with congruent regular convex polygons (triangles, squares, or hexagons). Summarizing and extending existing classification of the usual, "square", grids, we give a comprehensive taxonomy of the grid graphs. For many classes of grid graphs we resolve the computational complexity of the Hamiltonian cycle problem. For graphs for which there exists a polynomial-time algorithm we give efficient algorithms to find a Hamiltonian cycle. We also establish, for any g≥6, a one-to-one correspondence between Hamiltonian cycles in planar bipartite maximum-degree-3 graphs and Hamiltonian cycles in the class ^Cg of girth-g planar maximum-degree-3 graphs. As applications of the correspondence, we show that for graphs in ^Cg the Hamiltonian cycle problem is NP-complete and that for any N≥5 there exist graphs in ^Cg that have exactly N Hamiltonian cycles. We also prove that for the graphs in ^Cg, a Chinese Postman tour gives a (1+8g)-approximation to TSP, improving thereby the Christofides ratio when g>16. We show further that, in any graph, the tour obtained by Christofides' algorithm is not longer than a Chinese Postman tour.