Canadian Conference on Computational Geometry · 2007 · 11 citations · 4 references
Geometric Graph TheoryHexagonal Grid GraphEngineeringGraph TheoryAlgebraic Graph TheoryTopological Graph TheoryExtremal Graph TheoryPlanar GraphHexagonal Grid GraphsComputational ComplexityComputer ScienceDiscrete MathematicsCombinatorial OptimizationComputational GeometryHamilton CircuitHamilton Circuits
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