Hamilton Circuits in Hexagonal Grid Graphs
Kamrul Islam, Henk Meijer, Yurai Núñez Rodríguez, David D. Rappaport, Henry Xiao · Canadian Conference on Computational Geometry · 2007
We look at a variant of the Hamilton circuit problem, where the input is restricted to hexagonal grid graphs. A hexagonal grid graph has a vertex set that is a subset of the grid points of a regular hexagonal tiling of the plane and edges corresponding to hexagon sides. We show that Hamilton circuit in hexagonal grid graphs is NP-complete.