The two-edge connectivity survivable-network design problem in
planar graphs

arXiv:1302.2184v2 [] 30 Sep 2015

Glencora Borradaile
Oregon State University

Philip Klein
Brown University

October 1, 2015

Abstract
Consider the following problem: given a graph with edge costs and a subset Q of vertices,
find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every
pair of vertices in Q. The problem is a failure-resilient analog of the Steiner tree problem
arising, for example, in telecommunications applications. We study a more general mixedconnectivity formulation, also employed in telecommunications optimization. Given a number
(or requirement) r(v) ∈ {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph
in which there are min{r(u), r(v)} edge-disjoint u-to-v paths for every pair u, v of vertices.
We address the problem in planar graphs, considering a popular relaxation in which the
solution is allowed to use multiple copies of the input-graph edges (paying separately for each
copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs.
We give the first polynomial-time approximation scheme in planar graphs. The running time is
O(n log n).
Under the additional restriction that the requirements are only non-zero for vertices on the
boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the
optimal solution.

1

Introduction

In the field of telecommunications network design, an important requirement of networks is resilience to link failures [24]. The goal of the survivable network problem is to find a graph that
provides multiple routes between pairs of terminals. In this work we address a problem concerning
edge-disjoint paths. For a set S of non-negative integers, an instance of the S-edge connectivity
design problem is a pair (G, r) where G = (V, E) is a undirected graph with edge costs c : V → <+
and connectivity requirements r : V → S. The goal is to find a minimum-cost subgraph of G that,
for each pair u, v of vertices, contains at least min{r(u), r(v)} edge-disjoint u-to-v paths.
In telecommunication-network design, failures are rare; for this reason, there has been much
research on low-connectivity network design problems, in which the maximum connectivity requirement is two. Resende and Pardalos [24] survey the literature, which includes heuristics, structural
results, polyhedral results, computational results using cutting planes, and approximation algorithms. This work focuses on {0, 1, 2}-edge connectivity problems in planar graphs.
We consider the previously studied variant wherein the solution subgraph is allowed to contain
multiple copies of each edge of the input graph (a multi-subgraph); the costs of the edges in the
solution are counted according to multiplicity. For {0, 1, 2}-connectivity, at most two copies of an
1

edge are needed. We call this the relaxed version of the problem and use the term strict to refer to
the version of the problem in which multiple copies of edges of the input graph are disallowed.
A polynomial-time approximation scheme (PTAS) for an optimization problem is an algorithm
that, given a fixed constant  > 0, runs in polynomial time and returns a solution within 1 +  of
optimal. The algorithm’s running time need not be polynomial in . The PTAS is efficient if the
running time is bounded by a polynomial whose degree is independent of . In this paper, we focus
on designing a PTAS for {0, 1, 2}-edge connectivity.
Two edge-connected spanning subgraphs A special case that has received much attention
is the problem of finding a minimum-cost subgraph of G in which every pair of vertices is two
edge-connected. Formally this is the strict {2}-edge connectivity design problem. This problem
is NP-hard [12] (even in planar graphs, by a reduction from Hamiltonian cycle) and max-SNP
hard [10] in general graphs. In general graphs, Frederickson and JáJá [13] gave an approximation
ratio of 3 which was later improved to 2 (and 1.5 for unit-cost graphs) by Khuller and Vishkin [17].
In planar graphs, Berger et al. [4] gave a polynomial-time approximation scheme (PTAS) for the
relaxed {1, 2}-edge connectivity design problem and Berger and Grigni [5] gave a PTAS for the strict
{2}-edge connectivity design problem. Neither of these algorithms is efficient; the degree of the
polynomial bounding the running time grows with 1/. For the relaxed version of spanning planar
2-edge connectivity, the techniques of Klein [19] can be used to obtain a linear-time approximation
scheme.
Beyond spanning When a vertex can be assigned a requirement of zero, edge-connectivity design
problems include the Steiner tree problem: given a graph with edge costs and given a subset of
vertices (called the terminals), find a minimum-cost connected subgraph that includes all vertices
in the subset. More generally, we refer to any vertex with a non-zero connectivity requirement
as a terminal. For {0, 2}-edge connectivity design problem, in general graphs, Ravi [23] showed
that Frederickson and JáJá’s approach could be generalized to give a 3-approximation algorithm
(in general graphs). Klein and Ravi [20] gave a 2-approximation for the {0, 1, 2}-edge connectivity
design problem. (In fact, they solve the even more general version in which requirements r(u, v)
are specified for pairs u, v of vertices.) This result was generalized to connectivity requirements
higher than two by Williamson et al. [27], Goemans et al. [14], and Jain [16]. These algorithms
each handle the strict version of the problem.
In their recent paper on the spanning case [5], Berger and Grigni raise the question of whether
there is a PTAS for the {0, 2}-edge connectivity design problem in planar graphs. In this paper,
we answer that question in the affirmative for the relaxed version. The question in the case of the
strict version is still open.

1.1

Summary of new results

Our main result is a PTAS for the relaxed {0, 1, 2}-edge connectivity problem in planar graphs:
Theorem 1.1. For any , there is an O(n log n) algorithm that, given a planar instance (G, r) of
relaxed {0, 1, 2}-edge connectivity, finds a solution whose cost is at most 1 +  times optimal.

2

This result builds on the work of Borradaile, Klein and Mathieu [7, 8, 9] which gives a PTAS for
the Steiner tree (i.e. {0, 1}-edge connectivity) problem. This is the first PTAS for a non-spanning
two-edge connectivity problem in planar graphs.
Additionally, we give an exact, polynomial-time algorithm for the special case where are the
vertices with non-zero requirement are on the boundary of a common face:
Theorem 1.2. There is an O(k 3 n)-time algorithm that finds an optimal solution to any planar
instance (G, r) of relaxed {0, 1, 2}-edge-connectivity in which only k vertices are assigned nonzero
requirements and all of them are on the boundary of a single face. For instances of relaxed {0, 2}edge connectivity (i.e. all requirements are 0 or 2), the algorithm runs in linear time.

1.2

Organization

We start by proving Theorem 1.2 in Section 3. The proof of this result is less involved and provides
a good warm-up for the proof of Theorem 1.1. The algorithm uses the linear-time shortest-path
algorithm for planar graphs [15] and a polynomial-time algorithm for the equivalent boundary
Steiner-tree problem [11] as black boxes.
In order to prove Theorem 1.1, we need to review the framework developed for the Steiner tree
problem in planar graphs. We give an overview of this framework in Section 4 and show how to use
it to solve the relaxed {0, 1, 2}-edge connectivity problem. The correctness of the PTAS relies on a
Structure Theorem (Theorem 4.6) which bounds the number of interactions of a solution between
different regions of the graph while paying only a small relative penalty in cost. We prove this
Structure Theorem in Section 5. The algorithm itself requires a dynamic program; we give the
details for this in Section 6.

2

Basics

We consider graphs and multi-subgraphs. A multi-subgraph is a subgraph where edges may be
included with multiplicity. In proving the Structure Theorem we will replace subgraphs of a solution
with other subgraphs. In doing so, two of the newly introduced subgraphs may share an edge.
For a subgraph H of a graph G, we use V (H) to denote the set of vertices in H. For a graph
G and set of edges E, G/E denotes the graph obtained by contracting the edges E.
For a path P , P [x, y] denotes the x-to-y subpath of P for vertices x and y of P ; end(P ) and
start(P ) denote the first and last vertices of P ; rev(P ) denotes the reverse of path P . For paths A
and B, A ◦ B denotes the concatenation of A and B. See Figure 1 for an illustration of the notion
of paths crossing. A cycle is non-self-crossing if every pair of subpaths of the cycle do not cross.
We employ the usual definitions of planar embedded graphs. For a face f , the cycle of edges
making up the boundary of f is denoted ∂f . We assume the planar graph G is connected and is
embedded in the plane, so there is a single infinite face, and we denote its boundary by ∂G.
For a cycle C in a planar embedded graph, C[x, y] denotes an x-to-y path in C for vertices x and
y of C. There are two such paths and the choice between the two possibilities will be disambiguated
by always choosing the subpath in the clockwise direction. A cycle C is said to enclose the faces
that are embedded inside it. C encloses an edge/vertex if the edge/vertex is embedded inside it or
on it. In the former case, C strictly encloses the edge/vertex. For non-crossing x-to-y paths P and
Q, P is said to be left of Q if P ◦ rev(Q) is a clockwise cycle.
We will use the following as a subroutine:
3

Q
y

P

P
Q

v

x

(a)

(b)

(c)

(d)

Figure 1: (a) P crosses Q. (b) P and Q are noncrossing; Q is left of P (c) A self-crossing cycle.
(d) A non-self-crossing cycle (non-self-crossing allows for repeated vertices, i.e. v.)
Theorem 2.1. Erickson, Monma and Veinott [11] Let G be a planar embedded graph with edgecosts and let Q be a set of k terminals that all lie on the boundary of a single face. Then there is
an algorithm to find an minimum-cost Steiner tree of G spanning Q in time O(nk 3 + (n log n)k 2 )
or O(nk 3 ) time using the algorithm of [15].

2.1

Edge-connectivity basics

Since we are only interested in connectivity up to and including two-edge connectivity, we define
the following: For a graph H and vertices x, y, let
cH (x, y) = min{2, maximum number of edge-disjoint x-to-y paths in H}.
For two multi-subgraphs H and H 0 of a common graph G and for a subset S of the vertices of G,
we say H 0 achieves the two-connectivity of H for S if cH 0 (x, y) ≥ cH (x, y) for every x, y ∈ S. We
say H 0 achieves the boundary two-connectivity of H if it achieves the two-connectivity of H for
S = V (∂G).
Several of the results in the paper build on observations of the structural property of two-edge
connected graphs. The first is a well-known property:
Lemma 2.2 (Transitivity). For any graph H, for vertices u, v, w ∈ V (H), cH (u, w) ≥ min{cH (u, v), cH (v, w)}
Note that in the following, we can replace “strictly encloses no/strictly enclosed” with “strictly
encloses all/strictly not enclosed” without loss of generality (by viewing a face enclosed by C as
the infinite face).
Lemma 2.3 (Empty Cycle). Let H be a (multi-)subgraph of G and let C be a non-self-crossing
cycle of H that strictly encloses no terminals. Let H 0 be the subgraph of H obtained by removing
the edges of H that are strictly enclosed by C. Then H 0 achieves the two-connectivity of H.
Proof. See Figure 2(b). Without loss of generality, view C as a clockwise cycle. Consider two
terminals x and y. We show that there are cH (x, y) edge-disjoint x-to-y paths in H that do not
use edges strictly enclosed by C. There are two nontrivial cases:
cH (x, y) = 1 : Let P be an x-to-y path in H. If P intersects C, let xP be the first vertex of P that
is in C and let yP be the last vertex of P that is in C. Let P 0 = P [x, xP ] ◦ C[xP , yP ] ◦ P [yP , y].
If P does not intersect C, let P 0 = P . P 0 is an x-to-y path in H that has no edge strictly
enclosed by C.
4

cH (x, y) = 2 : Let P and Q be edge-disjoint x-to-y paths in H. If Q does not intersect C, then P 0
and Q are edge-disjoint paths, neither of which has an edge strictly enclosed by C (where P 0
is as defined above). Suppose that both P and Q intersect C. Define xQ and yQ as for P .
Suppose these vertices are ordered xP , xQ , yQ , yP around C. Then P [x, xP ] ◦ C[xP , yQ ] ◦
Q[yQ , y] and Q[x, xQ ] ◦ rev(C[yP , xQ ]) ◦ P [yP , y] are edge disjoint x-to-y paths that do not use
any edges enclosed by C. This case is illustrated in Figure 2; other cases (for other orderings
of {xP , xQ , yQ , yP } along C) follow similarly.

y

yQ
yP
P

xP
C

x

Q

xQ

Figure 2: An illustration of the proof of Lemma 2.3: there are edge-disjoint x-to-y paths (grey)
that do not use edges enclosed by C.
We have shown that we can achieve the boundary two-connectivity of H without using any edges
strictly enclosed by a cycle of H. The lemma follows.

2.2

Vertex-connectivity basics

The observations in this section do not involve planarity. Although our results are for edge connectivity, we use vertex connectivity in Section 5 to simplify our proofs.
Vertices x and y are biconnected (a.k.a. two-vertex-connected) in a graph H if H contains two
x-to-y paths that do not share any internal vertices, or, equivalently, if there is a simple cycle in H
that contains both x and y. For a subset S of vertices of H, we say H is S-biconnected if for every
pair x, y of vertices of S, H contains a simple cycle through x and y. We refer to the vertices of S
as terminals.
Lemma 2.4. A minimal S-biconnected graph is biconnected.
Proof. Suppose H has a cut-vertex v: H = H1 ∪ H2 where H1 ∩ H2 = {v} and Hi 6= {v} for
i = 1, 2. If H1 and H2 both have terminals then H does not biconnect every pair of terminals. If,
say, H2 does not have a terminal then H − (H2 − {v}) is a smaller subgraph that biconnects the
terminals.
For the next two proofs, we use the notion of an (open) ear decomposition. An ear decomposition
of a graph G is a partition of the edges
S into a cycle C and a sequence of paths P1 , P2 , . . . , Pk such
that the endpoints of Pi are in C ∪ ( j<i Pj ). The ear decomposition is open if the endpoints of Pi
are distinct. A graph is biconnected iff it has an open ear decomposition [25]. Ear decompositions
can be built greedily starting with any cycle.
Theorem 2.5. Let H be a minimal S-biconnected graph. Every cycle in H contains a vertex of S.
5

Proof. Assume for a contradiction that H contains a cycle C that does not contain any terminals.
By Lemma 2.4, H is biconnected and so has an open ear decomposition starting with C; let
C, P1 , P2 , . . . , Pk be an open
S ear decomposition of H. Define Ei to be the subgraph composed of C
and the first i ears: C ∪ ( j≤i Pj ). We construct another open ear decomposition with
S one fewer
0
0
0
0
0
0
ear C , P2 , . . . , Pk of H as follows (note there is no ear P1 ) and use Ei to denote C ∪ ( j≤i Pj0 ).
Let x and y be the endpoints of P1 . Let C 0 = C[y, x] ◦ P1 . Let Q01 = C[x, y] be the portion of
C that is not used in C 0 . We will maintain the invariant:
Q0i contains at least one edge and Q0i = Ei − Ei0
Clearly this invariant holds for i = 1. For i ≥ 2, we define Pi0 using Pi and Q0i−1 . Note that
0
one or more of the endpoints of Pi may be in Q0i−1 and so Ei−1
∪ Pi is not necessarily a valid
0 , allowing us to
ear decomposition. However, by the invariant, Pi ’s endpoints are in Q0i−1 ∪ Ei−1
0
0
0
define a new valid ear Pi by extending Pi along Qi−1 to reach Ei−1 as follows: Pi0 is the minimal
0
0
path of Pi ∪ Q0i−1 ∪ Ei−1
whose endpoints are in Ei−1
such that Pi is a subpath of Pi0 . Define
Q0i = Q0i−1 − (Pi0 − Pi ). Since Pi has distinct endpoints, Pi0 does not contain all the edges of Q0i−1 ,
thus maintaining the invariant.
By construction, C 0 , P20 , . . . , Pk0 is an open ear decomposition of H − Q0k and so H − Q0k is
biconnected. Since Q0k ⊂ C and C does not contain any terminals, H − Q0k is S-biconnected and
since Q0k contains at least one edge, H − Q0k contradicts the minimality of H.
Theorem 2.6. Let H be a minimal S-biconnected graph. For any cycle C in H, every C-to-C
path contains a vertex of S.
Proof. Let C be any cycle. By Theorem 2.5, C contains a terminal. We consider an ear decomposition C, P1 , P2 , . . . of H built as follows. Consider s ∈ S not spanned by C ∪ P1 ∪ · · · ∪ Pi−1 .
Then there are vertex-disjoint paths from s to C ∪ P1 ∪ · · · ∪ Pi−1 since s and the terminal on, for
example, C are biconnected. Let Pi be the ear formed by these vertex-disjoint paths. Observe that
by this construction each ear Pi contains a terminal for every i.
Suppose every path in ∪i≤k Pi with two endpoints in C strictly contains a vertex of S. We prove
that this is then the case for ∪i≤k+1 Pi . Since Pk+1 is an ear, its endpoints are in ∪i≤k Pi and so
any C-to-C path that uses an edge of Pk+1 would have to contain the entirety of Pk+1 ; therefore
Pk+1 cannot introduce a terminal-free path.

3

An exact algorithm for boundary {0, 1, 2}-edge connectivity

Our algorithm for the boundary case of {0, 1, 2}-edge connectivity, as formalized in Theorem 1.2
is based on the observation that there is an optimal solution to the problem that is the union of
Steiner trees whose terminals are boundary vertices, allowing us to employ the boundary-Steinertree algorithm of Theorem 2.1.
When terminals are restricted to the boundary of the graph, no cycle can strictly enclose a
terminal. By Lemma 2.3, we get:
Corollary 3.1. Let H be a subgraph of G and let H 0 be a minimal subgraph of H that achieves the
boundary two-connectivity of H. Then in H 0 every cycle C strictly encloses no edges.

6

In the following we will assume that the boundary of the graph G is a simple cycle; that is,
a vertex appears at most once along ∂G. Let us see why this is a safe assumption. Suppose the
boundary of G is not simple: there is a vertex v that appears at least twice along ∂G. Partition
G into two graphs G1 and G2 such that G1 ∩ G2 = v, v appears exactly once along ∂G1 and
E(∂G) = E(∂G1 ) ∪ E(∂G2 ). Let x be a vertex of ∂G1 and let y be a vertex of ∂G2 . Then
cG (x, y) = min{cG1 (x, v), cG2 (v, y)}, allowing us to define new connectivity requirements and solve
the problem separately for G1 and G2 .
Lemma 3.2. Let P and Q be leftmost non-self-crossing xP -to-yP and xQ -to-yQ paths, respectively,
where xP , yP , xQ , and yQ are vertices in clockwise order on ∂G. Then P does not cross Q.
Proof. For a contradiction, assume that Q crosses P . Refer to Figure 3(a). Let C (interior shaded)
be the cycle P ◦ rev(∂G[xP , yP ]). C strictly encloses neither xQ nor yQ . If Q crosses P , there must
be a subpath of Q enclosed by C. Let x be the first vertex of Q in P and let y be the last. There
are two cases:
x ∈ P [y, yP ] : Refer to Figure 3(a). In this case, rev(P [y, x]) is left of Q[x, y] and so Q[xQ , x] ◦
rev(P [y, x]) ◦ Q[y, yQ ] (grey path) is left of Q, contradicting the leftmostness of Q.
x ∈ P [xP , y] : Refer to Figure 3(b). In this case, Q[xQ , x] ◦ rev(P [xP , x]) ◦ ∂G[xP , xQ ] (shaded
interior) is a cycle that strictly encloses y and does not enclose yQ . Since y is the last vertex
of Q on P , Q must cross itself, a contradiction.

yQ

Q
y

P

yQ

xP

P
Q

y

x
xQ

xP

x

xQ

yP
(a)

yP
(b)

Figure 3: Illustration of Lemma 3.2: there exist leftmost paths that do not cross.
Lemma 3.3. Let H be a subgraph of G. Let S be a subset of V (∂G) such that, for every x, y ∈ S,
cH (x, y) = 2. Then there is a non-self-crossing cycle C in H such that S ⊆ V (C) and the order
that C visits the vertices in S is the same as their order along ∂G.
Proof. Assume that the vertices of S are in the clockwise order s0 , s1 , . . . , sk−1 along ∂G.
Let Pi be the leftmost non-self-crossing si−1 -to-si path in H, taking the indices modulo k. Let
C = P1 ◦ P2 ◦ · · · ◦ Pk−1 . Certainly C visits each of the vertices s0 , s1 , . . . in order. By Lemma 3.2,
Pi does not cross Pj for all i 6= j. Therefore, C is non-self-crossing, proving the lemma.

7

We now give an algorithm for the following problem: given a planar graph G with edge
costs and an assignment r of requirements such that r(v) > 0 only for vertices v of ∂G, find a
minimum-cost multi-subgraph H of G that satisfies the requirements (i.e. such that there are at
least min{r(x), r(y)} edge-disjoint x-to-y paths in H).
Boundary2EC(G, r)
1.
2.
3.
4.

Let q1 , q2 , . . . be the cyclic ordering of vertices {v ∈ V (∂G) : r(v) = 2}.
For i = 1, . . ., let Xi = {qi } ∪ {v ∈ V (∂G[qi , qi+1 ]) : r(v) = 1} ∪ {qi+1 }.
For i = 1, . . ., let Ti be the minimum-cost Steiner tree spanning Xi .
Return the disjoint union ∪i Ti .

We show that Boundary2EC correctly finds the minimum-cost multi-subgraph of G satisfying
the requirements. Let OPT denote an optimal solution. By Lemma 3.3, OPT contains a non-selfcrossing cycle C that visits q1 , q2 , . . . (as defined in Boundary2EC). By Corollary 3.1, C strictly
encloses no edges of OPT. Let Pi be the leftmost qi -to-qi+1 path in C. The vertices in Xi are
connected in OPT, by the input requirements. Let Si be the subgraph of OPT that connects
Xi . This subgraph is enclosed by ∂G[qi , qi+1 ] ◦ C[qi , qi+1 ]. Replacing Si by Ti achieves the same
connectivity among vertices v with r(v) > 0 without increasing the cost.
We will use the following lemma to give an efficient implementation of Boundary2EC.
Lemma 3.4. Let a, b and c be vertices ordered along the clockwise boundary ∂G of a planar graph
G. Let Ta be the shortest-path tree rooted at a (using edge costs for lengths). Then for any set of
terminals Q in ∂G[b, c], there is a minimum-cost Steiner tree connecting them that enclosed by the
cycle ∂G[b, c] ◦ Ta [c, b].
Proof. Refer to Figure 4. Let C = ∂G[b, c] ◦ Ta [c, b]. Let T be a minimum-cost Steiner tree in G
connecting Q. Suppose some part of T is not enclosed by C. Let T 0 be a maximal subtree of T
not enclosed by C. The leaves of T 0 are on Ta [c, b]. Let P be the minimum subpath of Ta [b, c] that
spans these leaves. Let P 0 be the start(P )-to-end(P ) path in T 0 . See Figure 4.
We consider the case when start(P 0 ) is a vertex of Ta [a, b] and end(P 0 ) is a vertex of Ta [a, c]
(the other cases, when start(P 0 ) and end(P 0 ) are either both vertices of Ta [a, b] or both vertices
of Tb [a, c], are simpler). Then P 0 must cross Ta [a, x] where x is the last vertex common to Ta [a, b]
and Ta [a, c] (i.e. the lowest common ancestor in Ta of b and c). Let y be a vertex of P 0 ∩ Ta [a, x].
Since Ta is a shortest-path tree in an undirected path, every subpath of Ta [a, z] and Ta [z, a], for
any vertex z, is a shortest path. We have that:
c(P 0 ) = c(P 0 [start(P 0 ), y]) + c(P 0 [y, end(P 0 )])
≥ c(Ta [start(P 0 ), y]) + c(Ta [y, end(P 0 )])
≥ c(Ta [start(P 0 ), end(P 0 )])
≥ c(P )
Let Tb = T − T 0 ∪ P . By construction, Tb spans Q. Using that c(P 0 ) ≥ c(P ), we have that
c(Tb) = c(T ) − c(T 0 ) + c(P ) ≤ c(T ) − c(T 0 ) + c(P 0 ) ≤ c(T ) since P 0 is a subpath of T 0 .
Repeating this process for every subtree of T not enclosed by C results in a tree enclosed by C
spanning Q that is no longer than T .
8

Figure 4: There is a tree Tb that is just as cheap as T (dotted) and spans the terminals between b
and c but is enclosed by C (whose interior is shaded). Tb is composed of the portion of T enclosed
by C plus P , the thick grey path.
We describe an O(k 3 n)-time implementation of Boundary2EC (where k is the number of
terminals). Compute a shortest-path tree T rooted at terminal q1 in linear time. For each i,
consider the graph Gi enclosed by Ci = ∂G[qi , qi+1 ] ◦ T [qi+1 , qi ]. Compute the minimum Steiner
tree spanning Xi in Gi . By Lemma 3.4, Ti has the same cost as the minimum spanning tree
spanning Xi in G. Since each edge of G appears in at most two subgraphs Gi and Gj , the trees Ti
can be computed in O(k 3 n) time (by Theorem 2.1).
Note: if the requirements are such that r(v) ∈ {0, 2} for every vertex v on the boundary of G,
then the sets Xi have cardinality 2. Instead of computing Steiner trees in Step 3, we need only
compute shortest paths. The running time for this special case is therefore linear.
This completes the proof of Theorem 1.2.

4

A PTAS framework for connectivity problems in planar graphs

In this section, we review the approach used in [9] to give a PTAS framework for the Steiner
tree problem in planar graphs. While the contents of this section are largely a summary of the
framework, we generalize where necessary for the survivable network design problem, but refer the
reader to the original paper [9] for proofs and construction details that are not unique to the focus
of this article.
Herein, denote the set of terminals by Q. OPT denotes an optimal solution to the survivable
network design problem. We overload this notation to also represent the cost of the optimal solution.

4.1

Mortar graph and bricks

The framework relies on an algorithm for finding a subgraph MG of G, called the mortar graph [9].
The mortar graph spans Q and has total cost no more than 9−1 times the cost of a minimum
Steiner tree in G spanning Q (Lemma 6.9 of [9]). Since a solution to the survivable network
problem necessarily spans Q, the mortar graph has cost at most
9−1 · OPT.

(1)

The algorithm for computing MG first computes a 2-approximate Steiner tree [21, 26, 28] and then
augments this subgraph with short paths. The resulting graph is a grid-like subgraph (the bold
edges in Figure 5(a)) many of whose subpaths are -short:
9

Definition 4.1. A path P in a graph G is -short if for every pair of vertices x and y on P ,
distP (x, y) ≤ (1 + )distG (x, y).
That is, the distance from x to y along P is at most (1 + ) times the distance from x to y in G.
For each face f of the mortar graph, the subgraph of G enclosed by that face (including the
edges and vertices of the face boundary) is called a brick (Figure 5(b)), and the brick’s boundary
is defined to be f . The boundary of a brick B is written ∂B. The interior of B is defined to be
the subgraph of edges of B not belonging to ∂B. The interior of B is written int(B).
Bricks satisfy the following:
Lemma 4.2 (Lemma 6.10 [9]). The boundary of a brick B, in counterclockwise order, is the
concatenation of four paths WB , SB , EB , NB (west, south, east, north) such that:
1. The set of edges B − ∂B is nonempty.
2. Every vertex of Q ∩ B is in NB or in SB .
3. NB is 0-short in B, and every proper subpath of SB is -short in B.
4. There exists a number t ≤ κ() and vertices s0 , s1 , s2 , . . . , st ordered from west to east along
SB such that, for any vertex x of SB [si , si+1 ), the distance from x to si along SB is less than
 times the distance from x to NB in B: distSB (x, si ) <  distB (x, NB ).
The number κ() is given by:
κ() = 42 (1 + 1 )

(2)

The mortar graph has some additional properties. Let B1 be a brick, and suppose B1 ’s eastern
boundary EB1 contains at least one edge. Then there is another brick B2 whose western boundary
WB2 exactly coincides with EB1 . Similarly, if B2 is a brick whose western boundary contains at least
one edge then there is a brick B1 whose eastern boundary coincides with B2 ’s western boundary.
The paths forming eastern and western boundaries of bricks are called supercolumns.
Lemma 4.3 (Lemma 6.6 [9]). The sum of the costs of the edges in supercolumns is at most  OPT.
The mortar graph and the bricks are building blocks of the structural properties required for
designing an approximation scheme. Borradaile, Klein and Mathieu demonstrated that there is
a near-optimal Steiner tree whose interaction with the mortar graph is “simple” [9]. We prove a
similar theorem in Section 5. In order to formalize the notion of “simple”, we select a subset of
vertices on the boundary of each brick, called portals, and define a portal-connected graph.

4.2

Portals and simple connections

We define a subset of θ evenly spaced vertices along the boundary of every brick. The value of θ
depends polynomially on the precision  and on α, a parameter that represents how complex the
solution can be within a single brick (α will be defined precisely in Equation (6))
θ() is O(−2 α())
The portals are selected to satisfy the following:
10

(3)

Lemma 4.4 (Lemma 7.1 [9]). For any vertex x on ∂B, there is a portal y such that the cost of the
x-to-y subpath of ∂B is at most 1/θ times the cost of ∂B.
Recall that, for each face f of the mortar graph M G, there is a corresponding brick B, and
that B includes the vertices and edges comprising the boundary of f . The next graph construction
starts with the disjoint union of the mortar graph M G with all the bricks. Each edge e of the
mortar graph is represented by three edges in the disjoint union: one in M G (the mortar-graph
copy of e) and one on each of two brick boundaries (the brick copies of e). Similarly, each vertex
on the boundary of a brick occurs several times in the disjoint union.
The portal-connected graph, denoted B + (M G), is obtained from the disjoint union as follows: a
copy of each brick B of M G is embedded in the interior of the corresponding face of M G, and each
portal p of B is connected by an artificial edge to the corresponding vertex of M G. The construction
is illustrated in Figure 5(c). The artificial edges are called portal edges, and are assigned zero cost.
Noting that each vertex v on the boundary of a brick occurs several times in B + (M G), we
identify the original vertex v of G with that duplicate in B + (M G) that belongs to M G. In particular, each terminal (vertex in Q) is considered to appear exactly once in B + (M G), namely in M G.
Thus the original instance gives rise to an instance in B + (M G): the goal is to compute the optimal
solution w.r.t. the terminals on M G in B + (M G) and then map the edges of this solution to G.
Since G can be obtained from B + (M G) by contracting portal edges and identifying all duplicates
of each edge and all duplicates of each vertex, we infer:
Lemma 4.5. Let H be a subgraph of B + (M G) that, for each pair of terminals u, v, contains at
least min{r(u), r(v)} edge-disjoint u-to-v paths. Then the subgraph of G consisting of edges of H
that are in G has the same property.
The graph B ÷ (M G), which we call the brick-contracted graph, is obtained by contracting each
brick in B + (M G) to a single vertex, called a brick vertex, as illustrated in Figure 5(d). This graph
will be used in designing the dynamic program in Section 6.

4.3

Structure Theorem

Lemma 4.5 implies that, to find an approximately optimal solution in G, it suffices to find a solution
in B + (M G) whose cost is not much more than the cost of the optimal solution in G. The following
theorem, which we prove in Section 5, suggests that this goal is achievable. An equivalent theorem
was proven for the Steiner tree problem [9].
Theorem 4.6 (Structure Theorem). For any  > 0 and any planar instance (G, r) of the {0, 1, 2}edge connectivity problem, there exists a feasible solution S to the corresponding instance (B + (M G), r)
such that
• the cost of S is at most (1 + c)OPT where c is an absolute constant, and
• the intersection of S with any brick B is the union of a set of non-crossing trees whose leaves
are portals.

4.4

Approximation scheme

We assume that the input graph G has degree at most three. This can be achieved using a wellknown embedding-preserving transformation in which each vertex of degree d > 3 is replaced with
11

(a)

(b)

(c)

(d)

Figure 5: (a) The mortar graph in bold, (b) the set of bricks, (c) the portal-connected graph
B + (M G), and (d) the brick-contracted graph B ÷ (M G).
a cycle of d degree-three vertices, as shown in Figure 6. Making this assumption simplifies the
dynamic program using for Step 5 below.
The approximation scheme consists of the following steps.
Step 1: Find the mortar graph MG.
Step 2: Decompose MG into “parcels”, subgraphs with the following properties:
(a) The parcels partition the faces of MG. Since each edge of MG belongs to the boundaries
of exactly two faces, it follows that each edge belongs to at most two parcels.
(b) The cost of all boundary edges (those edges belonging to two parcels) is at most
1

η c(MG). We choose η so that this bound is 2 c(OP T ):
η = η() = d20−2 e

(4)

(c) The planar dual of each parcel has a spanning tree of depth at most η + 1.
Each parcel P corresponds to a subgraph of G, namely the subgraph consisting of the bricks
corresponding to the faces making up P . Let us refer to this subgraph as the filled-in version
of P .
Step 3: Select a set of “artificial” terminals on the boundaries of parcels to achieve the following:

12

Figure 6: Each vertex of degree greater than 3 is replaced with a cycle of degree-three vertices
• for each filled-in parcel, there is a solution that is feasible with respect to original and
artificial terminals whose cost is at most that of the parcel’s boundary plus the cost
of the intersection of OPT with the filled-in parcel, and
• the union over all parcels of such feasible solutions is a feasible solution for the original
graph.
Step 4: Designate portals on the boundary of each brick.
Step 5: For each filled-in parcel P , find a optimal solution in the portal-connected graph, B + (P ).
Output the union of these solutions.
Step 1 can be carried out in O(n log n) time [9]. Step 2 can be done in linear time via breadthfirst search in the planar dual of MG, and then applying a “shifting” technique in the tradition of
Baker [1]. Step 3 uses the fact that each parcel’s boundary consists of edge-disjoint, noncrossing
cycles. If such a cycle separates terminals, a vertex v on the cycle is designated an artificial terminal.
We set r(v) = 2 if the cycle separates terminals with requirement 2 and r(v) = 1 otherwise. Under
this condition, any feasible solution for the original graph must cross the cycle; by adding the
edges of the cycle, we get a feasible solution that also spans the artificial terminal. Step 3 can be
trivially implemented in linear time. Step 5 is achieved in linear time using dynamic programming
(Section 6).

5

Proof of the Structure Theorem

We are now ready to prove the Structure Theorem for {0, 1, 2}-edge connectivity, Theorem 4.6. In
order to formalize the notion of connectivity across the boundary of a brick, we use the following
definition:
Definition 5.1 (Joining vertex). Let H be a subgraph of G and P be a subpath of ∂G. A joining
vertex of H with P is a vertex of P that is the endpoint of an edge of H − P .
We will use the following structural lemmas in simplifying OPT. The first two were used in
proving a Structure Theorem for the Steiner tree PTAS [9]; in these, T is a tree and P is an
-short path on the boundary of the graph in which T and P are embedded. The third is in fact a
generalization of the second lemma that we require for maintaining two connectivity.

13

Lemma 5.2 (Simplifying a tree with one root, Lemma 10.4 [9]). Let r be a vertex of T . There is
another tree Tb that spans r and the vertices of T ∩ P such that c(Tb) ≤ (1 + 4 · )c(T ) and Tb has at
most 11 · −1.45 joining vertices with P .
Lemma 5.3 (Simplifying a tree with two roots, Lemma 10.6 [9]). Let p and q be two vertices of T .
There is another tree Tb that spans p and q and the vertices of T ∩ P such that c(Tb) ≤ (1 + c1 )c(T )
and Tb has at most c2 · −2.5 joining vertices with P , where c1 and c2 are constants.
Lemma 5.4. Let F be a set of non-crossing trees whose leaves are vertices of -short boundary
paths P and Q and such that each tree in the forest has leaves on both these paths. There is a cycle
b a set Fb of trees, and a mapping φ : F −→ Fb ∪ {C}
b with the following properties
or empty set C,
• For every tree T in F, φ(T ) spans T ’s leaves.
b for at least one of i = 1, 2 then φ(T1 ) and φ(T2 )
• For two trees T1 and T2 in F , if φ(Ti ) 6= C
are edge-disjoint (taking into account edge multiplicities).
S
b has o(−2.5 ) joining vertices with P ∪ Q.
• The subgraph Fb ∪ {C}
b + P{c(T ) : T ∈ F}
b ≤ 3c(Q) + (1 + d · ) P{c(T ) : T ∈ F} where d is an absolute
• c(C)
constant.
Proof. View the embedding of the boundary such that P is on top and Q is at the bottom. Let
T1 , . . . , Tk be the trees of F ordered according the order of their leaves from left to right.
There are two cases.
b Let a be
Case 1) k > 1/. In this case, we reduce the number of trees by incorporating a cycle C.
the smallest index such that c(Ta ) ≤ c(F ) and let b be the largest index such that c(Tb ) ≤ c(F ).
We will replace
Let Q0 be the minimal subpath of Q that spans
Sb trees Ta , Ta+1 , . . . , Tb with a cycle.
0
the leaves of i=a Ti on Q. We likewise define P . Let L be the leftmost Q-to-P path in Ta and let
R be the rightmost Q-to-P path in Tb . Since P is -short,
c(P 0 ) ≤ (1 + )c(L ∪ Q0 ∪ R).

(5)

b = P 0 ∪ L ∪ Q0 ∪ R and set
To obtain Fb from F , we replace the trees Ta , . . . , Tb with the cycle C
b
b
b
φ(Ta ), . . . , φ(Tb ) to C. By construction C spans the leaves of ∪i=a Ti .
Case 2) k ≤ 1/. In this case, the number of trees is already bounded. We set a = 2, b = 1 so
b to be the empty set.
as to not eliminate any trees, and we set C
In both cases, for each remaining tree Ti (i 6= a, a + 1, . . . , b) we do the following. Let Ti0 be a
minimal subtree of Ti that spans all the leaves of Ti on P and exactly one vertex r of Q. Let Qi be
the minimal subpath of Q that spans the leaves of Ti on Q. We replace Ti with the tree Tbi that is
the union of Q0i and the tree guaranteed by Lemma 5.2 for tree Ti0 with root r and -short path P .
By construction Tbi spans the leaves of Ti . We set φ(Ti ) = Tbi for i 6= a, . . . , b.
b has at most four joining vertices with P ∪ Q. Each tree Tbi has one joining vertex with Q and,
C
by Lemma 5.2, o(−1.5 ) joining vertices with P . By the choice of a and b, there are at most 2/ of
the trees in the second part of the construction. This yields the bound on joining vertices.

