The NL vs. L problem in log-space computation is the reachability problem: given a directed graph $G$ and $s, t \in V(G)$, determine if there is a path from $s$ to $t$ in $G$. This problem is NL-complete, and its undirected analogue is L-complete.

Another important question is: what happens if we restrict to planar digraphs? It appears that restricting to acyclic planar digraphs is helpful, and then again restricting the number of sources: vertices with in-degree 0.

Theorem (Stolee, Bourke, Vinodchandran, 2010). There is a log-space algorithm to solve the reachability problem on planar digraphs with $O(\log n)$ sources.

We can naturally extend planar graphs to graphs embedded on surfaces of low genus.

Theorem (Stolee, Vinodchandran, 2012). Let $G$ be an acyclic digraph with $m$ sources embedded on a surface of genus $g$. There exists an algorithm to solve the reachability problem on $G$ using:

1. $O((\log(m+g))^2)$ space, or
2. $O(\frac{m+g}{2^{\sqrt{m+g}}})$ space and polynomial time.

One assumption in the above theorem is that the graphs must be given with their embeddings into low-genus surfaces (except planar graphs). A 2014 result of Elberfeld and Kawarabayashi demonstrates an algorithm to embed bounded-genus graphs on bounded-genus surfaces in log-space, making this unconditional for graphs with finite genus.

M. Elberfeld, K. Kawarabayashi, Embedding and canonizing graphs of bounded genus in logspace, STOC '14 (2014) pp. 383-392.

This work was supported by the NSF grants CCF-0430991 and CCF-0830730.