Title: The directed planar reachability problem

Abstract: 

We investigate the s-t reachability problem for directed planar
graphs, which is hard for L and contained in NL but not known to 
be complete. We show that this problem logspace-reduces to its
complement, and we also show that the problem of searching digraphs
in genus 1 (toroidal graphs) reduces to the planar case. 

We also consider a previously-studied class of planar graphs known
as grid graphs. We show that the directed planar s-t connectivity
problem (logspace-)reduces to the reachability problem for 
directed grid graphs. 

We also define a layered version of grid graphs and call it LGGR,
and we prove that reachability in such graphs is in the complexity
class UL. 

We also mention ongoing work about various classes of directed
planar graphs in which reachability can be done in Logspace.

This is joint work with Eric Allender and Samir Datta.