hide
Free keywords:
-
Abstract:
We show how to decompose efficiently in parallel
{\em any} graph into a number,
$\tilde{\gamma}$, of outerplanar subgraphs
(called {\em hammocks}) satisfying
certain separator properties. Our work combines and extends
the sequential hammock decomposition technique
introduced by G.~Frederickson and
the parallel ear decomposition
technique, thus we call it the {\em hammock-on-ears decomposition}.
We mention that hammock-on-ears
decomposition also draws from techniques in computational
geometry and that an embedding of the graph does not need to
be provided with the input. We achieve this decomposition
in $O(\log n\log\log n)$ time using $O(n+m)$ CREW PRAM
processors, for an $n$-vertex, $m$-edge graph or digraph.
The hammock-on-ears decomposition implies a general framework
for solving graph problems efficiently. Its value is
demonstrated by a variety of applications on a
significant class of (di)graphs, namely that of
{\em sparse (di)graphs}. This class consists of all (di)graphs
which have a $\tilde{\gamma}$ between $1$ and $\Theta(n)$,
and includes planar graphs and graphs with genus $o(n)$.
We improve previous bounds for certain instances of shortest paths
and related problems, in this class of graphs. These problems include
all pairs shortest paths, all pairs reachability,
