Abstract
There has been a great deal of progress in the fifteen years that have elapsed since Wigderson published his survey on the complexity of the graph connectivity problem [Wig92]. Most significantly, Reingold solved the longstanding question of the complexity of the s-t connectivity problem in undirected graphs, showing that this is complete for logspace (L) [Rei05].
This survey talk will focus on some of the remaining open questions dealing with graph reachability problems. Particular attention will be paid to these topics:
Reachability in planar directed graphs (and more generally, in graphs of low genus) [ADR05, BTV07].Reachability in different classes of grid graphs [ABC + 06].Reachability in mangroves [AL98].