Hamiltonian Cycles in Solid Grid Graphs

A grid graph is a finite node induced subgraph of the infinite two dimensional integer grid. A solid grid graph is a grid graph without holes. For general grid graphs, the Hamiltonian cycle problem is known to be NP complete. We give a polynomial time algorithm for the Hamiltonian cycle problem in solid grid graphs, resolving a longstanding open question posed by A. Itai et al. (1982). In fact, our algorithm can identify Hamiltonian cycles in quad quad graphs, a class of graphs that properly includes solid grid graphs.

Authors

• Chris Umans
• William J. Lenhart

Keywords

• Solids
• Strips
• Polynomials
• Computer science
• Merging
• Educational institutions
• Algorithm design and analysis
• Simple Cycle
• Hamiltonian Path
• Grid Graph
• Polynomial-time Algorithm
• Class Of Graphs
• Graph Problems
• Proof Of Theorem
• Cell Edge
• Bottom Edge
• Top Edge
• Light Patterns
• Input Graph
• Proof Sketch
• Dependency Graph
• Distance Formula
• Strip Length