A grid graph is a finite, node-induced subgraph of the two-dimensional integer
lattice. A solid grid graph is a grid graph in which every bounded face has
unit area. For arbitrary grid graphs, the hamiltonicity problem is known to be
NP-complete. We give a polynomial-time algorithm for solid grid graphs,
resolving a long-standing open question. In addition, our algorithm can be
used
to solve the minimum cycle cover problem for solid grid graphs. Both of these
results can be extended to a larger class of planar graphs known as quad-quad
graphs.
This information is available at
http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and
suggestions for speakers to Therese Biedl at
therese@cgm.cs.mcgill.ca.