Hamiltonian (s, t)-paths in solid supergrid graphs.

The Hamiltonian path is a well-known NP-complete problem. This problem has been studied for solid supergrid graphs, in some special cases, and recently for 3-connected solid supergrid graphs. In this paper, we extend the previous result to general solid supergrid graphs, and present an O(n²)-time algorithm where n is the number of the vertices of the input graph. [ABSTRACT FROM AUTHOR]