The reachability problem is to input a graph G and two
points, s and t, and determine whether a path exists from s to t in G.
Variants of the reachability problem are complete for a wide variety
of complexity classes. A grid graph is a graph embedded into
a rectangular mesh, and the restrictions of the reachability problem
to various forms of grid graphs provide a new set of problems whose
exact complexity is largely unknown. We will survey these problems,
some algorithms for them, and some non-trivial relationships among them.
Along the way we will outline the landscape of relevant complexity
classes (such as deterministic and nondeterministic logarithmic space,
and circuit classes such as NC1, TC0, and
AC0.
Last modified 16 September 2002