Hamiltonian paths in grid graphs

I'm a non-mathematically inclined amateur whom is presently interested in Hamiltonian paths / Traveling Salesman problems.

I would like to request that someone be kind enough to tell me whether my understanding of the following sentence found in this research paper (http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf) is correct:

"In contrast, the Hamilton path (and circuit) problem for general grid graphs is shown to be NP-complete"

My understanding:

• A grid graph is this type of graph: http://mathworld.wolfram.com/images/eps-gif/GridGraph_701.gif
• NP-complete means if anyone can solve it, then a non general grid graph can be converted int o a general grid graph and be solved using the same algorithm.
• Traveling Salesman Problem is a Hamiltonian path (circuit)

1. Is the paper credible?
2. What does the 'general' in 'general grid graph' mean?
-

1. It means that there are some grid graphs for which there is some simple algorithm (or simply an existence/nonexistence proof), but this cannot be done for an arbitrary grid graph.

2.Traveling Salesman is not generally the same problem as hamiltonian path/circuit (usually there are costs involved).

1. The paper is written by some of the best people in the field, and published in the best journal in the field.

2. "General" means "arbitrary".

-
 May I further ask whether it is possible to convert a non grid graph TSP problem into a grid graph one? If so, what are the search terms I should google for to find the relevant research papers.. Thank you. – darryl Apr 29 2012 at 1:46 darryl: I think that the paper you mentioned in fact shows you how to convert a non grid graph TSP into a grid graph one if you read through the details. The paper might be a little difficult for you, but it is highly unlikely an easier source exists. – Alexander Woo Apr 29 2012 at 4:04 @Alexander... my bad. Thanks, though. Indeed it is a difficult paper for me to grasp but since it is proven that such a problem can be converted into another it has thus answered my question. – darryl Apr 29 2012 at 4:23