We show that the reachability problem for directed graphs that are either K_{3,3}-free or K_5-free is in unambiguous log-space, UL \cap coUL. This significantly extends the result of Bourke, Tewari, and Vinodchandran that the reachability problem for directed planar graphs is in UL \cap coUL. Our algorithm decomposes the graphs into biconnected and triconnected components. This gives a tree structure on these components. The non-planar components are replaced by planar components that maintain the reachabilty properties. For K_5-free graphs we also need a decomposition into fourconnected components. A careful analysis finally gives a polynomial size planar graph which can be computed in log-space. We show the same upper bound for computing distances in K_{3,3}-free and K_5-free directed graphs and for computing longest paths in K_{3,3}-free and K_5-free directed acyclic graphs.

We show that the reachability problem for directed graphs
that are either K_{3,3}-free or K_5-free
is in unambiguous log-space, UL \cap coUL.
This significantly extends the result of Bourke, Tewari, and Vinodchandran
that the reachability problem for directed planar graphs
is in UL \cap coUL.

Our algorithm decomposes the graphs into biconnected and triconnected components.
This gives a tree structure on these components.
The non-planar components are replaced by planar components
that maintain the reachabilty properties.
For K_5-free graphs we also need a decomposition into fourconnected components.
A careful analysis finally gives a polynomial size planar graph which can be computed
in log-space.

We show the same upper bound for computing distances
in K_{3,3}-free and K_5-free directed graphs
and for computing longest paths
in K_{3,3}-free and K_5-free directed acyclic graphs.