We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that on input $\langle G,u,v \rangle$ where $G\in {\cal G}(m,g)$ and $u$ and $v$ are two vertices of $G$, outputs $\langle G',u',v' \rangle$ where $G'$ is directed graph, and $u', v'$ are vertices of $G'$, so that (a) there is a directed path from $u$ to $v$ in $G$ if and only if there is a directed path from $u'$ to $v'$ in $G'$ and (b) $G'$ has $O(m+g)$ vertices.

By a direct application of Savitch's theorem on the reduced instance we
get a deterministic $O(\log n + \log^{2}(m+g))$-space algorithm for the reachability problem for graphs in ${\cal G}(m,g)$. By setting $m$ and $g$ to be $2^{O(\sqrt{\log n})}$ we get that the reachability problem for directed acyclic graphs with $2^{O(\sqrt{\log n})}$ sources embedded on surfaces of genus $2^{O(\sqrt{\log n})}$ is in $\L$ (deterministic logarithmic space). Earlier, in this direction, deterministic log-space algorithms were known only for planar directed acyclic graphs with $O(\log n)$ sources. Hence our result drastically improves the class of directed graphs for which we now know how to decide reachability in deterministic logarithmic space. By setting $m$ and $g$ to be $n^{o(1)}$ we get a deterministic algorithm for reachability for directed acyclic graphs embedded on surfaces with sub-polynomial genus and with sub-polynomial number of sources, that asymptotically beats Savitch's $O(\log^2 n)$ space bound.

Our reduction can also be combined with a simple depth-first search to achieve new simultaneous time-space upper bounds for reachability in a large class of directed acyclic graphs embedded on surfaces. In particular, for any $\epsilon < 1$, by performing a depth-first search on the reduced instance, we get a polynomial time algorithm for reachability over graphs in ${\cal G}(O(n^\epsilon),O(n^\epsilon))$ that uses $O(n^\epsilon)$ space. This beats the best upper bound of polynomial time and $O(n/2^{\sqrt{\log n}})$ space for this class of graphs known earlier.