Hamiltonian paths in L-shaped grid graphs

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. (C) 2016 Elsevier E.V. All rights reserved.