Hamiltonian paths in L-shaped grid graphs

• The Hamiltonian path problem is a well-known NP-complete problem.
• We give necessary and sufficient conditions for the existence of a Hamiltonian (s,t)(s,t)-path in L-shaped grid graphs.
• We show that a Hamiltonian (s,t)(s,t)-path in L-shaped grid graph can be computed in linear time if it does exist.

Grid graphs are subgraphs of the infinite 2-dimensional integer grid. The Hamiltonian path problem for general grid graphs is a well-known NP-complete problem. In this paper, we present necessary and sufficient conditions for the existence of a Hamiltonian path between two given vertices in L-shaped grid graphs. We also show that a Hamiltonian path between two given vertices of a L-shaped grid graph can be computed in linear time.