Canadian Conference on Computational Geometry · 2007 · 11 citations · 4 references
ComputingComputer ScienceMathematicsAlgorithmsCircuit TheoryCombinatoricsCircuit ComplexityGraph AlgorithmsGraph TheoryCircuit Graph TheoryHamiltonian CircuitsTiling Problems
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.
4
Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter · SIAM Journal on Computing · 1982 · 515 citations · Full text
Hamiltonian cycles in solid grid graphs
Chris Umans, William Lenhart · 2002 · 87 citations