Reachability in K_3,3-free Graphs and K₅-free Graphs is in Unambiguous Log-Space

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