Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitchs algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can be solved by a deterministic algorithm in polynomial time and $O({\log}^2{n})$ space i.e., whether $NL \subseteq SC^2$. $RL$, which lies between $L$ and $NL$, is known be in $SC^2$. Hence reachability in directed graphs with polynomial mixing-time is in $SC^2$.I am looking for special cases of st-connectivity (that are not known to be in $L$) that have $SC^2$ algorithms. Is anything known about planar graphs, planar DAGs ? Note that st-connectivity in DAGs remains NL-complete.
SC^2 algorithms for st-connectivity
cc.complexity theory;space bounded
There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by Cook).  The first is $\text{RUL}$, for Reach-Unambiguous Log-space which has reachability in mangroves (graphs where every pair of vertices has at most one directed path between them) as a complete problem.  This class has been discussed before.The second is $\text{ReachFewL}$, which has reachability complete for graphs with at most a polynomial number of paths between any pair of vertices. Performing depth-first search on these graphs using a stack has a guarantee that it will take polynomial time, so these classes are in $\text{LogDCFL} \subseteq \text{SC}^2$.