We obtain the following new simultaneous time-space upper bounds for the directed reachability problem. (1) A polynomial-time, O(n23g13) -space algorithm for directed graphs embedded on orientable surfaces of genus g. (2) A polynomial-time, O(n23) -space algorithm for all H -minor-free graphs given the tree decomposition, and (3) for K33-free and K5-free graphs, a polynomial-time, O(n12+) -space algorithm, for every 0">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(n2klogn) 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 n2(logn) , and for all H -minor-free graphs. This significantly broadens the class of directed graphs for which the BBRS bound can be improved.