14

The total cost of the replacement cycle is:
b ≤ c(P 0 ) + c(L) + c(Q0 ) + c(R)
c(C)
≤ (2 + )(c(L) + c(Q0 ) + c(R))

by Equation (5)

0

≤ (2 + )(c(Ta ) + c(Q ) + c(Tb ))
0

≤ (2 + )(2c(F ) + c(Q ))

since L and R are paths in Ta and Tb

by the choice of a and b
0

2

≤ (4 + 2 )c(F ) + (2 + )c(Q )
The total cost of the replacement trees is:
X
X
c(Tbi ) ≤
c(Q0i ) + (1 + 4)c(Ti0 )
i=1,...,a−1,b+1...k

by Lemma 5.2

i=1,...,a−1,b+1...k

≤

X

c(Q0i ) + (1 + 4)c(Ti )

since Ti0 is a subtree of Ti

i=1,...,a−1,b+1...k

By the ordering of the trees and the fact that they are non-crossing, Q0 and the Q0i ’s are disjoint.
Combining the above gives the bound on cost.

5.1

Construction of a new solution

We start with a brief overview of the steps used to prove the structure theorem. We start with
an edge multiset forming an optimal solution, OPT. Each step modifies either the input graph G
or a subgraph thereof while simultaneously modifies the solution. The graphs and edge multisets
resulting from these steps are denoted by subscripts. Details are given in subsequent sections.
Augment We add two copies of each supercolumn, obtaining GA and OPTA . We consider the
two copies to be interior to the two adjacent bricks. This step allows us, in the restructure
step, to concern ourselves only with connectivity between the north and south boundaries of
a brick.
Cleave Cleaving a vertex refers to splitting it into two vertices and adding an artificial edge between
the two vertices. In the cleave step, we modify GA (and so in turn modify M GA and OPTA )
to create GC (and M GC and OPTC ) by cleaving certain vertices while maintaining a planar
embedding. Let JC be the set of artificial edges introduced. Note that XC /JC = XA . The
artificial edges are assigned zero cost so the metric between vertices is preserved. The artificial
edges are added to the solution, possibly in multiplicity, so connectivity is preserved.
Flatten In this step, for each brick B, we consider the intersection of the solution with int(B); we
replace some of the connected components of the intersection with subpaths of the boundary
of B. We denote the resulting solution by OPTF .
Map We map the edges of OPTF to B + (M G) creating OPTM . This step temporarily disconnects
the solution.
Restructure In this step, we modify the solution OPTM . For each brick B in M GC , the part of
OPTM strictly interior to B is replaced with another subgraph that has few joining vertices
with ∂B. We denote the resulting solution by OPTS .
15

