__
Revision #1 to TR09-029 | 9th April 2009 00:00
__
#### Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

**Abstract:**
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.

__
TR09-029 | 3rd April 2009 00:00
__

#### Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

**Abstract:**
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.