Hamilton Paths in Grid Graphs

TLDR

A grid graph is a node‑induced finite subgraph of the infinite grid, and it is rectangular when its nodes form the product of two intervals. The study aims to determine necessary and sufficient conditions for a Hamilton path between two specified nodes in a rectangular grid graph. The authors derive these conditions analytically for rectangular grid graphs. They show that the Hamilton path and circuit problems for general grid graphs are NP‑complete, and use this result to provide a new, relatively simple proof that the Euclidean traveling salesman problem is NP‑complete.

Abstract

A grid graph is a node-induced finite subgraph of the infinite grid. It is rectangular if its set of nodes is the product of two intervals. Given a rectangular grid graph and two of its nodes, we give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes. In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete. This provides a new, relatively simple, proof of the result that the Euclidean traveling salesman problem is NP-complete.