This work presents a log-space reduction which compresses an n-vertex directed acyclic graph with m(n) sources embedded on a surface of genus g(n), to a graph with O(m(n) + g(n)) vertices while preserving reachability between a given pair of vertices. Applying existing algorithms to this reduced graph yields new deterministic algorithms with improved space bounds as well as improved simultaneous timespace bounds for the reachability problem over a large class of directed acyclic graphs. Specifically, it significantly extends the class of surface-embedded graphs with log-space reachability algorithms: from planar graphs with O(log n) sources, to graphs with 2O(√log n)sources embedded on a surface of genus 2O(√log n). Additionally, it yields an O(n1-ϵ) space algorithm with polynomial running time for reachability over graphs with O(n1-ϵ) sources embedded on surfaces of genus O(n1-ϵ).

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. This paper focuses on the reachability problem over planar graphs where the complexity is unknown. Showing that the planar reachability problem is NL-complete would show that nondeterministic log-space computations can be made unambiguous. On the other hand, very little is known about classes of planar graphs that admit log-space algorithms. We present a new `source-based' structural decomposition method for planar DAGs. Based on this decomposition, we show that reachability for planar DAGs with m sources can be decided deterministically in O(m + log n) space. This leads to a log-space algorithm for reachability in planar DAGs with O(log n) sources. Our result drastically improves the class of planar graphs for which we know how to decide reachability in deterministic log-space. Specifically, the class extends from planar DAGs with at most two sources to at most O(log n) sources.