Rejoin In order to re-establish connections broken in the Map step, we add edges to OPTS . Next,
we contract the artificial edges added in the cleave step. We denote the resulting solution by
[
OP
T.
Note that the solutions OPT, OPTA , and so on are multisets; an edge can occur more than
once. We now describe these steps in greater detail.
5.1.1

Augment

Recall that a supercolumn is the eastern boundary of one brick and the western boundary of
another, and that the sum of costs of all supercolumns is small. In the Augment step, for each
supercolumn P , we modify the graph as shown in Figure 7:
• Add to the graph two copies of P , called P1 and P2 , creating two new faces, one bounded by
P1 and P and the other bounded by P and P2 .
• Add P1 and P2 to OPT.
The resulting graph is denoted GA , and the resulting solution is denoted OPT0A . We consider P1
and P2 to be internal to the two bricks. Thus P remains part of the boundary of each of the bricks,
and M G contains P but not P1 or P2 . Since P1 and P2 share no internal vertices with P , the
joining vertices of OPT0A ∩ B with ∂B belong to NB and SB .

(a)

(b)

Figure 7: Adding the column between two adjacent bricks (solid) in the augment step. The dotted
edges represent OPT in (a) and OPTA in (b).
We perform one more step, a minimality-achieving step:
• We remove edges from OPT0A until it is a minimal set of edges achieving the desired connectivity between terminals.
Let OPTA be the resulting set. We get:
Lemma 5.5. For every brick B, the joining vertices of OPTA ∩ B with ∂B belong to NB and SB .

16

5.1.2

Cleave

We define a graph operation, cleave. Given a vertex v and a bipartition A, B of the edges incident
to v, v is cleaved by
• splitting v into two vertices, vA and vB ,
• mapping the endpoint v of edges in A to vA ,
• mapping the endpoint v of edges in B to vb , and
• introducing a zero-cost edge ev = vA vB .
This operation is illustrated in Figure 8(a) and (b). If the bipartition A, B is non-interleaving
with respect to the embedding’s cycle of edges around v then the construction maintains a planar
embedding.
A
v

B

vA

vB
ev

(a)

(b)

vB
v

vA

(c)

eA

(d)

eA

eB

e'A

e'A
e'B

v

ev

eB
ev
vA

(e)

vB

e'B

(f)

Figure 8: Cleavings illustrated. The bipartition of the edges incident to v is given by the dashed
edges A and solid edges B. (a) Starting with this bipartition, (b) the result of cleaving vertex
v according to this bipartition. A simplifying cleaving of vertex v with respect to a cycle (bold)
before (c) and after (d). A lengthening cleaving of a cycle (e) before and (f) after.
We use two types of cleavings:
17

Simplifying cleavings Refer to Figures 8(c) and (d). Let C be a clockwise non-self-crossing,
non-simple cycle that visits vertex v twice. Define a bipartition A, B of the edges incident
to v as follows: given the clockwise embedding of the edges incident to v, let A start and
end with consecutive edges of C and contain only two edges of C. Such a bipartition exists
because C is non-self-crossing.
Lengthening cleavings Refer to Figures 8(e) and (f). Let C be a cycle, let v be a vertex on
C with two edges eA and eB adjacent to v embedded strictly inside C, and let e0A and e0B
be consecutive edges of C adjacent to v such that the following bipartition is non-crossing
with respect to the embedding: A, B is a bipartition of the edges adjacent to v such that
eA , e0A ∈ A and eB , e0B ∈ B.
We perform simplifying cleavings for non-simple cycles of OPTA until every cycle is simple; the
artificial edges introduced are not included in OPT. The following lemma does not use planarity
and shows that (since cycles get mapped to cycles in this type of cleaving) simplifying cleavings
preserve two-edge connectivity.
b be the graph obtained from H by a simplifying
Lemma 5.6. Let e be an edge in a graph H. Let H
b
cleaving. Then e is a cut-edge in H iff it is a cut-edge in H.
Proof. Let u1 , u2 be the endpoints of e and let C be the cycle w.r.t. which a simplifying cleaving
was performed. If H contains an e-avoiding ui -to-C path for i = 1, 2 then e is not a cut-edge in H,
b Suppose therefore that removing e separates ui from C in H. Then the same
and similarly for H.
b
is true in H, and conversely.
Corollary 5.7. For k = 1, 2, if two vertices are k-edge connected in H then any of their copies
are k-edge connected in HC .
Moreover, after all the simplifying cleavings, every cycle is simple, so:
Lemma 5.8. Vertices that are two-edge-connected in OPTC are biconnected.
Next we perform lengthening cleavings w.r.t. the boundary of a brick and edges eA and eB
of OPTC ; we include in OPTC all the artificial zero-cost edges introduced. Lengthening cleavings
clearly maintain connectivity. Suppose that vertices x and y are biconnected in OPTC , and consider
performing a lengthening cleaving on a vertex v. Since there are two internally vertex-disjoint xto-y paths in OPTC , v cannot appear on both of them. It follows that there remain two internally
vertex-disjoint x-to-y paths after the cleaving. We obtain the following lemma.
Lemma 5.9. Lengthening cleavings maintain biconnectivity.
Lengthening cleavings are performed while there are still multiple edges of the solution embedded in a brick that are incident to a common boundary vertex. Let JC be the set of artificial
edges that are introduced by simplifying and lengthening cleavings. We denote the resulting graph
by GC , we denote the resulting mortar graph by M GC , and we denote the resulting solution by
OPTC .
As a result of the cleavings, we get the following:
Lemma 5.10. Let B be a brick in GC with respect to M GC . The intersection OPTC ∩ int(B) is
a forest whose joining vertices with ∂B are the leaves of the forest.
18

Proof. Let H be a connected component of OPTC ∩int(B). As a result of the lengthening cleavings,
the joining vertices of H with ∂B have degree 1 in H. Suppose otherwise; then there is a vertex
v of H ∩ ∂B that has degree > 1 in H. Hence v is a candidate for a lengthening cleaving, a
contradiction.
By Theorem 2.5 and the minimality-achieving step of the Augment step, any cycle in H must
include a terminal u with r(u) = 2 by Theorem 2.5. Since there are no terminals strictly enclosed
by bricks, u must be a vertex of ∂B. However, that would make u a joining vertex of H with ∂B.
As argued above, such vertices are leaves of H, a contradiction to the fact that u is a vertex of a
cycle in H. Therefore H is acyclic.
Furthermore, leaves of H are vertices of ∂B since OPTC is minimal with respect to edge inclusion
and terminals are not strictly internal to bricks.
Lemma 5.11. Let C be a cycle in OPTC . Let B be a brick. Distinct connected components of
C ∩ int(B) belong to distinct components of OPTC ∩ int(B).
Proof. Assume the lemma does not hold. Then there is a C-to-C path P in int(B). Each vertex
of P that is strictly interior to B is not a terminal. A vertex of P that was on ∂(B) would be
a candidate for a lengthening cleaving, a contradiction. Therefore P includes no terminals. This
contradicts Theorem 2.6.
5.1.3

Flatten

For each brick B, consider the edges of OPTC that are strictly interior to B. By Lemma 5.10,
the connected components are trees. By Lemma 5.5, for each such tree T , every leaf is either on
B’s northern boundary NB or on B’s southern boundary SB . For each such tree T whose leaves
are purely in NB , replace T with the minimal subpath of NB that contains all the leaves of T .
Similarly, for each such tree T whose leaves are purely in SB , replace T with the minimal subpath
of SB that contains all the leaves of T .
Let OPTF be the resulting solution. Note that OPTF is a multiset. An edge of the mortar
graph can appear with multiplicity greater than one.
5.1.4

Map

This step is illustrated in Figures 9(a) and (b). In this step, the multiset OPTF of edges resulting
from the flatten step is used to select a set OPTM of edges of B + (M GC ). Recall that every edge e
of M GC corresponds in B + (M GC ) to three edges: two brick copies (one in each of two bricks) and
one mortar-graph copy. In this step, for every edge e of M GC , we include the mortar-graph copy
of e in OPTM with multiplicity equal to the multiplicity of e in OPTF . At this point, none of the
brick copies are represented in OPTM .
Next, recall that in the augment step, for each supercolumn P , we created two new paths, P1
and P2 , and added them to OPT. The edges of these two paths were not considered part of the
mortar graph, so mortar-graph copies were not included in OPTM for these edges. Instead, for
each such edge e, we include the brick-copy of e in OPTF with multiplicity equal to the multiplicity
of e in OPTF .
Finally, for each edge e interior to a brick, we include e in OPTM with the same multiplicity
as it has in OPTF .

19

(a)

(b)

Figure 9: Map (a) The intersection of OPTC with a brick, dashed. (b) The same brick in the
portal connected graph with portal edges (double-lines) connecting the brick to the corresponding
face (outer boundary) of the mortar graph.
5.1.5

Restructure

Let B be a brick. For simplicity, we write the boundary paths of B as N, E, S, W . Let F be the
multiset of edges of OPTM that are in the interior of B. F is a forest (Lemma 5.10). As a result of
the flatten step, each component of F connects S to N . We will replace F with another subgraph
Fb and map each component T of F to a subgraph φ(T ) of Fb where φ(T ) spans the leaves of T and
is a tree or a cycle. Distinct components of F are mapped by φ to edge-disjoint subgraphs (taking
into account multiplicities).
Refer to Figure 10. We inductively define S-to-N paths P0 , P1 , . . . and corresponding integers
k0 , k1 , . . .. Let s0 , . . . , st be the vertices of S guaranteed by Lemma 4.2 (where s0 is the vertex
common to S and W and st is the vertex common to S and E). Let P0 be the easternmost path
in F from S to N . Let k0 be the integer such that start(P0 )) is in S[sk0 , sk0 +1 ). Inductively, for
i ≥ 0, let Pi+1 be the easternmost path in FN ∧S from S[s0 , ski ) to N that is vertex-disjoint from
Pi . Let ki be the integer such that start(Pi ) ∈ S[ski , ski +1 ). This completes the inductive definition
of P0 , P1 , . . .. Note that the number of paths is at most t, which in turn is at most κ() as defined
in Equation 2.
We use these paths to decompose F , as illustrated in Figure 10. Let Fi be the set of edges of
F − Pi+1 enclosed by the cycle formed by Pi , Pi+1 , N and S. Clearly F = ∪i Fi . If Pi is connected
to Pi+1 , they share at most one vertex, wi . If they are not connected, we say wi is undefined.
There are two cases: either Fi is connected or not.
yi

