<p>This paper is more general than what you're asking for, but should lead you to some answers.  It's pretty accessible too:</p>

<p><a href="http://research.cs.queensu.ca/home/yurai/Publications/Hamilt%20of%20thin%20solid%20and%20hard%20grids.pdf" rel="nofollow">http://research.cs.queensu.ca/home/yurai/Publications/Hamilt%20of%20thin%20solid%20and%20hard%20grids.pdf</a></p>

<p>(Though looking at it now the primary reference I'd have suggested out of that would be the Umans and Lenhart paper...)</p>

CC BY-SA 3.0
2012-03-30T16:06:58.533Z
2012-03-30T16:06:58.533Z
SamM
<p>Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such paper is beyond my capability.</p>

CC BY-SA 3.0
2012-03-30T10:30:14.683Z
What problem do you want to solve on solid grid graphs ? Hamiltonian Cycle ?
Shiva Kintali
CC BY-SA 3.0
2012-03-30T11:47:38.907Z
Could you please edit the question (and the title)?
Jeffε
CC BY-SA 3.0
2012-03-30T16:28:51.293Z
What is “m by n solid grid graph”?  If it means the m×n grid graph with mn vertices, then it is straightforward to see that the Hamiltonian Cycle problem on such graphs is in P.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-30T20:00:09.017Z
even if it's beyond you to read the paper, doesn't the abstract answer your question? http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1997.646138
Sasho Nikolov
<ds.algorithms><graph-algorithms>
Polynomial time algorithm to solve the TSP on an m by n solid grid
Darryl
# Polynomial time algorithm to solve the TSP on an m by n solid grid

(Asked by: username_0 on 2012-03-30)

Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such paper is beyond my capability.

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: What problem do you want to solve on solid grid graphs ? Hamiltonian Cycle ?  
> **username_2**: Could you please edit the question (and the title)?  
> **username_3**: What is “m by n solid grid graph”?  If it means the m×n grid graph with mn vertices, then it is straightforward to see that the Hamiltonian Cycle problem on such graphs is in P.  
> **username_4**: even if it's beyond you to read the paper, doesn't the abstract answer your question? http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1997.646138  

---

## 1 answers

### Answer by username_5 on 2012-03-30. Score: 2

This paper is more general than what you're asking for, but should lead you to some answers. It's pretty accessible too:

<http://research.cs.queensu.ca/home/yurai/Publications/Hamilt%20of%20thin%20solid%20and%20hard%20grids.pdf>

(Though looking at it now the primary reference I'd have suggested out of that would be the Umans and Lenhart paper...)


---

