Planar Strong Connectivity Helps in Parallel Depth-First Search.
This paper proves that for a strongly connected planar directed graph of size $n$, a depth-first search tree rooted at a specified vertex can be computed in $O(\log^{5}n)$ time with $n/\log{n}$ processors.  Previously, for planar directed graphs that may not be strongly connected, the best depth-first search algorithm runs in $O(\log^{10}n)$ time with $n$ processors.  Both algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory, and in case of a write conflict, permits an arbitrary processor to succeed.
Introduction
. Depth-first search is one of the most useful tools in graph
theory [32], [4]. The depth-first search problem is the following: given a graph and
a distinguished vertex, construct a tree that corresponds to performing depth-first
search in the graph starting from the given vertex.
The parallelization of depth-first search has been studied by numerous authors.
Reif showed that lexicographic depth-first search is P-complete even for general undirected
graphs [28]. For unordered depth-first search, Smith gave the first NC algorithm
for planar undirected graphs [30]. The processor complexity of his algorithm
was reduced to linear by He and Yesha [15]. Independently, Ja'Ja and Kosaraju [16]
and Shannon [29] also achieved the same result. Aggarwal and Anderson gave a randomized
NC algorithm for general undirected graphs [2]. Kao studied the problem for
directed graphs, and found an NC algorithm using n 4 processors for a planar directed
graph of size n [17]. This was followed by the randomized NC algorithm of Aggarwal,
Anderson and Kao for general directed graphs [3].
Recently, Kao and Klein gave an algorithm that computes depth-first search trees
in O(log 10 n) time using n processors for planar directed graphs that may not be
strongly connected [19].
This paper shows that for a strongly connected planar directed graph of size n,
a depth-first search tree rooted a specified vertex can be computed in O(log 5 n) time
using n= log n processors. This algorithm runs on a parallel random access machine
that allows concurrent reads and concurrent writes in its shared memory, and in case
of a write conflict, permits an arbitrary processor to succeed.
Both the algorithm of this paper and that of Kao and Klein use directed graph
separators defined by Kao [17], and follow the framework of the randomized NC
algorithm for general directed graphs [3]. The algorithm in this paper achieves a
superior complexity by exploiting topological properties of strongly connected planar
directed graphs. The strongly connected components of key subgraphs created in the
course of the algorithm have very regular structures. A major task of the algorithm
is to recursively maintain and utilize these structures.
This paper is organized as follows. Section 2 reviews basic definitions and relevant
facts about planar directed graphs.
Department of Computer Science, Duke University, Durham, NC 27706. Supported in part by
NSF Grant CCR-8909323.
Section 3 quotes previous results and reports new results on computing strongly
connected components and directed spanning trees.
Section 4 discusses directed graph separators. A more detailed discussion about
separations is given in the Appendix.
Section 5 details this paper's depth-first search algorithm for strongly connected
planar directed graphs.
2. Basics of planar directed graphs. A planar directed graph is one that can
be embedded on a plane such that the edges intersect only at common end vertices
or start vertices [14], [7], [33], [6]. An embedded planar directed graph is one with a
given planar embedding.
For subtle technical reasons, a planar graph in this paper may have multiple edges
but does not have loop edges.
2.1. Strong graphs. For brevity, a strongly connected embedded planar directed
graph with at least one vertex is simply called a strong graph.
The goal of this paper is to efficiently compute a depth-first search spanning tree
of a strong graph rooted at a specified vertex.
2.2. Faces, boundaries and orientations. Let G be a connected embedded
planar directed graph. If the vertices and edges of G are deleted from its embedding
plane, then the plane is divided into disconnected regions. Exactly one of the regions
is infinite; all others are finite. Each region is called a face of G. The infinite region
is called the external face; the finite regions are called the internal faces.
Let f be a face of G. The boundary of f , denoted by B(f), is the set of edges and
vertices surrounding f . If G contains at least two vertices, by its connectivity, B(f)
can be arranged into a unique undirected cycle by having an observer stay inside f
and walk around B(f) once. This cycle is called the boundary cycle of f . It may not
be edge-simple.
Let e be a boundary edge of f . The orientation of e with respect to f is defined
as follows:
ffl Case (1): f is the external face. The edge e is positive (or negative) with
respect to f if it points in the counterclockwise (resp., clockwise) direction
on the boundary cycle of f .
ffl Case (2): f is an internal face. The edge e is positive (or negative) with
respect to f if it points in the clockwise (resp., counterclockwise) direction
on the boundary cycle of f .
2.3. Holes, boundaries, and orientations. Let G be a connected embedded
planar directed graph. Let H be a connected subgraph of G. If the vertices and edges
of H are removed from the embedding plane of G, then the plane is divided into
disconnected regions. Exactly one of the regions is infinite; the others are all finite.
Each region is called a hole of H. The infinite region is called the external hole; the
finite regions are called the internal holes.
Let X be a hole of H. The boundary of X, denoted by B(X), is the set of vertices
and edges surrounding X. If H contains at least two vertices, by its connectivity,
B(X) can be arranged into a unique undirected cycle by having an observer stay
inside X and walk around B(X) exactly once. This cycle is called the boundary cycle
of X. It may not be edge-simple.
Let e be a boundary edge of X. The orientation of e with respect to X is defined
as follows:
ffl Case (1): X is the external hole of H. The edge e is positive (or negative) with
respect to X if it points in the counterclockwise (resp., clockwise) direction
on the boundary cycle of X.
ffl Case (2): X is an internal hole of H. The edge e is positive (or negative) with
respect to X if it points in the clockwise (resp., counterclockwise) direction
on the boundary cycle of X.
2.4. Combinatorial embeddings and data structures. Let G be a connected
planar directed graph. Algorithmically, a planar embedding of G is encoded
by the boundary of its external face and the clockwise cyclic order of the edges incident
with each vertex. Such an encoding is called a combinatorial planar embedding
of G. Topologically a planar embedding is uniquely specified by its corresponding
combinatorial embedding.
The cyclic edge incidence in a combinatorial embedding is further encoded by
the following data structure: for each vertex, there is a doubly linked circular list
consisting of the edges incident with that vertex in the clockwise order. These lists
can be used to efficiently trace the boundary cycles of the faces of G. They can also
be used to trace the boundary cycles of the holes of a connected subgraph.
Given a connected planar directed graph of size n, a combinatorial planar embedding
can be computed in O(logn) time using n log log n= log n processors on a
deterministic Arbitrary-CRCW PRAM [27].
2.5. Planar embeddings induced by vertex contraction. In this paper,
vertex contraction contracts only connected vertex subsets of a connected embedded
planar directed graph. This ensures that planarity is preserved.
For technical reasons, all multiple edges created by vertex contraction are kept
while all loop edges are deleted.
Let G be a connected embedded planar directed graph. Let H be the subgraph
induced by a connected vertex subset of G. Let G 0 be the graph constructed from G
by contracting H into a vertex H 0 . If H consists of at most one vertex, then G 0 and
G are the same. Otherwise a planar embedding for G 0 is specified as follows:
ffl For every vertex u 62 H, the clockwise cyclic order of the edges incident with
u is the same in G and G 0 .
ffl The edges around each nonempty hole X of H stay together around H 0 , and
their clockwise cyclic order around H 0 is the same as their cyclic order around
the boundary cycle of X in the negative direction of X.
ffl All uncontracted edges on the boundary of the external face of G remain on
that of G 0 , and have the same orientations with respect to both external faces.
ffl If H contains a boundary vertex of the external face of G, then H 0 is on the
boundary of the external face of G 0 .
In general such a planar embedding is not unique. Any planar embedding that fits
this construction is suitable for the purposes of this paper.
Lemma 2.1. Given a connected embedded planar directed graph of size n, a planar
embedding induced by contracting a disjoint family of connected vertex subsets can be
computed in O(log n) time using n= log n processors.
Remark: If vertex contraction is required to delete all multiple edges that it
creates, then computing an induced embedding may take more than linear space to
achieve O(log n) time on n= log n processors.
Proof. The edges around a new vertex of G 0 are collected by processing the
doubly linked circular lists of the combinatorial embedding of G. The computation
takes O(log n) time and n= log n processors, using optimal parallel algorithms for list
ranking [5], [9], [13], prefix computation [24], [23], tree contraction [26], [1], [8], [22],
[11], [10], and planar connectivity [12].
3. Strongly connected components and directed spanning trees. This
section quotes previous results and reports new results on computing strongly connected
components and directed spanning trees.
3.1. Directed spanning trees.
Theorem 3.1 (Kao and Shannon [20]). For a strong graph of size n, a
directed spanning tree rooted at a specified vertex can be computed in O(log 2 n) time
using n= log n processors on a deterministic Arbitrary-CRCW PRAM.
3.2. Compactness and strongly connected components. Let G be a connected
embedded planar directed graph. Let H 1 and H 2 be two nonempty connected
subgraphs of G. H 1 encloses H 2 if H 2 is in an internal hole of H 1 . A compact strongly
connected component of G is one that encloses no strongly connected component.
Theorem 3.2 (Kao [18]). Let G be a connected embedded planar directed graph.
Let n be the size of G. Let ff be the number of noncompact strongly connected components
in G. Then, the strongly connected components of G can be computed in
O(dlog using n= log n processors on a deterministic Arbitrary-
CRCW PRAM.
3.3. New results for computing strongly connected components. The
next three theorems discuss how to compute the strongly connected components of a
graph that is obtained by deleting or contracting a subgraph.
For an embedded planar directed graph that may not be connected, a strongly
connected component is compact if it is compact in the connected component that
contains it.
3.3.1. Deleting a vertex subset from a strong graph. Let G be a directed
graph. Let H be a subgraph or vertex subset of G. Let G \Gamma H be the subgraph
obtained by removing the vertices in H and their incident edges.
Theorem 3.3. Let G be a strong graph of size n. Let H be a subgraph of G.
be the number of connected components in H. Let ff 0 be
the number of noncompact strongly connected components of G 0 . Then the following
statements are true:
1. ff 0 - fl.
2. The strongly connected components of G 0 can be computed deterministically
in O(dlog 2 (fl using n= log n processors.
Proof. The first statement is obtained by counting arguments based on the following
facts:
ffl Let W be a noncompact strongly connected component of G 0 . By the planarity
and strong connectivity of G, at least one connected component of H
is enclosed by W in G.
ffl Let W 1 and W 2 be two noncompact strongly connected components of G 0 .
By the planarity of G, if some connected component of H is enclosed in G by
both W 1 and W 2 , then either W one encloses the other in G.
ffl Let W be a noncompact strongly connected component of G 0 . By the strong
connectivity and planarity of G, some connected component of H is enclosed
in G by W but not by any noncompact strongly connected component of G 0
that is itself enclosed by W in G.
To prove the second statement, first compute the connected components of G 0 .
This takes O(logn) time using n= log n processors [12]. Next compute the strongly
connected components of these connected components via Theorem 3.2. The second
statement then follows from the first statement of this theorem.
3.3.2. Deleting an edeg subset from a strong graph.
Theorem 3.4. Let G be a strong graph of size n. Let U be a vertex subset of G.
Let D be a subset of the edges in G incident with U . Let G 0 be the graph obtained
by deleting from G the edges in D. Let ! be the number of vertices in U . Let ff 0
be the number noncompact strongly connected components of G 0 . Then the following
statements are true:
1. ff 0 - 2!.
2. The strongly connected components of G 0 can be computed deterministically
in O(dlog 2 (2! using n= log n processors.
Proof. The second statement follows directly from the first statement and Theorem
3.2. Thus, it suffices to prove the first statement as follows.
Let W be a noncompact strongly connected component of G. A vertex is absorbed
by W in G if it either is a vertex in W or is enclosed by W in G. With this definition,
the first statement is obtained by counting arguments based on the following facts:
ffl Let W be a noncompact strongly connected component of G 0 . By the planarity
and strong connectivity of G, some u 2 U is absorbed by W in G.
ffl Let W 1 and W 2 be two noncompact strongly connected components of G 0 .
By the planarity of G, if some vertex u 2 U is absorbed by both W 1 and W 2
in G, then either W one encloses the other in G.
ffl Let W be a noncompact strongly connected component of G 0 . By the strong
connectivity and planarity of G, some vertex of U is absorbed in G by W and
at most one noncompact strongly connected of G 0 that is itself enclosed by
W in G.
3.3.3. Contracting connected vertex subsets in an acyclic graph.
Theorem 3.5. Let G be an acyclic connected embedded planar directed graph.
Let H be a subgraph of G. Let G 0 be the graph obtained from G by contracting each
connected component of H into a vertex. Let n be the size of G. Let fl be the number of
connected components in H. Let ff 0 be the number of noncompact strongly connected
components in G 0 . Then the following statements are true:
1. ff 0 - fl.
2. The strongly connected components of G 0 can be computed deterministically
in O(dlog 2 (fl using n= log n processors.
Proof. A noncompact strongly connected component contains at least two ver-
tices. Thus, by the acyclicity of G, each noncompact strongly connected component
of G 0 contains at least one contracted connected component of H. Therefore, the first
statement is true. The second statement then follows from Theorem 3.2.
4. Directed graph separators. Intuitively, a separator of a graph is a subgraph
whose removal disconnects the graph into small pieces.
4.1. Cycle separators and k-path separators. Most of the works on parallel
depth-first search rely on finding some form of graph separator. The algorithms for
planar undirected graphs employ undirected cycle separators [30], [15], [16]. The
algorithm for general undirected graphs uses path separators [2].
Procedure MergeTwoPaths
Input: a strong graph G, and a two-path separator
Output: a path separator S of G.
begin
1. Let s be the largest index such that some strongly connected component
Z s of G \Gamma (fu is heavy for G.
(Remark:
2. if s does not exist then return
3. Let P 0 be the path u
(Remark: P 0 and Q form a two-path separator.)
4. Let t be the smallest index such that some strongly connected component
Z t of G is heavy for G.
5. if t does not exist then return
6. Let Q 0 be the path v
(Remark: P 0 and Q 0 form a two-path separator.)
7. Compute a directed path R in Z s [ Z t from u s to v t .
(Remark: Z s [Z t is strongly connected.)
8. Let S be the directed path formed by P 0 , R, Q 0 .
(Remark: S is vertex-simple.)
9. return S.
end.
Fig. 1. A procedure for merging a two-path separator into a path separator.
The notion of a directed graph separator was originally introduced for depth-first
search in planar directed graphs [17]. It was then used for general directed graphs [3].
Here it is tailored for a strongly connected directed graph G:
ffl A vertex subset is called heavy for G if it contains more than two thirds of
the vertices in G.
ffl A separator of G is a set S of vertices such that no strongly connected component
in G \Gamma S is heavy for G.
ffl A cycle separator is a vertex-simple directed cycle whose vertices form a
separator. A single vertex is considered a cycle of length zero. Thus, if the
removal of a vertex separates a graph, the vertex is a cycle separator.
ffl For a positive integer k, a k-path separator is a set of k vertex-disjoint vertex-
simple directed paths whose vertices form a separator. A 1-path separator is
simply called a path separator.
Kao showed that every directed graph has a directed path separator and a directed
cycle separator [17]. These results are included in Appendix A. For a graph of size
n, his proofs yield a sequential algorithm that computes a path separator in optimal
O(n) time, and an algorithm that computes a cycle separator in O(n log n) time.
Aggarwal, Anderson, and Kao improved to O(n) the sequential time for computing
a directed cycle separator [3]. They also showed that computing cycle separators
and computing depth-first search trees are NC-equivalent.
4.2. Computing cycle separators for strong graphs.
Lemma 4.1. Given a strong graph of size n, a two-path separator can be computed
in O(log 2 n) time using n= log n processors.
Proof. Let T be a directed spanning tree of the given graph. By the work of
Lipton and Tarjan [25], there exist two vertices x and y such that the two tree paths
of T from the root to x and from the root to y form a separator.
A two-path separator is easily obtained from these tree paths. Kao, Teng, and
Toyama gave an algorithm [21] that computes x and y in O(log n) using n= log n
processors. Thus, this lemma follows from Theorem 3.1.
Lemma 4.2. Given a strong graph of size n, a path separator can be computed in
O(log 3 n) time using n= log n processors.
Proof. Let G be the given graph. First, use Lemma 4.1 to obtain a two-path
separator for G. Then, use the algorithm MergeTwoPaths in Fig. 1 to compute a
path separator. The proof for the correctness of MergeTwoPaths is similar to that of
Theorem A.2 in Appendix A.3.
As for the complexity, it suffices to show that MergeTwoPaths runs in O(log 3 n)
time using n= log n processors. Z s , Z t , s and t are computed by binary search and
Theorem 3.3 in O(log 3 n) time using n= log n processors. R 0 is obtained by computing
a divergent directed spanning tree rooted at u s in the subgraph induced by Z s [ Z t .
This uses Theorem 3.1 and takes O(log 2 n) time using n= log n processors. Thus, the
complexity of MergeTwoPaths is as stated.
Theorem 4.3. Given a strong graph of size n, a cycle separator can be computed
in O(log 3 n) time using n= log n processors.
Proof. The proof is similar to those of Lemma 4.2 and Theorem A.2.
5. Parallel depth-first search. Section 5.1 gives an overview of this paper's
algorithm for performing depth-first search in a strong graph. Sections 5.2 through
5.6 discuss key techniques used in the algorithm. Section 5.8 details the algorithm.
5.1. An overview. Let G be a strong graph. Let r be a vertex in G. The goal
is to construct a depth-first search spanning tree rooted at r for G. Such a tree will
be recursively constructed using cycle separators.
First, compute a cycle separator of G. Then, compute a path separator starting
from r by finding a directed path from r to the cycle separator. This path and
the cycle separator form a path separator S after an appropriate edge on the cycle
separator is removed. S will be a branch of the final depth-first search tree.
i.e., the remaining graph that is not searched by S. Suppose
that the search is continued in G 0 starting from a vertex r 0 that is the end vertex
of an edge pointing from the last vertex of S. This time the search recurses on the
subgraph B r 0 that consists of all the vertices reachable from r 0 via directed paths in
G 0 . The graph B r 0
is called a dangling subgraph. (See x5.5.)
Because S is a separator of G, every strongly connected component of G 0 contains
at most two thirds of the vertices in G. However, B r 0
may contain several such
strongly connected components. Consequently, B r 0
may still be too large for small
depth recursion. To avoid this problem, a set of directed paths is removed from G
such that the remaining directed graph has small dangling subgraphs. These removed
paths will form a subtree, called a partial depth-first search tree, in the final depth-first
search tree. (See x5.5.)
A dangling subgraph of a strong graph is a special kind of a graph called a bubble
graph. The structures of a bubble graph can be exploited to efficiently process the
dangling subgraphs. (See x5.2.)
A strong graph is in fact a special case of a bubble graph. The depth-first search
algorithm in this paper actually takes a bubble graph as input, and computes a depth-first
search tree by recusing on bubble subgraphs. (See x5.7.)
5.2. Bubble graphs. A strongly connected component of a directed graph is a
sink component if it has no outgoing edges to any other strongly connected component.
Let B be an embedded planar directed graph. B is called a bubble graph rooted
at a vertex r if the following conditions hold:
ffl Every vertex in B can be reached from r via directed paths.
ffl The vertex r is a boundary vertex of the external face of B, and every sink
component of B contains at least one boundary vertex of the external face.
Remark: It is assumed that a bubble graph has a specified root. For brevity, that
root is not explicitly mentioned unless there is a risk of ambiguity.
Lemma 5.1. Let B be a bubble graph rooted at r. Let n be the size of G. Then
the following statements are true:
1. The strongly connected components of B can be computed in O(log 2 n) time
using n= log n processors.
2. A directed spanning tree of B rooted at r can be computed in O(log 2 n) time
using n= log n processors.
Proof. The first statement follows from Theorem 3.2 and the fact that a bubble
graph has no noncompact strongly connected components.
The second statement is shown as follows. Let B 0 be the graph obtained from
B by adding a directed edge from each sink component of B to r via the external
face of B. Then, a directed spanning tree of B 0 rooted at r is also one for B. As
for the complexity, by the first statement of this lemma, B 0 can be computed in
O(log 2 n) time using n= log n processors. Because B 0 is a strong graph, a desired
directed spanning tree of B 0 can be computed via Theorem 3.2 in O(log 2 n) time
using n= log n processors.
5.3. Heavy bubble graphs and splitting components. Let k be an integer.
A bubble graph is called k-heavy (or k-light) if it has more than (resp., at
vertices.
Let B be a k-heavy bubble graph. Let W 1 and W 2 be two distinct strongly
connected components. W 2 is called a descendant component of W 1 if W 1 can reach
directed paths.
For a directed graph G and a vertex subset (or a vertex) H of G, let R(H;G) be
the set of vertices that can be reached from H via directed paths in G.
Let W be a strongly connected component of B. Let R(W;B) be the set of
vertices in B that can be reached from W via directed paths.
W is called a splitting component of B if R(W;B) consists of more than k vertices,
and no descendant component of W satisfies this condition.
The depth-first search algorithm of this paper will find a cycle separator of a
splitting component of B, and then use the separator to break B into bubble subgraphs
with smaller splitting components.
5.4. Computing a splitting component via s-t graphs. An acyclic embedded
planar directed graph is called an s-t graph if it has a unique source and a unique
sink, and they are on the boundary of its external face.
Theorem 5.2. Given a k-heavy bubble graph of size n, a splitting component can
be computed in O(log 2 n) time using n= log n processors.
Proof. Let B be a k-heavy bubble graph. A splitting component of B is computed
by converting B into an s-t graph as follows.
be the graph obtained by adding a vertex t in the external face of B
and a directed edge pointing to t from each sink component of B.
be the graph obtained from B 1 by contracting each strongly connected
component of B into a vertex. The vertices in B 2 are assigned weights. The
weight of t is 0. For each vertex w that is contracted from a strongly connected
component W of B, the weight of w is the number of vertices in W .
Note that B 2 is an s-t graph. Its sink is t, and its source is contracted from the
strongly connected component of B that contains its specified root.
By Lemmas 5.1(1) and 2.1, B 2 can be computed in O(log 2 n) time using n= log n
processors. Next, the cardinality of R(W;B) for each strongly connected component
W of B is computed in O(log 2 n) time on n= log n processors. This computation applies
to B 2 the descendant counting algorithm of Tamassia and Vitter for s-t graphs
[31]. With the cardinality of R(W;B) computed, a splitting component of B is identified
in a straightforward manner in O(logn) time using n= log n.
5.5. Partial depth-first search trees and dangling subgraphs. Let B be
a bubble graph. A partial depth-first search tree of B is a subtree of a depth-first
search tree of B such that both trees are rooted at the specified root of B.
Let T be a partial depth-first search tree of B. Let x be the vertices of
T listed in the post-order traversal sequence of depth-first search, i.e., in this sequence
x i is marked right after all its descendants in T are marked.
For each x i , let y
be the vertices that are not in T but are the end
vertices of the edges pointing from x i . The order of y
is arbitrary. This
is the post-order that will be used to search starting from x i . A y vertex may
have several different indices if it is adjacent from several x vertices.
The dangling subgraph of B, denoted by D(i; j), with respect to (i; and T is
the subgraph induced by the vertices in that can be reached from y i;j but not
from any y vertex before y i;j in the intended post-order traversal sequence of the y
vertices, i.e., D(i; j)g.
For each nonempty D(i; j), the directed edge from x i to y i;j is called the dangling
edge associated with D(i; j).
The next two lemmas provides a natural way of extending T into a complete
depth-first search tree by recursing on the nonempty dangling subgraphs in parallel.
Lemma 5.3. Let r be the specified root of B. Let H be a connected subgraph of
B that contains r. Let u be a vertex that is not in H but is adjacent with H. Then
the subgraph of B induced by R(u; bubble graph rooted at u.
Proof. Let B u be the subgraph of B induced by R(u; First, by the
definition of B u , the vertex u can reach every vertex in B u via directed paths in B u .
Next, because r is a boundary vertex of the external face of B, by the connectivity
of H and by the relationship of r, H, and u, the vertex u is a boundary vertex of the
external face of B u .
Let W be a sink component of B u . The following discussion shows that W
contains a boundary vertex of the external face of B u . Because B is a bubble graph,
contains a directed path s from W to a boundary vertex on the
external face of B. There are two cases based on whether Q intersects H or not.
ffl Case (1): Q does not intersect H. Then Q lies in B u . Because W is a sink
component of B u , the path Q lies in W . Therefore, W contains the last vertex
of Q, which is a boundary vertex on the external face of B u .
ffl Case (2): Q intersects H. Let y s be the first vertex of Q that is in H. Because
boundary vertex on the external face of B, by the adjacency of
H and y s\Gamma1 , the vertex y s\Gamma1 is a boundary vertex of the external face of B u .
Furthermore, because W is a sink component of B u , the vertex y s\Gamma1 is in W .
Lemma 5.4.
Let\Omega be the set of dangling subgraphs of B with respect to T . Let
L be the set of the associated dangling edges. Then the following statements are true:
1. Each nonempty D(i; j) is a bubble graph rooted at y i;j . Hence, y i;j is chosen
to be the specified root of D(i; j).
2. The dangling subgraphs are disjoint.
3. A depth-first search tree of B can be formed by T , L, and a depth-first search
tree for each dangling subgraph with at least two vertices.
Proof. The first statement is obtained by recursively applying Lemma 5.3. The
other two statements are straightforward.
5.6. Computing dangling subgraphs with respect to a path. This section
shows how to compute the dangling subgraphs with respect to a partial depth-first
search tree that is a path. The computation is based on two bisection strategies using
the subroutines in Fig. 2 and Fig. 3.
5.6.1. Analyzing the subroutine in Fig. 2. The next two lemmas analyze
the subroutine in Fig. 2.
Lemma 5.5. Let Y be the set of the end vertices of the edges in B that point from
Proof. The proof has two directions.
contains a directed
path Q 1 from P 1 to y. Note that Q 1 contains no edge from D. On the other hand,
because A 1 is strongly connected, there is a directed path Q 2 from y to P such that
intersect at only one vertex. Because Q 2 contains no outgoing edges from
, it has no edge from D. Let Q be the directed path formed by Q 1 and Q 2 . Because
Q goes from P to P , its becomes a directed cycle in A 2 that contains w. Because Q
contains no edge from D. it remains a directed cycle in A 3 . Therefore, y
contains a vertex-simple
directed path R 1 from w to z. Let R 2 be a directed path in A 1 that corresponds
to R 1 and intersects P only at one vertex x. Note that x is the start vertex of R 1 .
Because A 1 is constructed by adding incoming edges to r and because the edges in
are removed from A 3 , the vertex x is in P 1 and the edges of R 2 are in
Therefore, z 2 R(Y;
Lemma 5.6. Let B be a bubble graph of size n. Then the procedure in Fig. 2
correctly computes an output as specified in O(log 2 n) time using n= log n processors.
Proof. The second and the fourth output property of the procedure are straight-
forward. The other two properties are shown below.
is the subgraph of B induced by R(x
Therefore, by Lemma 5.3, B 1 is a bubble graph rooted at x q . Then, because
is obtained from a bubble graph by contracting a connected vertex subset,
it is a bubble graph rooted at x p .
ffl Property 3: By Lemma 5.5, the nonempty dangling subgraphs and the associated
dangling edges of B with respect to P are exactly those of B 1 with
respect to P 1 and those of with respect to P 2 . Because may
or may not be a bubble graph, B 1 is contracted instead of deleted. The contraction
of B 1 into x q+1 may add new edges in B 2 from
Procedure SubOneComputeDSG
Input: a bubble graph B rooted at r, and a vertex-simple directed path
2.
Output: two graphs B 1 and B 2 constructed from B, and two paths
are bubble graphs rooted at x dp=2e and x p , respectively.
2. P 1 and P 2 are vertex-simple directed paths, respectively, in B 1 and
starting from their specified roots.
3. The nonempty dangling subgraphs and the associated dangling
edges of B with respect to P are exactly those of B 1 with respect
to P 1 and those of B 2 with respect to P 2 .
4. The total size of B 1 and B 2 is at most the size of B.
begin
1. Let
2. Let P 1 be the subpath of P formed by x
3. Let P 2 be the subpath of P formed by x
4. Let D be the set of edges in B that point from P 2 to
5. if B is strongly connected
then let A
else let A 1 be the graph obtained from B by adding a directed
edge from each sink component to r via the external face of B.
6. Let A 2 be the graph obtained from A 1 by contracting P into a
vertex
(Remark: The edges in D are now outgoing edges of w.)
7. Let A 3 be the graph obtained from A 2 by deleting the edges in D.
8. Let W be the strongly connected component in A 3 that contains
the super vertex w.
9. Let B 1 be the subgraph of B induces by (W
be the graph obtained from B by contracting
into x q+1 .
end.
Fig. 2. The first subroutine for computing dangling subgraphs.
Procedure SubTwoComputeDSG
Input: a bubble graph B rooted at r with k - 2 edges outgoing from r.
Output: two graphs B 1 and B 2 constructed from B with the following
properties:
are bubble graphs rooted at r.
2. The nonempty dangling subgraphs and the associated dangling
edges of B with respect to r are exactly those of B 1 and B 2 with
respect to r, where r is considered as a path of a single vertex.
3. The outdegrees of r in B 1 and B 2 are at most dk=2e and bk=2c,
respectively.
4. The total size of B 1 and B 2 is at most the size of B.
begin
1. Let
2. Let y be the k end vertices of the outgoing edges of r in B.
3. Let D be the set of the edges from r to y in B.
4. if B is strongly connected
then let A
else let A 1 be the graph obtained from B by adding a directed
edge from each sink component to r via the external face of B.
5. Let A 2 be the graph obtained from A 1 by contracting
into a vertex w.
(Remark: The edges in D are now outgoing edges of w.)
6. Let A 3 be the graph obtained from A 2 by deleting the edges in D.
7. Let W be the strongly connected component in A 3 that contains
the super vertex w.
8. Let B 1 be the subgraph of B induces by (W \Gamma
without the edges in D.
9. Let B 2 be the graph obtained from B by contracting
into r.
end.
Fig. 3. The second subroutine for computing dangling subgraphs.
x q+1 . However, this contraction creates no new edges in B 2 from x q+1 to
Such edges would point from B 1 and thus their end vertices
would have been included in B 1 . Therefore, contracting B 1 into x q+1 does
not change the nonempty dangling subgraphs and the associated dangling
edges of with respect to P 2 .
As for the complexity, Steps 1 through 4 can be done in O(log n) time using
n= log n processors. Step 5 can be done via Lemma 5.1(1) in O(log 2 n) time using
n= log n processors. Step 6 is done via Lemma 2.1 in O(log n) time using n= log n
processors. Step 7 can be done in O(log n) time using n= log n processors. Because
A 1 is a strong graph, A 2 remains a strong graph. Because the edges of D are adjacent
to w in A 2 , by Theorem 3.4, W can be computed in O(log 2 n) time using n= log n
processors. Step 9 can be done in O(logn) time using n= log n processors. Step 10
can be done via Lemma 2.1 in O(logn) time using n= log n processors. Thus, the total
complexity of the procedure in Fig. 2 is as stated.
5.6.2. Analyzing the subroutine in Fig. 3. The next lemma analyzes the
subroutine in Fig. 3.
Lemma 5.7. Let B be a bubble graph of size n. Then the procedure in Fig. 3
correctly computes an output as specified in O(log 2 n) time using n= log n processors.
Proof. The proof is similar to those of Lemmas 5.6 and 5.3. A subtle point is
as follows. B 1 may contain some of y . The dangling subgraphs of B with
respect to such vertices are empty. Therefore, the edges in D can be deleted from B 1
without affecting its nonempty dangling subgraphs. This deletion ensures that the
outdegree of r in B 1 is dk=2e.
5.6.3. Computing dangling subgraphs. The next theorem uses the procedures
in Fig. 2 and Fig. 3 to compute the nonempty dangling subgraphs with respect
to a path.
Theorem 5.8. Let B be a bubble graph of size n. Let P be a vertex-simple directed
path of B starting from its specified root. Then the nonempty dangling subgraphs and
the associated dangling edges of B with respect to P can be computed in O(log 3 n)
time using n= log n processors.
Proof. The computation is divided into two phases as follows.
ffl The first phase iteratively applies SubOneComputeDSG to B and P to bisect
P . In O(logn) iterations, a collection of bubble subgraphs of B is obtained
such that each subgraph B 0 contains only one vertex of P .
ffl The second phase iteratively applies SubTwoComputeDSG to each B 0 to
bisect the outdegree of its root. In O(log n) iterations, a collection of even
smaller bubble subgraphs of B is obtained. Each subgraph B 00 is rooted at a
vertex y. The subgraph B 00 either has exactly one outgoing edge from y or
consists of only y. If B 00 consists of only y, then its corresponding dangling
subgraph of B is empty. Otherwise, B 00 \Gammafyg is a nonempty dangling subgraph
of B. Its associated dangling edge is the outgoing edge of y in B 00 .
The correctness and complexity of this computation follow directly from Lemmas 5.6
and 5.7.
5.7. Parallel depth-first search in bubble graphs. Fig. 6 details this paper's
algorithm for performing depth-first search in a bubble graph. Its subroutines are
described in Fig. 5 and Fig. 4.
Lemma 5.9. Let B be a bubble graph of size n. The procedure in Fig. 4 correctly
computes an output as specified in O(log 3 n) time using n= log n processors.
Procedure SplitHeavyDSG
Input: a positive integer m, and a 2m=3-heavy bubble graph B that has
at most m vertices.
Output:
1. a partial depth-first search tree S of B with either property below:
ffl no dangling subgraph of B with respect to S is 2m=3-heavy, or
ffl some dangling subgraph is 2m=3-heavy but each of its splitting
component consists of at most two thirds of the vertices from
the same splitting component of B;
2. the set \Delta of the dangling subgraphs of B with respect to
3. the set K of the associated dangling edges.
begin
1. Let r be the specified root of B.
2. Let W be a splitting component of B.
3. Let C be a directed cycle separator of W .
4. Let P be a vertex-simple directed path in B from r to C such that
P and C intersect at only one vertex u.
5. Let e be the edge on C pointing to u.
6. Let S be the vertex-simple directed path formed by P and C without
the edge e.
7. Let \Delta be the set of dangling subgraphs of B with respect to S.
8. Let K be the set of the associated dangling edges.
9. return the tuple (S; \Delta; K).
end.
Fig. 4. A procedure for splitting a heavy dangling subgraph
Procedure ComputePartialTree
Input: a bubble graph B with m vertices.
Output:
1. a partial depth-first search tree T of B such that all dangling sub-graphs
are 2m=3-light;
2. the
set\Omega of the dangling subgraphs of B with respect to T .
3. the set L of the associated dangling edges.
begin
1.
2. while some B 0
2\Omega is 2m=3-heavy do
begin
2-2. Delete the dangling edge of B 0 from L.
2-3. Add the above edge to T to form a larger tree.
2-4.
2-5. Add S to T to form a larger tree.
Add \Delta to \Omega\Gamma
2-7. Add K to L.
end.
3. return the tuple
end.
Fig. 5. A procedure for computing a partial depth-first search tree
Procedure ComputeDFSTree
Input: a bubble graph B with at least two vertices.
Output: a depth-first search tree T of B.
begin
1.
2. Add L to T to form a larger tree.
3. for each B 0
2\Omega with at least two vertices do
begin
3-1.
3-2. Add T 0 to T to form a larger tree.
end.
4. return T .
end.
Fig. 6. A procedure for computing a depth-first search tree
Proof. The correctness of the procedure is shown as follows. Let S 0 be the set of
the vertices in both S and W . Assume that some dangling subgraph B 0 of B with
respect to S is 2m=3-heavy. Because B has at most m vertices, B 0 is the only 2m=3-
heavy dangling subgraph of B with respect to S. Then, the splitting components of
are strongly connected components of W \Gamma S 0 . Because S 0 is a separator of W ,
the output property of the procedure holds.
The complexity of the procedure is analyzed as follows. Step 1 is obvious. Step
2 is done via Theorem 5.2. Step 3 is done via Theorem 4.3. Step 4 can be done using
Lemma 5.1(2). Steps 5 and 6 are obvious. Steps 7 and 8 are done via Theorem 5.8.
Thus, the total complexity is as stated.
Lemma 5.10. Let B be a bubble graph of size n. The procedure in Fig. 5 correctly
computes an output as specified in O(log 4 n) time using n= log n processors.
Proof. This lemma follows directly from Lemma 5.9 and the fact that by the
output property of SplitHeavyDSG, the number of iterations in ComputePartialTree
is O(logn).
Theorem 5.11. Let B be a bubble graph of size n. Let r be the specified root of
B. Then a depth-first search tree of B rooted at r can be computed in O(log 5 n) time
using n= log n processors on a deterministic Arbitrary-CRCW PRAM.
Proof. The computation is done by the procedure in Fig. 6. This theorem then
follows directly from Lemmas 5.4 and 5.10, and the fact that by the output property
of ComputePartialTree, the depth of recursion of ComputeDFSTree is O(log n).
5.8. Parallel depth-first search in strong graphs. The next theorem states
the main result of this paper.
Theorem 5.12. Let G be a strong graph of size n. Let r be a vertex in G. Then
a depth-first search spanning tree of G rooted at r can be computed in O(log 5 n) time
using n= log n processors on a deterministic Arbitrary-CRCW PRAM.
Proof. The external face of G can be changed so that r is a boundary vertex on
that face. Then, by the strong connectivity of G, it is a bubble graph rooted at r.
Therefore, this theorem follows from Theorem 5.11 and the fact that the external face
can be changed in O(logn) time on n= log n processors using list ranking [5], [9], [13]
and prefix computation [24], [23].

Acknowledgement

. The author wishes to thank Subhrajit Bhattacharya for
helpful discussions.
A. All graphs have cycle separators. The following discussion uses depth-first
search trees to compute graph separators [17].
A.1. Path and cycle separators of weighted graphs. A weighted graph is
one with non-negative vertex weights. To avoid triviality, assume that at least one
vertex has a positive weight.
Let G be a weighted directed graph. Let H be a subgraph or vertex subset of G.
H be the subgraph obtained by removing the vertices in H and their incident
edges.
Let W(H) be the total weight of H. The set H is called heavy for G if W(H) ?
W(G)=2. Remark: The threshold for heaviness here is different from that in x4.1,
which is 2=3.
A separator S of G is a vertex subset such that no strongly connected component
of G \Gamma S is heavy for G. A cycle (or path) separator is a vertex-simple directed cycle
(resp., path) such that its vertices form a separator.
For technical uniformity, a vertex is considered a trivial cycle. Thus, if a vertex
forms a separator, it is a cycle separator. The empty set is considered both a trivial
cycle and a trivial path. Thus, if the empty set forms a separator, it is a cycle
separator as well as a path separator.
A.2. Computing path separators from depth-first search trees. The next
theorem can be applied to a weighted undirected graph by substituting each undirected
edge with a pair of directed edges.
Theorem A.1. Every weighted directed graph has a path separator.
Proof. Let G be a weighted directed graph. Without loss of generality, assume
that G is strongly connected. Otherwise, replace G with its maximum-weight strongly
connected component. Every path separator of that component is also one for G.
A path separator P for G is constructed as follows. Let T be a depth-first search
spanning tree of G rooted at an arbitrary vertex r. Let z be the vertices
of G in the corresponding depth-first search postorder. Let p be the smallest index
with
Let P be the tree path in T from r to z p . Let g. Let
P is shown to be a path separator as follows. Draw G on a plane in such a way
that for all postorder indices i and j with i ? j, the vertex z i either is to the right of
z j or is an ancestor of z j in T [4].
The vertex z p either is an ancestor of or is to the right of every vertex in GL
because p is greater than the postorder indices of all vertices in GL . Also, every
vertex in GR is to the right of z p because the postorder indices of vertices in GR are
all greater than p and because P consists of z p and all its ancestors. Therefore, every
vertex in GR is to the right of every vertex in GL .
Because in depth-first search no edge points from left to right, every strongly
connected component of G \Gamma P is either entirely in GL or entirely in GR . Thus, the
weight of a strongly connected component of G \Gamma P is at most W(GL ) or W(GR ).
A.3. Computing cycle separators from path separators. The next theorem
can also be applied to a weighted undirected graph by edge substitution. Note
that a separator obtained by the theorem actually consists of either no vertex, or a single
vertex, or at least three vertices. Thus, it does not degenerate into an undirected
edge after edge substitution is undone.
Theorem A.2. Every weighted directed graph has a cycle separator.
Proof. Let G be a weighted directed graph. Let be a path separator
of G obtained by Theorem A.1.
P is converted into a cycle separator as follows. Let s be the largest index such
that some strongly connected component Z s of G \Gamma fu is heavy for G.
Then because the path u does not exist, then
the empty set is a trivial cycle separator. Otherwise, continue the conversion and let
Let t be the smallest index such that some strongly connected component Z t of
is heavy for G. Then u because the path u
separator.
There are two cases based on whether not. If t, then u s is a trivial
cycle separator. Otherwise, u t 62 Z s and u s 62 Z t . Because Z s and Z t are heavy for G
and are strongly connected, Z s " Z t contains a vertex z such that there is a vertex-
simple directed path Q from u s via Z s \Gamma Z t to z and then via Z t \Gamma Z s to u t . Because
contains none of u the path Q and the path u
vertex-simple directed cycle with at least three vertices. This cycle is a separator
because the path u is a separator.



--R

A simple tree contraction algorithm
A random NC algorithm for depth first search
Parallel depth-first search in general directed graphs
The Design and Analysis of Computer Algorithms
Deterministic parallel list ranking
New York

The accelerated centroid decomposition technique for optimal tree evaluation in logarithmic time

Optimal tree contraction in the EREW model
An optimal parallel algorithm for dynamic expression evaluation and its applications
Optimal parallel algorithms on planar graphs
An optimal linked list prefix algorithm on a local memory computer
Graph Theory
A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs
Parallel algorithms for planar graphs and related problems
All graphs have cycle separators and planar directed depth-first search is in DNC

Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

An O(n log n)-work NC algorithm for depth-first search in undirected planar graphs
Optimal parallel evaluation of tree-structured computations by raking
The power of parallel prefix
Parallel prefix computation
A separator theorem for planar graphs
Parallel tree contractions and its applications
An optimal parallel algorithm for graph planarity

A linear-processor algorithm for depth-first search in planar graphs
Parallel algorithms for depth first search I.
Parallel transitive closure and point location in planar struc- tures

Graph Theory
--TR
strong connectivity;depth-first search;s-t graphs;linear-processor NC algorithms;graph separators;planar directed graphs;bubblegraphs