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 K5-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 K3,3-free and K5-free directed graphs
and for computing longest paths
in K3,3-free and K5-free directed acyclic graphs.