On the Space Complexity of Directed Planar Reachability Problem

Talk by Vinodchandran N. Variyam

Work by Vinodchandran N. Variyam, Chris Bourke, and Raghunath Tewari.

Graph reachability problems are fundamental to the study of space bounded computations. Reachability problem for general directed graphs (given a directed graph G and two vertices s and t, is t reachable from s?) characterizes the complexity of computational problems solvable using non-deterministic machines with logarithmic space bound (complexity class NL). A recent breakthrough result due to Reingold implies that the reachability problem for undirected graphs captures all of deterministic logarithmic space bounded computations (complexity class L). Various restricted versions of reachability problem are known to characterize other small-space complexity classes.

In this talk we look at the space complexity of directed planar graph reachability problem. Planar graphs are an important and natural subclass of general graphs and are well studied in graph theory. However, the space complexity of reachability problem for directed planar graphs is not yet well understood. We make progress on this situation by giving a new upper bound that reachability for planar graphs can be decided in the complexity class UL, an unambiguous version of NL.