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.
['Kamrul Islam', 'Henk Meijer', 'Yurai Núñez Rodríguez', 'David Rappaport', 'Henry Xiao']
Hamilton Circuits in Hexagonal Grid Graphs