Pi+1
ri

s0

s1

Pi
ski

xi

ski+1

st

Figure 10: Paths used to decompose F . The brick boundary is given by the rectangle. The paths
P0 , P1 , . . . are bold. Fi is given by the shaded background.
20

Connected case:

There are two subcases. Either Fi spans vertices of S[·, ski ) or not.

Suppose Fi spans vertices of S[·, ski ). Let TS be a minimal subtree of Fi that spans Fi ∩ S and
let TN be a minimal subtree of Fi that spans Fi ∩ N . Let rN be the first vertex of Pi in TN and let
rS be the last vertex of Pi in TS . A path in Fi from TS to N that does not go through rS contradicts
the choice of Pi+1 as there would be a path in Fi from S[·, ski ) to N that is disjoint from Pi . It
follows that TS and TN are edge disjoint: if they intersect they may only do so at rS = rN . If wi
is defined, then there is a path Q from wi to Pi ; Q intersects Pi between rN and rS , for otherwise
there would be a superpath of Q that contradicts the choice of Pi+1 .
If wi−1 is defined and wi−1 ∈ TN , then we replace TN with the tree guaranteed by Lemma 5.3
with roots rN and wi−1 . Otherwise, we replace TN with the tree guaranteed by Lemma 5.2 with
root rN . We do the same for TS .
Suppose Fi does not span vertices of S[·, ski ). Let TN be a minimal connected subgraph of
Fi ∪ S[ski , start(Pi )] that spans Fi ∩ N . Let rN be the first vertex of Pi in TN . If wi is defined, then
there is a path Q from wi to Pi ∪ S[ski , start(Pi )] and Q’s intersection with Pi belongs to Pi [·, rN ],
for otherwise there would be a superpath of Q that contradicts the choice of Pi+1 . If wi−1 is defined
and wi−1 ∈ TN , then we replace Fi with the tree guaranteed by Lemma 5.3 with roots rN and wi−1
along with Q, Pi [·, rN ], and S[ski , start(Pi )]. Otherwise we replace Fi with the tree guaranteed by
Lemma 5.2 with root rN along with Q, Pi [·, rN ], and S[ski , start(Pi )].
In both cases, we define φ0 (Fi ) to be the resulting tree that replaces Fi . By construction, φ0 (Fi )
spans the leaves of Fi and wi−1 and wi (if defined).
Disconnected case: In this case, by the definition of Pi+1 , Fi ∩ S is a subset of the vertices of
S[ski , start(Pi )], for otherwise there would be a path to the right of Pi+1 that connects to N and is
disjoint from Pi .
If Fi is connected to Fi+1 , then the western-most tree TW is a tree with root wi and leaves on
S and does not connect to N as that would contradict the choice of Pi+1 ; if this is the case, let TbW
be the tree guaranteed by Lemma 5.2 and define φ0 (TW ) = TbW .
If Fi is connected to Fi−1 , let S 0 be the subpath of S that spans the eastern-most tree TE ’s
leaves on S. Let TbE be the tree guaranteed by Lemma 5.3 that spans the eastern-most tree’s leaves
on N and roots wi−1 and start(Pi ) and define φ0 (TE ) = TbE .
Let F be the set of remaining trees, let P = N , and let Q = S[ski , start(Pi )] in Lemma 5.4.
b F,
b and φ be the cycle (or empty set), set of trees, and mapping that satisfy the properties
Let C,
stated in the lemma.
b (and TbW , S 0 and TbE if defined).
We define Fbi to consist of the trees of Fb and the cycle C
We replace every Fi with Fbi , as described above, for every brick, creating OPTS . This is illustrated
in Figure 11(a). Now we define φ in terms of φ0 . A component T of F is partitioned into adjacent
trees in this restructuring: namely T1 , . . . , Tk , k ≥ 1. T1 and Tk may be restructured via the
disconnected case and all others are restructured via the connected case. Define φ(T ) = ∪ki=1 φ0 (Ti ).
If k > 1, then consecutive trees Ti and Ti+1 share a vertex wi and by construction φ0 (Ti ) and φ0 (Ti )
also share this vertex. Since φ0 (T ) spans the leaves of T , we get that φ(T ) spans the leaves of T , as
desired. Also by construction, the submapping of φ0 of trees to trees (and not cycles) is bijective;
the same holds for φ.
21

