We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.
(1) A polynomial-time,
$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and $K_5$-free graphs, a polynomial-time, $O(n^{1/2+\epsilon})$-space algorithm, for every $\epsilon > 0$.

For the general directed reachability problem, the best known simultaneous time-space upper bound is the BBRS bound, due to Barnes, Buss, Ruzzo, and Schieber, which achieves a space bound of $O(n/2^{k\sqrt{\log n}})$ with polynomial running time, for any constant $k$. It is a significant open question to improve this bound for reachability over general directed graphs.
Our algorithms beat the BBRS bound for graphs embedded on surfaces of genus $n/2^{\omega(\sqrt{\log n})}$, and for all $H$-minor-free graphs. This significantly broadens the class of directed graphs for which the BBRS bound can be improved.