Number of joining vertices In both the connected and disconnected case, the number of leaves
is the result of a constant number of trees resulting from Lemmas 5.2, 5.3 and 5.4. Therefore, Fbi
has o(−2.5 ) joining vertices with N and S. Since i ≤ κ() = O(−3 ), OPTS has o(−5.5 ) joining
vertices with the boundary of each brick. This is the number of connections required to allow a
solution to be nearly optimal and affects the number of portals required in Equation (3):
α() is o(−5.5 )

(6)

This will allow us to prove the second part of the Structure Theorem.

(a)

(b)

Figure 11: Continuing from Figure 9, restructure and rejoin: (a) Restructured version (dark grey)
of the intersection of OPTM with the brick (dashed). (b) Connecting the restructured solution
inside the brick to the mortar graph through portals (via dark grey edges).

5.1.6

Rejoin

In this step, we make inter-brick connections for parts that were disconnected in the mapping step.
Since joining vertices represent the ends of all disconnected parts, it suffices to connect joining
vertices of OPTS with ∂B to their mortar-graph counterparts via portal edges.
This is illustrated in Figure 11 (d): We first move the edges of OPTS ∩∂B to M G for every brick
B. Such edges may have been introduced in the restructure step: for every brick B, we connect
OPTS ∩ B to the mortar graph. For every joining vertex v of OPTS ∩ B, we find the nearest portal
pv , add the subpath of ∂B and M G connecting v and pv and add the portal edge corresponding to
pv . (We need at most two copies of each portal edge.) Finally we contract the edges introduced in
[
the cleaving step. This produces a solution OP
T of B + (M G).

5.2

Analysis of connectivity

In the augment step, because the added paths P1 and P2 form a cycle, this transformation preserves
two-connectivity and connectivity between terminals. Cleaving clearly preserves connectivity and,
by Lemmas 5.8 and 5.9, terminals that require two-connectivity are biconnected in OPTC . Therefore, for terminals x and y requiring connectivity, there is a path PC in OPTC connecting them. If
x and y require two-connectivity, there is a simple cycle CC in OPTC connecting them. We follow
PC and CC through the remaining steps.
Flatten Consider a tree T that is replaced by a subpath Q of a northern or southern boundary
of a brick that spans T ’s leaves. Q spans any terminals that T spanned, since there are no
terminals internal to bricks.
22

PC ∩ T is therefore a (set of) leaf-to-leaf paths and so (PC − T ) ∪ Q contains an x-to-y path.
It follows that there is an x-to-y path PF in OPTF .
By Lemma 5.11, CC ∩ T is a single path and, by the above reasoning, is a leaf-to-leaf path.
Therefore (CC − T ) ∪ Q contains a cycle through x and y. It follows that there is a cycle CF
through x and y in OPTF
1 , P 2 , . . .), (a cyclic sequence C
1
2
Map PF (CF ) gets mapped to a sequence PM = (PM
M = (CM , CM , . . .))
M
of paths of OPTM in B + (M GC ) such that each path either consists completely of mortargraph edges or consists completely of brick-copy edges. The last vertex of one path and the
first vertex of the next path are copies of the same vertex of GC , and that vertex belongs to
a north or south boundary of M GC . By Lemma 5.10, each path in PM or CM that consists
of brick-copy edges starts and ends at the northern or southern boundary of a brick.

Restructure We define a mapping φ̂, based in part on the map φ defined in Section 5.1.5. For
a path Q in PM or CM that uses mortar-copy edges, define φ̂(Q) = Q. For a path Q in PM
or CM that uses brick-copy edges, let T be the tree in OPTM that contains Q and define
φ̂(Q) = φ(T ).
Let CS be the cyclic sequence of trees and cycles to which CM maps by φ. Since φ(T ) spans
the leaves (joining vertices) of T , consecutive trees/cycles in CS contain copies of the same
vertex. By Lemma 5.11 and that, within a brick, the preimage of the set of trees mapped to
by φ, the trees of CS are edge disjoint. (The cycles may be repeated.)
Likewise we define PS having the same properties except for the fact that the sequence is not
cyclic.
Rejoin This step reconnects PS and CS .
Consider a tree T in either of these sequences that contains brick-copy edges. The rejoin step
first moves any edge of T that is in a brick boundary to the mortar copy. It then connects
joining vertices to the mortar by way of detours to portals and portal edges. Therefore, T is
mapped to a tree TJ that connects the mortar copies of T ’s leaves.
Consider a cycle C in either PS or CS . C contains a subpath of N and S whose edges are
moved to their mortar copy and two N -to-S paths whose joining vertices are connected to
their mortar copies. Therefore C is mapped to a cycle CJ through the mortar copies of the
boundary vertices of C.
Let the resulting sequence and cyclic sequence of trees and cycles be PJ and CJ . Since
consecutive trees/cycles in CS contain copies of the same vertex, in CJ consecutive trees/cycles
contain common mortar vertices. We have that CJ is a cyclic sequence of trees and cycles,
through x and y, the trees of which are edge-disjoint. Therefore the union of these contains
a cycle through x and y.
Similarly, we argue that the union of the trees and cycles in PJ contains and x-to-y path.

5.3

Analysis of cost increase

By Lemma 4.3, the total costs of all the east and west boundaries of the bricks is an  fraction of
OPT, so we have
c(OPTA ) ≤ (1 + 2)c(OPT).
(7)
23

The cleaving step only introduces edges of zero cost, so
c(OPTC ) = c(OPTA ).

(8)

The flatten step replaces trees by -short paths, and so can only increase the cost by an  fraction,
giving:
c(OPTF ) ≤ (1 + )c(OPTC ).
(9)
The mapping step does not introduce any new edges, so
c(OPTM ) = c(OPTF ).

(10)

The restructure step involves replacing disjoint parts of OPTM ∩ B for each brick by applying
Lemmas 5.2, 5.3, and 5.4. This increases the cost of the solution by at most an O() fraction. Further
we add subpaths of S[ski , start(Pi )] where OPTM contains disjoint subpaths Pi from start(Pi ) to N
and by the brick properties, c(S[ski , start(Pi )]) ≤ c(Pi ). This increases the the cost of the solution
by at most another O() fraction. We get, for some constant c:
c(OPTS ) ≤ (1 + c)c(OPTM ).

(11)

In the rejoin step, we add two paths connecting a joining vertex to its nearest portal: along the
mortar graph and along the boundary of the brick. The cost added per joining vertex is at most
twice the interportal cost: at most 2c(∂B)/θ for a joining vertex with the boundary of brick B, by
Lemma 4.4. Since each mortar graph edge appears as a brick-boundary edge at most twice, the
sum of the costs of the boundaries of the bricks is at most 18−1 OPT (Equation (1)). Since there
are α() joining vertices of OPTS with each brick, the total cost added due to portal connections is
α
OPT. Replacing α and θ via Equations (6) and (3) gives us that the total cost added
at most 36 θ
due to portal connections is
O(c(OPT))
(12)
[ ≤ (1 + c0 )c(OPT) for some constant c0 , proving
Combining equations (7) through (12), c(OPT)
Theorem 4.6.

6

Dynamic Program

In this section we show that there is a dynamic program that finds an approximately optimal
solution in the portal-connected graph B + (P ).

6.1

Structure of solution

We start by showing that we can restrict our attention to solutions whose intersection with each
brick is a small collection of trees whose leaves are portals.
Lemma 6.1. Let S be a minimal solution to the instance (B + (M G), r) of the {0, 1, 2}-edge connectivity problem. Let B be a brick, and suppose that the intersection of S with B is the union of
a set of non-crossing trees whose leaves are portals. Then the number of such trees is at most three
times the number of portals.

24

Proof. Let the portals be v1 , . . . , vk in counterclockwise order. Each tree induces a subpartition on
the set of pairs {(i, i + 1) : i ∈ {1, . . . , k − 1}} as follows: if the leaves of the tree are vi1 , vi2 , . . . , vip
where i1 < i2 < · · · < ip , then the parts are
{(i1 , i1 + 1), . . . , (i2 − 1, i2 )}, {(i2 , i2 + 1), . . . , (i3 − 1, i3 )}, . . . , {(ip−1 , ip−1 + 1), . . . , (ip − 1, ip )}
Because the trees are non-crossing, the corresponding subpartitions are non-crossing as well: for
each pair T1 , T2 of trees, either each part of T2 is a subset of some part of T1 , or vice versa.
Therefore the trees themselves form a rooted tree T according to the nesting relation of the
corresponding subpartitions. Furthermore, by minimality of S, no three trees have the same sets
of leaves. This shows that a node of T with only one child has a parent with at least two children.
The number of leaves of T is at most the number of pairs (i, i + 1), which is at most k − 1. This
shows that the number of trees is at most 3(k − 1).
Corollary 6.2. There exists a function f that maps each brick B to a cardinality-at-most-3θ
subpartition f (B) of the portals of B with the following property:
for each brick B, for each part PS of f (B), let TP be any minimum-cost tree in B whose leaves
are P , and let HB be the union P ∈f (B) TP . Then there is a feasible solution S 0 to the instance
(B + (M G), r) such that
• the cost of S 0 is at most (1 + c)OPT where c is an absolute constant, and
• the intersection of S with any brick B is HB .
Proof. Theorem 4.6 states that there is a feasible solution S of cost at most (1 + c)OPT such that
the intersection of S with any brick B is the multi-set union of a family TB of non-crossing trees
whose leaves are portals. We assume that S is a minimal feasible solution. Lemma 6.1 shows that
|TB | ≤ 3θ.
Now we construct the multi-subgraph S 0 from S. For each brick B, replace each tree in TB0 with
a minimum-cost tree having the same leaves. Clearly the cost of S 0 is at most that of S. It remains
to show that S 0 is a feasible solution.
Let u and v be two terminals. Let P or C be a minimal u-to-v path or minimal cycle containing
u and v in B + (M G) using edges of S. We obtain a u-to-v path P 0 in S 0 or a cycle C 0 in S 0 containing
u and v as follows. For each brick B, the intersection of P or C with B is a set of paths P1 , . . . , Pk
through the trees in TB such that each path Pi starts and ends on a portal. For each path Pi , the
tree in TB connecting the endpoints of Pi is replaced in S 0 by another tree that includes the same
endpoints, so that tree contains a path Pi0 with the same endpoints. We replace each path Pi with
the path Pi0 . Let P 0 and C 0 be the subgraphs obtained by performing these transformations for
each brick B. The transformations ensure that P 0 and C 0 are in S 0 . The path P 0 shows that u and
v are connected in S 0 .
For a cycle C in S, we still need to show that C 0 is a cycle. In particular, we need to show that,
for each brick B, the paths P1 , . . . , Pk forming the intersection of C with B all belong to different
trees in TB0 . Assume for a contradiction that Pi and Pj belong to a single tree T ∈ TB0 . By the
assumption that the degree is at most three, Pi and Pj cannot share a vertex. Therefore there is a
Pi -to-Pj path in T containing at least one edge. However, since C is a cycle containing Pi and PJ ,
an edge of the Pi -to-Pj path can be removed while preserving feasibility, a contradiction.

25

Figure 12: The spanning tree of the dual of the parcel is transformed to be a spanning tree of
the planar dual of B ÷ (P ). For each brick, all but one of the portal edges is included in the new
spanning tree.

6.2

The tree used to guide the dynamic program

Recall that B ÷ (P ) is the brick-contracted graph, in which each brick of B + (P ) is contracted to a
vertex. Recall that a parcel P is a subgraph of M G and defines a set of bricks contained by the
faces of P . The planar dual of the parcel has a spanning tree T of depth η + 1. The algorithm
transforms T into a spanning tree T 0 of the planar dual of B ÷ (P ) as follows. Each brick is a vertex
of T ; replace that vertex with a cycle minus one edge consisting of the duals of the portal edges,
as shown in Figure 12.
Since each brick has at most θ portal edges, it follows that the spanning tree T 0 of the dual of
B ÷ (P ) has depth at most (η + 1)θ. Next, the algorithm defines Tb to be the set of edges of B ÷ (P )
whose duals are not in T 0 . A classical result on planar graphs implies that Tb is a spanning tree of
B ÷ (P ). The construction ensures that each vertex of B ÷ (P ) that corresponds to a brick has only
one incident edge in Tb. By our assumption that each vertex in the input graph has degree at most
three, every vertex of B ÷ (P ) that appears in G has degree at most three in Tb. Thus Tb has degree
at most three. The bound on the depth of T 0 ensures that, for each vertex v of Tb, the graph B ÷ (P )
contains at most 2(η + 1)(θ + 1) + 1 edges between descendents of v and non-descendents.

6.3

The dynamic programming table

The algorithm considers the spanning tree Tb of B ÷ (P ) as rooted at an arbitrary leaf. By our
assumption that the input graph has degree three, each vertex v of Tb has at most two children.
Let Tb(v) denote the subtree of Tb rooted at v. For each vertex v of Tb, define

B if v is the result of contracting a brick B
f (v) =
v otherwise
S
and define W (v) to be the subgraph of B + (P ) induced by {f (w) : w ∈ Tb(v)}. Let δ(S) be the
subset of edges with exactly one endpoint in the subgraph S (i.e. a cut). It follows that the cut
δ(W (v)) in B + (P ) is equal to the cut δ(Tb(v)) in B ÷ (P ) and so has O(θη) edges. The dynamic
programming table will be indexed over configurations, defined below.

26

6.3.1

Configurations

Let L = δ(H) for a connected, vertex-induced subgraph H of B + (P ). We define a configuration
KL corresponding to L, illustrated in Figure 13. First, for each edge e ∈ L, we defined two edges
2
e1 and
the fact that an edge can be used twice. Let L̂ be the resulting set of edges,
S e to1 reflect
2
L̂ = e∈L {e , e }. A configuration is a forest with no degree-2 vertices whose leaf edges are a subset
of L̂, and such that, for each edge e ∈ L, if the forest contains both e1 and e2 then these two edges
are incident to the same vertex in the forest, together with a {1, 2} labeling of the internal vertices.
We denote the set of all configurations on edge set L by KL .
c

b

a

c

d
e

a

(c,1)

(a,2)

(d,1)

d
e

(a,1)

h

g
(a)

f

(h,1)

h
(g,1)

(b)

g

f

(c)

Figure 13: (a) The cut edges (black) of a subgraph H (shaded). (b) A configuration (dotted forest)
for L = δ(H). (c) A subgraph (bold) that meets the configuration.
Lemma 6.3. The number of configurations for H where n = |δ(H)| is at most 16n (2n)2n−2 and
these trees can be computed in O(16n (2n)2n−2 ) time.
Proof. A configuration can be selected as follows. First, for each of the n edges, decide whether
edge e1 is to be included and whether e2 is to be included. (There are 4n choices.) Let n0 be the
number of edges e for which either e1 or e2 is to be included. Next, select a tree with the selected
0
edges as leaf edges. It follows from Cayley’s formula that the number of such trees is 2n02n −2 ,
which is at most 2n2n−2 . Next, delete some subset of non-leaf edges of the tree. There are at most
2n ways of selecting such a subset. Finally, select a {1, 2} labeling of the internal vertices. There
are at most 2n such labelings.
The set of trees can be computed in O(1) amortized time per tree [22].
Connecting A configuration KL ∈ KL is connecting if, for each internal vertex v of KL , if v has
label c then KL contains c paths from v to leaves.
Compatibility Configurations KA ∈ KA and KB ∈ KB are compatible if for every edge e ∈ Â∩ B̂
either e ∈ KA ∩ KB or e ∈
/ KA ∪ KB .
Compressed bridge-block forest For a graph G, a block is a maximal subgraph such that, for
every two vertices u and v in the subgraph, there are two edge-disjoint u-to-v paths. Contracting
each block of G to a single vertex yields the bridge-block forest of G. It is easy to see that it is
indeed a forest. An edge e of G is an edge of this forest if e is a bridge of G, i.e. if the endpoints
of e are in different connected components of G − e.
27

We define the compressed bridge-block forest to be the forest obtained from the bridge-block
forest by substituting an edge for each maximal path of internal degree two. We denote the
g
compressed bridge-block forest of G by EC(G).
Consistency We say a configuration KA is consistent with a set of mutually compatible configurations {KA1 , KA2 , . . .} if
g i KA ) that preserves the identity of leaf edges
• there is an isomorphism between KA and EC(∪
i
of KA , and
• for each vertex x of ∪i KAi that is labeled 2, x is in a block of ∪i KAi that corresponds to a
vertex in KA that is labeled 2.
Meeting Let H be a connected, vertex-induced subgraph of G. Let M be a minimal solution
to an instance (G, r). Let MH be the graph obtained from M as follows. Remove edges not in
H ∪ δ(H). Next, for each vertex v outside of H, if v has k incident edges, replace v with k copies
of v, one incident to each of these edges.
g H ) = Kδ(H) and if, for each terminal x in H,
We say M meets a configuration Kδ(H) if EC(M
MH either contains r(x) edge-disjoint paths to vertices outside of H or contains min{r(x), r(y)}
edge-disjoint paths to every other terminal y.
DP table entry The dynamic program constructs a table DPv for each vertex v of Tb. The table
DPv is indexed by the configurations of δ(W (v)). We showed in Section 6.1 that we can restrict
our attention to solutions with the following property:
the intersection with each brick is a cardinality-at-most-3θ collection of minimum-cost
trees whose leaves are portals.
For each configuration K of δ(W (v)), the entry DPv [K] is the minimum cost of a subgraph of
W (v) that meets configuration K and has the above property. We do not count the cost of edges
of δ(W (v)).
6.3.2

The filling procedure

If u is not a leaf of Tb, then we populate the entries of DPu with the procedure fill. We use the
shorthand K for Kδ({u}) and Ki for Kδ(W (ui )) . The cuts are with respect to the graph B + (P ).
fill(DPu )
Initialize each entry of DPu to ∞.
Let u1 , . . . , us be the children of u.
For every set of connecting, mutually compatible configurations K, K1 , . . . , Ks ,
For every connecting configuration K0 that is consistent with P
K, K1 , . . . , Ks ,
cost ← c(K ∩ (∪si=1 Ki )) + (c(K1 ∩ K2 ) if s = 2 else 0) + si=1 DPui [Ki ].
DPu [K0 ] ← min{DPu [K0 ], cost}
Since Tb has degree at most three, the number s of children of each vertex u in Tb is at most two.

28

If u is a leaf of Tb and u does not correspond to a brick (i.e. f (u) = u), the problem is trivial.
Each configuration K is a star: u is the center vertex, and the edges of δ({u}) are the edges of K.
Since the cost of any subgraph that is induced by {u} is zero, the value of DPu [K] is zero for every
K.
Suppose u is a leaf of Tb and f (u) is a brick B. Recall that we restrict our attention to solutions
whose intersection with B is a collection of at most 3θ minimum-cost trees whose leaves are portals.
The algorithm populates the table DPu as follows. Initialize each entry of DPu to ∞. Next, iterate
over cardinality-at-most-3θ families of subsets of the portals. For each family F,
• define a subgraph HF to be the multi-set union over subsets P in F of a minimum-cost tree
spanning P ,
• find the configuration K corresponding to HF , and
• set DPu [K] ← min{DPu [K], cost of HF }.
The minimum-cost tree spanning a subset of portals can be computed in O(θ3 n) time using the
algorithm of Theorem 2.1.
6.3.3

Running time

Consider the time required to populate the DPu for all the leaves u of Tb. We need only consider
non-crossing partitions of subsets of δ(W (v)) since HK is the union of non-crossing trees. The
number of non-crossing partitions of an n element ordered set is the nth Catalan number, which is
at most 4n /(n + 1). Therefore, the number of non-crossing sub-partitions is at most 4n . It follows
that the time to populate DPv for v a brick vertex is O(θ4 4θ |B|) which is O(2poly(1/) |B|) since θ
depends polynomially on 1/. Since a vertex appears at most twice in the set of bricks, the time
needed to solve all the base cases in O(2poly(1/) n) where n is the number of vertices in the parcel.
Consider the time required to populate the DPu for all the internal vertices u of Tb. The number
of edges in δ(W (v)) in B + (P ) is O(θη). By Lemma 6.3, it follows that the corresponding number
of configurations is O(2poly(1/) ) since θ and η each depend polynomially on 1/. There are O(n)
vertices of the recursion tree and so the time required for the dynamic program, not including the
base cases is O(2poly(1/) n).
The total running time of the dynamic program is O(2poly(1/) n) where n is the number of
vertices in the parcel.

6.4

Correctness

The connecting property guarantees that the final solution is feasible (satisfying the conectivity
requirements). The definitions of compatible and consistent guarantee the inductive hypothesis.
We show that the procedure fill correctly computes the cost of a minimum-cost subgraph Hu
of W (u) that meets the configuration K0 . We have shown that this is true for the leaves of the
recursion tree. Since K is the configuration corresponding to the cut δ({u0 }), K is a star. Therefore
c(K) is the cost of the edges of δ({u0 }): K is both the configuration and a minimum-cost subgraph
that meets that configuration. Further, c(K ∩ (∪si=1 Ki )) is the cost of the edges of K that are in
Ki (for i = 1, . . . , s). w(∩si=1 Ki ) is equal to the cost of the edges common to K1 and K2 if s = 2
and zero otherwise. By the inductive hypothesis the cost computed is that of a Hu : the subgraph
of W (u) of a minimum-cost graph that meets this configuration.
29

Consider the entries of DPr where r is the root of Tb. Since δ(W (r)) is empty, there is only one
configuration corresponding to this subproblem: the trivial configuration. Therefore, the dynamic
program finds the optimal solution in B + (P ).
As argued in Section 4.4, combining parcel solutions forms a valid solution in our input graph.
We need to compare the cost of the output to the cost of an optimal solution.
Recall that new terminals are added at the parcel boundaries to guarantee connectivity between
the parcels; let r + denote the requirements including these new terminals. Let S(G, r) denote the
optimal solution in graph G with requirements r.
For each parcel P , there is a (possibly empty) solution SP in B + (P ) for the original and new
terminals in P consisting of edges of S(B + (MG), r) ∪ ∂H (where H is the set of parcels and ∂H is
the set of boundary edges of all parcels). We have:
c(S(B + (MG), r) ∩ B + (P )) ≤ c(SP ) = c(SP − ∂H) + c(SP ∩ ∂H).
Every edge of S(B + (MG), r) not in ∂H appears in SP for exactly one parcel P , and so
X
c(SP − ∂H) ≤ c(S(B + (MG), r)).
P ∈H

Every edge of ∂H appears in at most two parcels, and so
X
c(SP ∩ ∂H) ≤ 2 · c(∂H).
P ∈H

Since a feasible solution for the original and new terminals in B + (MG) can be obtained by adding
a subset of the edges of ∂H to S(B + (MG), r), the cost of the output of our algorithms is at most
X
c(∂H) +
S(B + (P ), r + ) ≤ c(S(B + (MG), r)) + 3c(∂H).
P ∈H

Combining the cost of the parcel boundaries, the definition of η, and the cost of the mortar graph,
we obtain c(∂H) ≤ 21 c(S(G, r)) = 12 OPT. Finally, by Theorem 4.6, the cost of the output is at
most (1 + c) OPT. This gives:
Theorem 6.4. There is an approximation scheme for solving the {0, 1, 2}-edge connectivity problem
(allowing duplication of edges) in planar graphs. The running time is O(2poly(1/) n + n log n).
Comments The PTAS framework used is potentially applicable to problems where (i) the input
consists of a planar graph G with edge-costs and a subset Q of the vertices of G (we call Q the set of
terminals), and where (ii) the output spans the terminals. Steiner tree and two-edge-connectivity
have been solved using this framework. The PTAS for the subset tour problem [18] (which was the
inspiration for this framework) can be reframed using this technique. Since the extended abstract of
this work first appeared, Borradaile, Demaine and Tazari have also this framework to give PTASes
for the same set of problems in graphs of bounded genus [6], Bateni, Hajiaghayi and Marx [3]
have extended the framework to the Steiner forest problem and Bateni et al. [2] have extended the
framework to prize collecting problems.

30

Acknowledgements The authors thank David Pritchard for comments on early versions of this
work and discussions with Baigong Zheng regarding Theorems 2.5 and 2.6. This material is based
upon work supported by the National Science Foundation under Grant Nos. CCF-0964037, CCF0963921, CCF-14-09520 and by a Natural Science and Research Council of Canada Postdoctoral
Fellowship.

References
[1] B. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of
the ACM, 41(1):153–180, 1994.
[2] M. Bateni, C. Chekuri, A. Ene, M. Hajiaghayi, N. Korula, and D. Marx. Prize-collecting
Steiner problems on planar graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1028–1049, 2011.
[3] M. Bateni, M. Hajiaghayi, and D. Marx. Approximation schemes for Steiner forest on planar
graphs and graphs of bounded treewidth. J. ACM, 58(5):21, 2011.
[4] A. Berger, A. Czumaj, M. Grigni, and H. Zhao. Approximation schemes for minimum 2connected spanning subgraphs in weighted planar graphs. In Proceedings of the 13th European
Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 472–483,
2005.
[5] A. Berger and M. Grigni. Minimum weight 2-edge-connected spanning subgraphs in planar
graphs. In Proceedings of the 34th International Colloquium on Automata, Languages and
Programming, volume 4596 of Lecture Notes in Computer Science, pages 90–101, 2007.
[6] G. Borradaile, E. Demaine, and S. Tazari. Polynomial-time approximation schemes for subsetconnectivity problems in bounded-genus graphs. Algorithmica, 2012. Online.
[7] G. Borradaile, C. Kenyon-Mathieu, and P. Klein. A polynomial-time approximation scheme
for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 1285–1294, 2007.
[8] G. Borradaile, P. Klein, and C. Mathieu. Steiner tree in planar graphs: An O(n log n) approximation scheme with singly exponential dependence on epsilon. In Proceedings of the 10th
International Workshop on Algorithms and Data Structures, volume 4619 of Lecture Notes in
Computer Science, pages 275–286, 2007.
[9] G. Borradaile, P. Klein, and C. Mathieu. An O(n log n) approximation scheme for Steiner tree
in planar graphs. ACM Transactions on Algorithms, 5(3):1–31, 2009.
[10] A. Czumaj and A. Lingas. On approximability of the minimum cost k-connected spanning
subgraph problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 281–290, 1999.
[11] R. Erickson, C. Monma, and A. Veinott. Send-and-split method for minimum-concave-cost
network flows. Mathematics of Operations Research, 12:634–664, 1987.

31

[12] K. Eswaran and R. Tarjan. Augmentation problems. SIAM Journal on Computing, 5(4):653–
665, 1976.
[13] G. Frederickson and J. Jájá. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270–283, 1981.
[14] M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, É. Tardos, and D. Williamson. Improved
approximation algorithms for network design problems. In Proceedings of the 5th Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 223–232, 1994.
[15] M. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for
planar graphs. Journal of Computer and System Sciences, 55(1):3–23, 1997.
[16] K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem.
Combinatorica, 2001(1):39–60, 21.
[17] S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings. Journal of the
ACM, 41(2):214–235, 1994.
[18] P. Klein. A subset spanner for planar graphs, with application to subset TSP. In Proceedings
of the 38th Annual ACM Symposium on Theory of Computing, pages 749–756, 2006.
[19] P. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with
edge-weights. SIAM Journal on Computing, 37(6):1926–1952, 2008.
[20] P. Klein and R. Ravi. When cycles collapse: A general approximation technique for constraind
two-connectivity problems. In Proceedings of the 3rd International Conference on Integer
Programming and Combinatorial Optimization, pages 39–55, 1993.
[21] K. Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs. Information
Processing Letters, 27(3):125–128, 1988.
[22] S. Nakano and T. Uno. Efficient generation of rooted trees. Technical Report NII-2003-005E,
National Institute of Informatics, 2003.
[23] R. Ravi. Approximation algorithms for Steiner augmentations for two-connectivity. Technical
Report TR-CS-92-21, Brown University, 1992.
[24] M. Resende and P. Pardalos, editors. Handbook of Optimization in Telecommunications.
Springer, 2006.
[25] H. Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc., 34:339–362, 1932.
[26] P. Widmayer. A fast approximation algorithm for Steiner’s problem in graphs. In GraphTheoretic Concepts in Computer Science, volume 246 of Lecture Notes in Computer Science,
pages 17–28. Springer Verlag, 1986.
[27] D. Williamson, M. Goemans, M. Mihail, and V. Vazirani. A primal-dual approximation algorithm for generalized Steiner network problems. In Proceedings of the 25th Annual ACM
Symposium on Theory of Computing, pages 708–717, 1993.

32

[28] Y. Wu, P. Widmayer, and C. Wong. A faster approximation algorithm for the Steiner problem
in graphs. Acta informatica, 23(2):223–229, 1986.

33

