Doubly Balanced Connected Graph Partitioning

arXiv:1607.06509v1 [math.CO] 21 Jul 2016

Saleh Soltan∗
Electrical Engineering
Columbia University
New York, NY
saleh@ee.columbia.edu

Mihalis Yannakakis†
Computer Science
Columbia University
New York, NY
mihalis@cs.columbia.edu

Gil Zussman∗
Electrical Engineering
Columbia University
New York, NY
gil@ee.columbia.edu

Abstract
We introduce and study the Doubly Balanced Connected graph Partitioning (DBCP) problem: Let G=(V, E) be a P
connected graph with a weight (supply/demand) function p:V →
{−1, +1} satisfying p(V )= j∈V p(j)=0. The objective is to partition G into (V1 , V2 ) such that
1 | |V2 |
G[V1 ] and G[V2 ] are connected, |p(V1 )|, |p(V2 )|≤cp , and max{ |V
|V2 | , |V1 | }≤cs , for some constants
cp and cs . When G is 2-connected, we show that a solution with cp =1 and cs =3 always exists
and can be found in polynomial time. Moreover, when G is 3-connected, we show that there
is always a ‘perfect’ solution (a partition with p(V1 )=p(V2 )=0 and |V1 |=|V2 |, if |V |≡0(mod 4)),
and it can be found in polynomial time. Our techniques can be extended, with similar results,
to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p(V )6=0
and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve
approximately the proportion of the two types.

∗

Research partially supported by DTRA grant HDTRA1-13-1-0021 and CIAN NSF ERC under grant EEC0812072.
†
Research partially supported by NSF grant CCF-1320654.

1

Introduction

Power Grid Islanding is an effective method to mitigate cascading failures in power grids [17].
The challenge is to partition the network into smaller connected components, called islands, such
that each island can operate independently for a while. In order for an island to operate, it is
necessary that the power supply and demand at that island are almost equal.1 Equality of supply
and demand in an island, however, may not be sufficient for its independent operation. It is also
important that the infrastructure in that island has the physical capacity to safely transfer the
power from the supply nodes to the demand nodes. When the island is large enough compared to
the initial network, it is more likely that it has enough capacity. This problem has been studied in
the power systems community but almost all the algorithms provided in the literature are heuristic
methods that have been shown to be effective only by simulations [8, 14, 16, 17].
Motivated by this application, we formally introduce and study the Doubly Balanced Connected graph Partitioning (DBCP) problem: Let G=(V,
P E) be a connected graph with a weight
(supply/demand) function p:V →Z satisfying p(V )= j∈V p(j)=0. The objective is to partition V
|V1 | |V2 |
into (V1 , V2 ) such that G[V1 ] and G[V2 ] are connected, |p(V1 )|, |p(V2 )|≤cp , and max{ |V
,
}≤cs ,
2 | |V1 |
for some constants cp and cs . We also consider the case that p(V )6=0, in which the excess supply/demand should be split roughly evenly.
The problem calls for a partition into two connected subgraphs that simultaneously balances
two objectives, (1) the supply/demand within each part, and (2) the sizes of the parts. The
connected partitioning problem with only the size objective has been studied previously. In the
most well-known result, Lováz and Gyori [9,13] independently proved, using different methods, that
every k-connected graph can be partitioned into k arbitrarily sized connected subgraphs. However,
neither of the proofs is constructive, and there are no known polynomial-time algorithms to find
such a partition for k>3. For k=2, a linear time algorithm is provided in [18] and for k=3 an
O(|V |2 ) algorithm is provided in [20].2 The complexity of the problem with the size objective and
related optimization problems have been studied in [3, 5, 6] and there are various NP-hardness and
inapproximability results. Note that the size of the cut is not of any relevance here (so the extensive
literature on finding balanced partitions, not necessarily connected, that minimize the cut is not
relevant.)
The objective of balancing the supply/demand alone, when all p(i) are ±1, can also be seen as
an extension for the objective of balancing the size (which corresponds to p(i)=1). Our bi-objective
problem of balancing both supply/demand and size, can be seen also as an extension of the problem
of finding a partition that balances the size for two types of nodes simultaneously: Suppose the
nodes of a graph are partitioned into red and blue nodes. Find a partition of the graph into two
large connected subgraphs that splits approximately evenly both the red and the blue nodes.
We now summarize our results and techniques. Since the power grids are designed to withstand
a single failure (“N −1” standard) [1], and therefore 2-connected, our focus is mainly on the graphs
that are at least 2-connected. We first, in Section 3, study the connected partitioning problem
with only the supply/demand balancing objective, and show results that parallel the results for
balancing size alone, using similar techniques: The problem is NP-hard in general. For 2-connected
graphs and weights p(i)=±1, there is always a perfectly balanced partition and we can find it easily
using an st-numbering. For 3-connected graphs and weights p(i)=±1, there is a perfectly balanced
partition into three connected graphs, and we can find it using a nonseparating ear decomposition
1

If the supply and demand are not exactly equal but still relatively close, load shedding/generation curtailing can
be used in order for the island to operate.
2
For k=2, a much simpler approach than the one in [18] is to use the st-numbering [11] for 2-connected graphs.

1

of 3-connected graphs [4] and similar ideas as in [20].
The problem is more challenging when we deal with both balancing objectives, supply/demand
and size. This is the main focus and occupies the bulk of this paper. Our main results are existence
results and algorithms for 2- and 3-connected graphs. It is easy to observe that we cannot achieve
perfection in one objective (cp =0 or cs =1) without sacrificing completely the other objective. We
show that allowing the supply/demand of the parts to be off balance by at most the weight of one
node suffices to get a partition that is roughly balanced also with respect to size.
First, in Section 3.1, we study the case of 3-connected graphs since we use this later as the basis
of handling 2-connected graphs. We show that if ∀i, p(i)=±1, there is a partition that is perfectly
balanced with respect to both objectives, if |V |≡0(mod 4) (otherwise the sizes are slightly off for
parity reasons); for general p, the partition is perfect in both objectives up to the weight of a single
node. Furthermore, the partition can be constructed in polynomial time. Our approach uses the
convex embedding characterization of k-connectivity studied by Linial, Lováz, and Wigderson [12].
We need to adapt it for our purposes so that the convex embedding also has certain desired geometric
properties, and for this purpose we use the nonseparating ear decomposition of 3-connected graphs
of [4] to obtain a suitable embedding.
Then, in Section 3.2, we analyze the case of 2-connected graphs. We reduce it to two subcases:
either (1) there is a separation pair that splits the graph into components that are not very large,
or (2) we can perform a series of contractions to achieve a 3-connected graph whose edges represent
contracted subgraphs that are not too large. We provide a good partitioning algorithm for case (1),
and for case (2) we extend the algorithms for 3-connected graphs to handle also the complications
arising from edges representing contracted subgraphs. Finally, in Section 4, we briefly discuss the
problem of finding a connected partitioning of a graph with two types of nodes that splits roughly
evenly both types.
The body of the paper contains proofs and sketches for some of the results, and Appendices B, C,
and D contain the remaining proofs. Graph-theoretic background and definitions (e.g., the notions
of st-numbering, nonseparating ear decomposition, convex embedding of k-connected graphs) are
given in Appendix A.

2

Balancing the Supply/Demand Only

In this section, we study the single objective problem of finding a partition of the graph into
connected subgraphs that balances (approximately) the supply and demand in each part of the
partition, without any regard to the sizes of the parts. We can state the optimization problem
as follows, and will refer to it as the Balanced Connected Partition with Integer weights (BCPI)
problem.
Definition
1. Given a graph G=(V, E) with a weight (supply/demand) function p : V → Z satisP
fying j∈V p(j)=0. The BCPI problem is the problem of partitioning V into (V1 , V2 ) such that
1. V1 ∩V2 =∅ and V1 ∪V2 =V ,
2. G[V1 ] and G[V2 ] are connected,
P
3. |p(V1 )|+|p(V2 )| is minimized, where p(Vi )= j∈Vi p(j).
Clearly, the minimum possible value for |p(V1 )|+|p(V2 )| that we can hope for is 0, which occurs
iff p(V1 )=p(V2 )=0. It is easy to show that the problem of determining whether there exists such a
‘perfect’ partition (and hence the BCPI problem) is strongly NP-hard. The proof is very similar
2

to analogous results concerning the partition of a graph into two connected subgraphs with equal
sizes (or weights, when nodes have positive weights) [3, 6]
Proposition 1. (1) It is strongly NP-hard to determine whether there is a solution to the BCPI
problem with value 0, even when G is 2-connected.
(2) If G is not 2-connected, then this problem is NP-hard even when ∀i, p(i)=±1.
Although it is NP-hard to tell whether there is a solution satisfying p(V1 )=p(V2 )=0, even when
∀i, p(i)=±1, in this case, if the graph G is 2-connected there is always such a solution. For general
weights p, there is a solution such that |p(V1 )|, |p(V2 )|≤maxj∈V |p(j)|/2 and it can be found easily
in linear time using the st-numbering between two nodes (see the Appendix B).
Proposition 2. Let G be a 2-connected graph and u, v any two nodes in V such that p(u)p(v)>0.
(1) There is a solution such that u∈V1 , v∈V2 , and |p(V1 )|=|p(V2 )|≤maxj∈V |p(j)|/2.
(2) If ∀i, p(i)=±1, we can find a solution such that u∈V1 , v∈V2 , and p(V1 )=p(V2 )=0.
In both cases, the solution can be found in O(|E|) time.
Remark. The bound in Proposition 2 (1) is tight. A simple example is a cycle of length 4 like
(v1 , v2 , v3 , v4 ) with p(v1 )=−p, p(v2 )=−p/2, p(v3 )=p, and p(v4 )=p/2. It is easy to see that in this
example |p(V1 )|+|p(V2 )|=maxj∈V |p(j)|=p is the best that one can do.

2.1

Connected Partitioning into Many Parts

The BCPI problem can be extended to partitioning a graph
P into k=3 or more parts. Let G=(V, E)
be a graph with a weight function p : V → Z satisfying j∈V p(j)=0. The BCPIk problem is the
problem of partitioning G into (V1 , V2 , . . . , Vk ) such that for any 1≤i≤k, G[Vi ] is connected and
P
k
i=1 |p(Vi )| is minimized.
In the following proposition, we show that for k=3, if p(i)=±1, ∀i, then there is always a perfect
partition (i.e., with p(V1 )=p(V2 )=p(V3 )=0) and it can be found efficiently. For general p, we can
find a partition such that |p(V1 )|+|p(V2 )|+|p(V3 )|≤2 maxj∈V |p(j)|. The proof and the algorithm use
a similar approach as the algorithm in [20] for partitioning a 3-connected graph to three connected
parts with prescribed sizes, using the nonseparating ear decomposition of 3-connected graphs as
described in Subsection A.4. The proof is given in the Appendix B.
Proposition 3. Let G be a 3-connected graph and u, v, w three nodes in V such that p(u), p(v), p(w)>
0 or p(u), p(v), p(w)<0.
(1) There is a solution such that u∈V1 , v∈V2 , w∈V3 , and |p(V1 )|+|p(V2 )|+|p(V3 )|≤2 maxj∈V |p(j)|.
(2) If ∀i, p(i)=±1, then there is a solution such that u∈V1 , v∈V2 , w∈V3 , and |p(V1 )|=|p(V2 )|=
|p(V3 )|=0.
In both cases, the solution can be found in O(|E|) time.

3

Balancing Both Objectives

In this section, we formally define and study the Doubly Balanced Connected graph Partitioning
(DBCP) problem.
Definition 2.PGiven a graph G=(V, E) with a weight (supply/demand) function p : V → Z satisfying p(V )= j∈V p(j)=0 and constants cp ≥0, cs ≥1. The DBCP problem is the problem of
partitioning V into (V1 , V2 ) such that
1. V1 ∩V2 =∅ and V1 ∪V2 =V ,
3

2𝑠 + 1
−1

−1

−1

−1

+1

+1

+1

−1

−1

−1

+1

+1

+1

−1

−1

−1

+1

+1

+1

−1

−1

+1

+1

+1

−1

2𝑡 + 1

+1

2𝑡 + 1

Figure 1: Series-parallel graphs with 2s+1 paths of length 4t+2 used in Observations 1 and 2.
2. G[V1 ] and G[V2 ] are connected,
|V1 | |V2 |
3. |p(V1 )|, |p(V2 )|≤cp and max{ |V
,
}≤cs , where p(Vi )=
2 | |V1 |

P

j∈Vi

p(j).

Remark. Our techniques apply also to the case that p(V )6=0. In this case, the requirement 3
on p(V1 ) and p(V2 ) is |p(V1 )−p(V )/2|, |p(V2 )−p(V )/2|≤cp , i.e., the excess supply/demand is split
approximately evenly between the two parts.
We will concentrate on 2-connected and 3-connected graphs and show that we can construct
efficiently good partitions. For most of the section we will focus on the case that p(i)=±1, ∀i∈V .
This case contains all the essential ideas. All the techniques generalize to the case of arbitrary p,
and we will state the corresponding theorems.
We observed in Section 2 that if the graph is 2-connected and p(i)=±1, ∀i∈V then there is
always a connected partition that is perfect with respect to the weight objective, p(V1 )=p(V2 )=0,
i.e., (3) is satisfied with cp =0. We know also from [9, 13] that there is always a connected partition
that is perfect with respect to the size objective, |V1 |=|V2 |, i.e., condition 3 is satisfied with cs =
1. The following observations show that combining the two objectives makes the problem more
challenging. If we insist on cp =0, then cs cannot be bounded in general, (it will be Ω(|V |)), and
if we insist on cs =1, then cp cannot be bounded. The series-parallel graphs of Figure 1 provide
simple counterexamples.
Observation 1. If cp =0, then for any cs <|V |/2−1, there exist a 2-connected graph G such that
the DBCP problem does not have a solution even when ∀i, p(i)=±1.
Proof. In the graph depicted in Figure 1, set t=0.
Observation 2. If cs =1, then for any cp <|V |/6, there exist a 2-connected graph G such that the
DBCP problem does not have a solution even when ∀i, p(i)=±1.
Proof. In the graph depicted in Figure 1, set s=1.
Thus, cp has to be at least 1 to have any hope for a bounded cs . We show in this section that
cp =1 suffices for all 2-connected graphs. We first treat 3-connected graphs.

3.1

3-Connected Graphs

Let G=(V, E) be a 3-connected graph. Assume for the most of this section that ∀i, p(i)=±1 and
p(V )=0 (we will state the results for general p at the end). We show that G has a partition that is
essentially perfect with respect to both objectives, i.e., with cp =0 and cs =1. We say “essentially”,
4

because p(V1 )=p(V2 )=0 and |V1 |=|V2 | imply that |V1 |=|V2 | are even, and hence V must be a
multiple of 4. If this is the case, then indeed we can find such a perfect partition. If |V |≡2(mod 4)
(|V | has to be even since p(V )=0), then we can find an ‘almost perfect’ partition, one in which
|p(V1 )|=|p(V2 )|=1 and |V1 |=|V2 | (or one in which p(V1 )=p(V2 )=0 and |V1 |=|V2 |+2).
We first treat the case that G contains a triangle (i.e., cycle of length 3). In the following Lemma,
we use the embedding for k-connected graphs introduced in [12] and as described in Subsection A.6,
to show that if G is 3-connected with a triangle and all weights are ±1, then the DBCP problem
has a perfect solution.
Lemma 1. If G is 3-connected with a triangle, ∀i, p(i)=±1, and |V |≡0(mod 4), then there exists a
solution to the DBCP problem with p(V1 )=p(V2 )=0 and |V1 |=|V2 |. If |V |≡2(mod 4), then there is a
solution with p(V1 )=p(V2 )=0 and |V1 |=|V2 |+2. Moreover, this partition can be found in polynomial
time.
Proof. Assume that |V |≡0(mod 4); the proof for the case |V |≡2(mod 4) is similar. In [12] as
described in Subsection A.6, it is proved that if G is a k-connected graph, then for every X⊂V
with |X|=k, G has a convex X-embedding in general position. Moreover, this embedding can be
found by solving a set of linear equations of size |V |. Now, assume v, u, w∈V form a triangle in G.
Set X={v, u, w}. Using the theorem, G has a convex X-embedding f :V →R2 in general position.
Consider a circle C around the triangle f (u), f (v), f (w) in R2 as shown in an example in Fig. 2.
Also consider a directed line L tangent to the circle C at point A. If we project the nodes of G
onto the line L, since the embedding is convex and also {u, v}, {u, w}, {w, v}∈E, the order of the
nodes’ projection gives an st-numbering between the first and the last node (notice that the first
and last nodes are always from the set X). For instance in Fig. 2, the order of projections give an
st-numbering between the nodes u and v in G. Hence, if we set V1 to be the |V |/2 nodes whose
projections come first and V2 are the |V |/2 nodes whose projections come last, then G[V1 ] and G[V2 ]
are both connected and |V1 |=|V2 |=|V |/2. The only thing that may not match is p(V1 ) and p(V2 ).
Notice that for each directed line tangent to the circle C, we can similarly get a partition such that
|V1 |=|V2 |=|V |/2. So all we need is a point D on the circle C such that if we partition based on the
directed line tangent to C at point D, then p(V1 )=p(V2 )=0. To find such a point, we move L from
being tangent at point A to point B (AB is a diameter of the circle C) and consider the resulting
partition. Notice that if at point A, p(V1 )>0, then at point B since V1 and V2 completely switch
places compared to the partition at point A, p(V1 )<0. Hence, as we move L from being tangent at
point A to point B and keep it tangent to the circle, in the resulting partitions, p(V1 ) goes from
some positive value to a non-positive value. Notice that the partition (V1 , V2 ) changes only if L
passes a point D on the circle such that at D, L is perpendicular to a line that connects f (i) to
f (j) for some i, j∈V . Now, since the embedding is in general position, there are exactly two points
on every line that connects two points f (i) and f (j), so V1 changes at most by one node leaving V1
and one node entering V1 at each step as we move L. Hence, p(V1 ) changes by either ±2 or 0 value
at each change. Now, since |V |≡0(mod 4), p(V1 ) has an even value in all the resulting partitions.
Therefore, as we move L from being tangent at point A to point B, there must be a point D such
that in the resulted partition p(V1 )=p(V2 )=0.
It is also easy to see that since V1 may change only when a line that passes through 2 nodes of
graph G is perpendicular to L, we can find D in at most O(|V |2 ) steps.
When G is a triangle-free 3-connected graph, however, the proof in Lemma 1 cannot be directly
used anymore. The reason is if for example {u, v}∈E
/ and we project the nodes of G onto the line
L, this time the order of the nodes projection does not give an st-numbering between the first and
the last node if for example u and w are the first and last node, since some of the middle nodes may
5

𝑉2

𝑉1
𝑢′

ℒ

𝑤′

𝑣′

𝐴

𝑤

𝒞

𝑢

𝑣

𝐵

Figure 2: Proof of Lemma 1.
only be connected to v. To prove a similar result for triangle-free 3-connected case, we first provide
the following two Lemmas. The main purpose of the following two Lemmas are to compensate for
the triangle-freeness of G in the proof of Lemma 1. The idea is to show that in every 3-connected
graph, there is a triple {u, w, v}∈V , such that {u, w}, {w, v}∈E and in every partition that we get
by the approach used in the proof of Lemma 1, if u and v are in Vi , so is a path between u and v.
Lemma 2. If G is 3-connected, then there exists a set {u, v, w}∈V and a partition of V into
(V10 , V20 ) such that:
1. V10 ∩V20 =∅ and V10 ∪V20 =V ,
2. G[V10 ] and G[V20 ] are connected,
3. {u, w}, {v, w}∈E,
4. w∈V10 , u, v∈V20 ,
5. |V20 |≤|V |/2.
Moreover, such a partition and {u, v, w} can be found in O(|E|) time.
Proof. Using the algorithm presented in [4], we can find a non-separating cycle C0 in G such that
every node in C0 has a neighbor in G\C0 . Now, we consider two cases:
(i) If |C0 |≤|V |/2+1, then select any three consecutive nodes (u, w, v) of C0 and set V20 =C0 \{w}
and V10 =V \V20 .
(ii) If |C0 |>|V |/2+1, since every node in C0 has a neighbor in G\C0 , there exists a node w∈V \C0
such that |N (w)∩C0 |≥2. Select two nodes u, v∈N (w)∩C0 . There exists a path P in C0
between u and v such that |P |<|V |/2−1. Set V20 ={u, v}∪P and V10 =V \V20 .
Lemma 3. Given a partition (V10 , V20 ) of a 3-connected graph G with properties described in
Lemma 2, G has a convex X-embedding in general position with mapping f :V →R2 such that:
1. X={u, w, v}, f (u)=(0, 0), f (v)=(1, 0), and f (w)=(0, 1),
2. Every node i in V10 is mapped to a point (f1 (i), f2 (i)) with f2 (i)≥1/2,
3. Every node i in V20 is mapped to a point (f1 (i), f2 (i)) with f1 (i)≥f2 (i) and f1 (i)+2f2 (i)≤1.
6

ℒ

𝐴

𝑤

ℒ3

(0,1)

ℒ2

ℒ1
𝒞

𝑉1 ′
(0.5,0.5)

(0,0.5)

𝑉2 ′
(0,0)

(1,0)

𝑣

𝑢
𝐵

Figure 3: Proof of Lemma 3 and Theorem 1.
Moreover, such an embedding can be found in in polynomial time.
Sketch of the proof. Set X={v, u, w}. Using [12], G has a convex X-embedding in R2 in general
position with mapping f :V →R2 such that f (u)=(0, 0), f (v)=(1, 0), and f (w)=(0, 1). In the Xembedding of the nodes, we have a freedom to set the elasticity coefficient vector ~c to anything that
we want (except a measure zero set of vectors). So for any edge {i, j}∈G[V1 ]∪G[V2 ], set cij =g; and
for any {i, j}∈E[V10 , V20 ], set cij =1. Since both G[V10 ] and G[V20 ] are connected, as we increase g,
nodes in V10 get closer to w and nodes in V20 get closer to the line uv (as g→∞, nodes in V10 get in
the same position as w and node in V20 get on the line uv). Hence, intuitively there exists a value
g, for which all the nodes in V1 are above line L1 and all the nodes in V20 are below the lines L2
and L3 as depicted in Fig. 3. In the appendix we give the detailed proof and show that a g with
polynomially many bits suffices.
Using Lemmas 2 and 3, we are now able to prove that for any 3-connected graph G such that
all the weights are ±1, the DBCP problem has a solution for cp =0 and cs =1. The idea of the proof
is similar to the proof of Lemma 1, however, we need to use Lemma 2 to find a desirable partition
(V10 , V20 ) and then use this partition to find an embedding with properties as described in Lemma 3.
By using this embedding, we can show that in every partition that we obtain by the approach in
the proof of Lemma 1, if u and v are in Vi , so is a path between u and v. This implies then that
G[V1 ] and G[V2 ] are connected. So we can use similar arguments as in the proof of Lemma 1 to
prove the following theorem (see the Appendix C for the proof details).
Theorem 1. If G is 3-connected, ∀i, p(i)=±1, and |V |≡0(mod 4), then there exists a solution to
the DBCP problem with p(V1 )=p(V2 )=0 and |V1 |=|V2 |. If |V |≡2(mod 4), then there is a solution
with p(V1 )=p(V2 )=0 and |V1 |=|V2 |+2. Moreover, this partition can be found in polynomial time.
It is easy to check for a 3-connected graph G, by using the same approach as in the proof of
Lemma 1 and Theorem 1, that even when the weights are arbitrary (not necessarily ±1) and also
p(V )6=0, we can still find a connected partition (V1 , V2 ) for G such that |p(V1 )−p(V )/2|, |p(V1 )−
p(V )/2|≤maxi∈V |p(i)| and |V1 |=|V2 |.
Corollary 1. If G is 3-connected, then the DBCP problem (with arbitrary p, and not necessarily
satisfying p(V )=0) has a solution for cp =maxi∈V |p(i)| and cs =1. Moreover, this solution can be
found in polynomial time.

7

3.2

2-Connected Graphs

We first define a pseudo-path between two nodes in a graph as below. The definition is inspired by
the definition of the st-numbering.
Definition 3. A pseudo-path between nodes u and v in G=(V, E), is a sequence of nodes v1 , . . . , vt
such that if v0 =u and vt+1 =v, then for any 1≤i≤t, vi has neighbors vj and vk such that j<i<k.
Using the pseudo-path notion, in the following lemma we show that if G is 2-connected and
has a separation pair such that none of the resulting components are too large, then the DBCP
problem always has a solution for some cp =cs =O(1). The idea used in the proof of this lemma is
one of the building blocks of the proof for the general 2-connected graph case.
Lemma 4. Given a 2-connected graph G and an integer q>1, if ∀i:p(i)=±1 and G has a separation pair {u, v}⊂V such that for every connected component Gi =(Vi , Ei ) of G[V \{u, v}], |Vi |<
(q−1)|V |/q, then the DBCP problem has a solution for cp =1, cs =q−1, and it can be found in
O(|E|) time.
Proof. Assume for simplicity that |V | is divisible by q. There is a separation pair {u, v}∈V such
that if G1 , . . . , Gk are the connected components of G\{u, v}, for any i, |Vi |<(q−1)|V |/q. Since G
is 2-connected, G1 , . . . , Gk can be presented by pseudo-paths P1 , . . . , Pk between u and v. Assume
P1 , . . . , Pk are in increasing order based on their lengths. There exists
two subsets of the pseudoP
paths S1 and S2 such that S1 ∩S2 =∅, S1 ∪S2 ={P1 , . . . , Pk } and Pj ∈Si |Pj |≥|V |/q−1 for i=1, 2.
The proof is very simple. If |Pk |<|V |/q, the greedy algorithm for the partition problem gives the
desired partition of {P1 , . . . , Pk }. If |Pk |≥|V |/q, since |Pk |<(q−1)|V |/q, S1 ={P1 , . . . , Pk−1 } and
S2 ={Pk } is the desired partition.
Now, if we put all the pseudo-paths in S1 back to back, they will form a longer pseudo-path Q1
between u and v. Similarly, we can form another pseudo-path Q2 from the paths in S2 . Without
loss of generality we can assume |Q1 |≥|Q2 |. From u, including u itself, we count |V |/q of the nodes
in Q1 towards v and put them in a set V 0 . Without loss of generality, we can assume p(V 0 )≥0.
If p(V 0 )=0, then (V 0 , V \V 0 ) is a good partition and we are done. Hence, assume p(V 0 )>0. We
keep V 0 fixed and make a new set V 00 by continuing to add nodes from Q1 to V 0 one by one until
we get to v. If p(V 00 ) hits 0 as we add nodes one by one, we stop and (V 00 , V \V 00 ) is a good
partition and we are done. So, assume V 00 =Q1 ∪{u} and p(V 00 )>0. Since |Q2 ∪{v}|≥|V |/q, |V 00 |≤
(q−1)|V |/q. If |V 00 |<(q−1)|V |/q, we add nodes from Q2 one by one toward u until either |V 00 |=0
or |V 00 |=(q−1)|V |/q. If we hit 0 first (i.e., p(V 00 )=0) and |V 00 |≤(q−1)|V |/q, define V1 =V 00 \{u},
then (V1 , V \V1 ) is a good partition. So assume |V 00 |=(q−1)|V |/q and p(V 00 )>0. Define V 000 =V \V 00 .
Since p(V 00 )>0 and |V 00 |=(q−1)|V |/q, then p(V 000 )<0 and |V 000 |=|V |/q. Also notice that V 000 ⊆Q2 .
We consider two cases. Either |p(V 0 )|≥|p(V 000 )| or |p(V 0 )|<|p(V 000 )|.
If |p(V 0 )|≥|p(V 000 )|, then if we start from u and pick nodes one by one from Q1 in order, we can
get a subset V10 of V 0 such that |p(V10 )|=|p(V 000 )|. Hence, if we define V1 =V10 ∪V 000 , then (V1 , V \V1 )
is a good partition.
If |p(V 0 )|<|p(V 000 )|, then we can build a new set V1 by adding nodes one by one from Q2 to V 0
until P (V1 )=0. It is easy to see that since |p(V 0 )|<|p(V 000 )|, then V1 \V 0 ⊆V 000 . Hence, (V1 , V \V1 ) is
a good partition.
Corollary 2. If G is a 2-connected series-parallel graph and ∀i:p(i)=±1, then the DBCP problem
has a solution for cp =1, cs =2, and the solution can be found in O(|E|) time.
The graph in Figure 1 with s=1 shows that these parameters are the best possible for series
parallel graphs: if cp =O(1) then cs must be at least 2.
8

𝑣1

𝑣3

𝑣4

𝑣5

𝑣2

𝐺1

𝑣3

𝑣6

𝐺2
𝐺3

𝑣7

𝑣7

𝐺
(a)
𝑣1

𝑣13
𝑣12
𝑣11

𝑣2
𝑣3
𝑣4

𝑣7

𝑣8
𝑣9

𝑣5

𝑣4

𝑣10

𝑣14 𝑣15

𝑣1

𝑣13
𝑣12
𝑣11

𝑣2
𝑣3

𝑣13
𝑣12
𝑣11

3
𝑣7

𝑣7

3

3
𝑣6

𝐺

𝑣1

𝑣5

𝑣6
𝑣14 𝑣15

𝑣5

𝑣6
𝑣14 𝑣15

𝐺∗

(b)

Figure 4: Lemma 5.
To generalize Lemma 4 to all 2-connected graphs, we need to define the contractible subgraph
and the contraction of a given graph as below.
Definition 4. We say an induced subgraph G1 of a 2-connected graph G is contractible, if there
is a separating pair {u, v}⊂V such that G1 =(V1 , E1 ) is a connected component of G[V \{u, v}].
Moreover, if we replace G1 by a weighted edge e0 with weight w(e0 )=|V1 | between the nodes u and v
in G to obtain a smaller graph G0 , we say G is contracted to G0 .
Remark. Notice that every contractible subgraph of a 2-connected graph G can also be represented
by a pseudo-path between its associated separating pair. We use this property in the proof of Theorem 2.
Using the notion of the graph contraction, in the following lemma, we show that to partition
a 2-connected graph, we can reduce it to one of two cases: either G can be considered as a graph
with a set of short pseudo-paths between two nodes, or it can be contracted into a 3-connected
graph as illustrated in Fig. 4.
Lemma 5. In every 2-connected graph G=(V, E), given an integer q≥3, one of the following cases
holds, and we can determine which in O(|E|) time:
1. There is a separation pair {u, v}⊂V such that if G1 , . . . , Gk are the connected components of
G[V \{u, v}], for all i, |Vi |<(q−1)|V |/q.
2. After a set of contractions, G can be transformed into a 3-connected graph G∗ =(V ∗ , E ∗ ) with
weighted edges representing contracted subgraphs such that for every e∗ ∈E ∗ , w(e∗ )<|V |/q.
Proof. If there is no separation pairs in G, then G is 3-connected and there is nothing left to
prove. So assume {u, v}⊂V is a separation pair and G1 , . . . , Gk are the connected components of
G[V \{u, v}]. If ∀i, |Vi |<(q−1)|V |/q, we are done. So let’s assume there is a connected component
9

Gj such that |Vj |≥(q−1)|V |/q. Then for every i6=j, Gi can be contracted and represented by an
edge of weight less than |V |/q between u and v. Now, we repeat the process by considering the
weight of the edges in the size of each connected component. An example for each case is shown in
Fig. 4 for q=3. We can find either a suitable separation pair as in case 1 or a suitable contracted
graph G∗ as in case 2 in linear time using the Hopcroft-Tarjan algorithm for finding the triconnected
components [10].
Using Lemma 5 for q=4, then Lemma 4, and the idea of the proof for Theorem 1, we can
prove that when G is 2-connected and all p(i)=±1, the DBCP problem has a solution for cp =1 and
cs =3. There are some subtleties in adapting Lemma 2 for this case to account for the fact that the
edges of G∗ are now weighted, and the partition (V10 , V20 ) has to take into account the edge weights.
We find a suitable convex embedding of the 3-connected graph G∗ and then embed the nodes of
the contracted pseudopaths appropriately along the segments corresponding to the weighted edges.
Some care is needed to carry out the argument of the 3-connected case, since as the line tangent to
the circle rotates, the order of the projections of many nodes may change at once, namely the nodes
on an edge perpendicular to the rotating line. The details of the proof are given in Appendix C.
We have:
Theorem 2. If G is 2-connected, ∀i, p(i)=±1, then the DBCP problem has a solution for cp =1
and cs =3. Moreover, this solution can be found in polynomial time.
Similar to Corollary 1, the approach used in the proof of Theorem 2, can also be used for the
case when the weights are arbitrary (not necessarily ±1) and p(V )6=0. It is easy to verify that
in this case, if G is 2-connected, the DBCP problem has a connected partition (V1 , V2 ) such that
|p(V1 )−p(V )/2|, |p(V2 )−p(V )/2|≤maxj∈V |p(j)| and |V1 |, |V2 |≥|V |/4.
Corollary 3. If G is 2-connected, then the DBCP problem (with general p and not necessarily
satisfying p(V )=0) has a solution for cp =maxj∈V |p(j)| and cs =3. Moreover, this solution can be
found in polynomial time.

4

Graphs with Two Types of Nodes

Assume G is a connected graph with nodes colored either red (R⊆V ) or blue (B⊆V ). Let |V |=n,
|R|=nr , and |B|=nb . If G is 3-connected, set p(i)=1 if i∈R and p(i)=−1 if i∈B. Corollary 1 implies
then that there is always a connected partition (V1 , V2 ) of V that splits both the blue and the red
nodes evenly (assuming nr and nb are both even), i.e., such that |V1 |=|V2 |, |R∩V1 |=|R∩V2 |, and
|B∩V1 |=|B∩V2 |. (If nr and/or nb are not even, then one side will contain one more red or blue
node.)
Corollary 4. Given a 3-connected graph G with nodes colored either red (R⊆V ) or blue (B⊆
V ). There is always a partition (V1 , V2 ) of V such that G[V1 ] and G[V2 ] are connected, |V1 |=|V2 |,
|R∩V1 |=|R∩V2 |, and |B∩V1 |=|B∩V2 | (assuming |R| and |B| are both even). Such a partition can
be computed in polynomial time.
If G is only 2-connected, we may not always get a perfect partition. Assume wlog that nr ≤nb .
If for every v∈R and u∈B, we set p(v)=1 and p(u)=−nr /nb , Corollary 3 implies that there is
always a connected partition (V1 , V2 ) of V such that both |(|R∩V1 |−nr /nb |B∩V1 |)|≤1 and |(|R∩
1 | |V2 |
V2 |−nr /nb |B∩V2 |)|≤1, and also max{ |V
|V2 | , |V1 | }≤3. Thus, the ratio of red to blue nodes in each side
Vi differs from the ratio nr /nb in the whole graph by O(1/n). Hence if the numbers of red and blue
nodes are ω(1), then the two types are presented in both sides of the partition in approximately
the same proportion as in the whole graph.
10

Corollary 5. Given a 2-connected graph G with nodes colored either red (R⊆V ) or blue (B⊆V ),
and assume wlog |R|≤|B|. We can always find in polynomial time a partition (V1 , V2 ) of V such
that G[V1 ] and G[V2 ] are connected, |V1 |, |V2 |≥|V |/4, and the ratio of red to blue nodes in each side
Vi differs from the ratio |R|/|B| in the whole graph by O(1/n).

5

Conclusion

In this paper, we introduced and studied the problem of partitioning a graph into two connected
subgraphs that satisfy simultaneouly two objectives: (1) they balance the supply and demand within
each side of the partition (or more generally, for the case of p(V )6=0, they split approximately equally
the excess supply/demand between the two sides), and (2) the two sides are large and have roughly
comparable size (they are both Ω(|V |)). We showed that for 2-connected graphs it is always possible
to achieve both objectives at the same time, and for 3-connected graphs there is a partition that is
essentially perfectly balanced in both objectives. Furthermore, these partitions can be computed
in polynomial time. This is a paradigmatic bi-objective balancing problem. We observed how it
can be easily used to find a connected partition of a graph with two types of nodes that is balanced
with respect to the sizes of both types. Overall, we believe that the novel techniques used in this
paper can be applied to partitioning heterogeneous networks in various contexts.
There are several interesting further directions that suggest themselves. First, extend the theory
and algorithms to find doubly balanced connected partitions to more than two parts. Second,
even considering only the supply/demand objective, does the analogue of the results of Lováz and
Gyori [9,13] for the connected k-way partitioning of k-connected graphs with respect to size (which
corresponds to p(i)=1) extend to the supply/demand case (p(i)=±1) for k>3? And is there a
polynomial algorithm that constructs such a partition? Finally, extend the results of Section 4 to
graphs with more than two types of nodes, that is, can we partition (under suitable conditions)
a graph with several types of nodes to two (or more) large connected subgraphs that preserve
approximately the diversity (the proportions of the types) of the whole population?

11

A

Definitions and Background

In this section, we provide a short overview of the definitions and tools used in our work. Most
of the graph theoretical terms used in this paper are relatively standard and borrowed from [2]
and [21]. All the graphs in this paper are loopless.

A.1

Terms from Graph Theory

Cutpoints and Subgraphs: A cutpoint of a connected graph G is a node whose deletion results
in a disconnected graph. Let X and Y be subsets of the nodes of a graph G. G[X] denotes the
subgraph of G induced by X. We denote by E[X, Y ] the set of edges of G with one end in X and
the other end in Y . The neighborhood of a node v is denoted N (v).
Connectivity: The connectivity of a graph G=(V, E) is the minimum size of a set S⊂V such that
G\S is not connected. A graph is k-connected if its connectivity is at least k.

A.2

st-numbering of a Graph

Given any edge {s, t} in a 2-connected graph G, an st-numbering for G is a numbering for the nodes
in G defined as follows [11]: the nodes of G are numbered from 1 to n so that s receives number 1,
node t receives number n, and every node except s and t is adjacent both to a lower-numbered and
to a higher-numbered node. It is shown in [7] that such a numbering can be found in O(|V |+|E|).

A.3

Series-Parallel Graphs

A Graph G is series-parallel, with terminals s and t, if it can be produced by a sequence of the
following operations:
1. Create a new graph, consisting of a single edge between s and t.
2. Given two series parallel graphs, X and Y with terminals sX , tX and sY , tY respectively,
form a new graph G=P (X, Y ) by identifying s=sX =sY and t=tX =tY . This is known as the
parallel composition of X and Y .
3. Given two series parallel graphs X and Y , with terminals sX , tX and sY , tY respectively, form
a new graph G=S(X, Y ) by identifying s=sX , tX =sY and t=tY . This is known as the series
composition of X and Y .
It is easy to see that a series-parallel graph is 2-connected if, and only if, the last operation is a
parallel composition.

A.4

Nonseparating Induced Cycles and Ear Decomposition

Let H be a subgraph of a graph G. An ear of H in G is a nontrivial path in G whose ends lie in H
but whose internal vertices do not. An ear decomposition of G is a decomposition G=P0 ∪· · ·∪Pk of
the edges of G such that P0 is a cycle and Pi for i≥1 is an ear of P0 ∪P1 ∪· · ·∪Pi−1 in G. It is known
that every 2-connected graph has an ear decomposition (and vice-versa), and such a decomposition
can be found in linear time.
A cycle C is a nonseparating induced cycle of G if G\C is connected and C has no chords. We
say a cycle C avoids a node u, if u∈C.
/

12

Theorem 3 (Tutte [19]). Given a 3-connected graph G(V, E) let {t, r} be any edge of G and let
u be any node of G, r6=u6=t. Then there is a nonseparating induced cycle of G through {t, r} and
avoiding u.
Notice that since G is 3-connected in the previous theorem, every node in C has a neighbor in
G\C. Cheriyan and Maheshwari showed that the cycle in Theorem 3 can be found in O(E) [4].
Moreover, they showed that any 3-connected graph G has a nonseparating ear decomposition
G=P0 ∪· · ·∪Pk defined as follows: Let Vi =V (P0 )∪V (P1 ) · · ·∪V (Pi ), let Gi =G[Vi ] and Gi =G[V \Vi ].
We say that G=P0 ∪P1 ∪· · ·∪Pk is an ear decomposition through edge {t, r} and avoiding vertex u
if the cycle P0 contains edge {t, r}, and the last ear of length greater than one, say Pm , has u as
its only internal vertex. An ear decomposition P0 ∪P1 · · ·∪Pk of graph G through edge {t, r} and
avoiding vertex u is a nonseparating ear decomposition if for all i, 0≤i<m, graph Gi is connected
and each internal vertex of ear Pi has a neighbor in Gi .
Theorem 4 (Cheriyan and Maheshwari [4]). Given an edge {t, r} and a vertex u of a 3-connected
graph G, a nonseparating induced cycle of G through {t, r} and avoiding u, and a nonseparating
ear decomposition can be found in time O(|V |+|E|).

A.5

Partitioning of Graphs to Connected Subgraphs

The following theorem is the main existing result in partitioning of graphs into connected subgraphs
and is proved independently by Lováz and Gyori [9, 13] by different methods.
Theorem 5 (Lováz and Gyori [9,13]). Let G=(V, E) be a k-connected graph. Let n=|V |, v1 , v2 , . . . , vk ∈
V and let n1 , n2 , . . . , nk be positive integers satisfying n1 +n2 +· · ·+nk =n. Then, there exists a partition of V into (V1 , V2 . . . , Vk ) satisfying vi ∈Vi , |Vi |=ni , and G[Vi ] is connected for i=1, 2, . . . , k.
Although the existence of such a partition has long been proved, there is no polynomial-time
algorithm to find such a partition for k>3. For k=2, it is easy to find such partition using stnumbering. For k=3, Wada and Kawaguchi [20] provided an O(n2 ) algorithm using the nonseparating ear decomposition of 3-connected graph.

A.6

Convex Embedding of Graphs

In this subsection, we provide a short overview of the beautiful work by Linial, Lováz, and Wigderson [12] on convex embedding of the k-connected graphs. Let Q={q1 ,P
q2 , . . . , qm } be P
a finite set
of points in Rd . The convex hull conv(Q) of Q is the set of all points m
λ
q
with
i=1 i i
i=1 λi =1.
The rank of Q is defined by rank(Q)=1+dim(conv(Q)). Q is in general position if rank(S)=d+1
for every (d+1)-subset S⊆Q. Let G be a graph and X⊂V . A convex X-embedding of G is any
mapping f :V →R|X|−1 such that for each v∈V \X, f (v)∈conv(f (N (v))). We say that the convex
embedding is in general position if the set f (V ) of the points is in general position.
Theorem 6 (Linial, Lováz, and Wigderson [12]). Let G be a graph on n vertices and 1<k<n.
Then the following two conditions are equivalent:
1. G is k-connected
2. For every X⊂V with |X|=k, G has a convex X-embedding in general position.
Notice that the special case of the Theorem for k=2 asserts the existence of an st-numbering
of a 2-connected graph. The proof of this theorem is inspired by physics. The embedding is
13

found by letting the edges of the graph behave like ideal springs and letting its vertices settle. A
formal summary of the proof (1→2) is as follows (for more details see [12]). For each vi ∈X, define
f (vi ) arbitrary in Rk−1 such that f (X) is in general position. Assign to every edge (u, v)∈E a
positive elasticity coefficient cuv and let c∈R|E| be the vector of coefficients. It is proved in [12]
that
vector c, an embedding f that minimizes the potential function P =
P for almost any coefficient
2 provides a convex X-embedding in general position (k.k is the Euclidean
c
kf
(u)−f
(v)k
{u,v}∈E uv
norm). Moreover, the embedding that minimizes P can be computed as follows,
f (v)=

1 X
cuv f (u) for all v∈V \X,
cv
u∈N (v)

P
in which cv = u∈N (v) cuv . Hence, the embedding can be found by solving a set of linear equations
in at most O(|V |3 ) time (or matrix multiplication time).

B

Missing Proofs from Section 2

Proof of Proposition 1. We use the proof of [3, Theorem 2] with a modest change. The reduction is
from the X3C problem [15], which is a variant of the Exact Cover by 3-sets and defined as follows:
Given a set X with |X|=3q and a family C of 3-element subsets of X such that |C|=3q and each
element of X appears in exactly 3 sets of C, decide whether C contains an exact cover for X. Given
an instance
set V =X∪C∪{a, b} and edge
S (X, C) of X3C, let G=(V, E) be the graph with the vertex
2 +q, p(C )=−1, and p(x )=−3q.
set E= 3q
[{C
x
|x
∈C
}∪{C
a}∪{C
b}].
Set
p(a)=2q,
p(b)=9q
j i i
j
j
j
j
i
j=1
It is easy to verify that C contains an exact cover for X if and only if the BCPI problem has a
solution such that p(V1 )=p(V2 )=0. This shows the first claim.
For the second claim, attach to nodes a, b, and the xi s, paths of length 2q, 9q 2 +q, and 3q,
respectively, and set the supply/demand values of a, b, the xi ’s and the new nodes equal to +1 (for
the paths for a and b) or −1 (for the xi ’s).
Proof of Proposition 2. Clearly, part (2) follows immediately from part (1) because in this case,
p(V1 ), p(V2 ) are integer and maxj∈V |p(j)|/2=1/2. To show part (1), pick two arbitrary nodes
u, v∈V with p(u)p(v)>0. Since we want to separate u and v, we can assume wlog that initially
{u, v}∈G. Since G is 2-connected, an st-numbering between nodes u and v as u=v1 , v2 , . . . , vn =v
(i)
(1)
can be found in O(|V |+|E|) [7]. Define V1 :={v1 , v2 , . . . , vi }. It is easy to see that p(V1 )=p(u)>0
(n−1)
(i∗ )
and p(V1
)=−p(v)<0. Hence, there must exist an index 1≤i∗ <n such that |p(V1 )|>0 and
(i∗ +1)
(i)
(i+1)
(i∗ )
(i∗ +1)
|p(V1
)|≤0. Since |p(V1 )−p(V1
)|=|p(i∗ +1)|, either |p(V1 )|≤|p(i∗ +1)|/2 or |p(V1
)|≤
(i∗ )
(i∗ +1)
∗
|p(i +1)|/2; Accordingly set V1 =V1
or V1 =V1
. Let V2 =V \V1 . Hence, (V1 , V2 ) is a solution
∗
with |p(V1 )|=|p(V2 )|≤|p(i +1)/2|≤maxj∈V |p(j)|/2. It is easy to see that i∗ can be found in O(|V |).

Proof of Proposition 3. Consider the case of general function p, and let pmax =maxj∈V |p(j)|. We
will show that we can find a solution such that u∈V1 , v∈V2 , w∈V3 with |p(V1 )|, |p(V2 )|≤pmax /2. Since
|p(V3 )|=|p(V1 )+p(V2 )| (recall p(V )=0), this implies that |p(V3 )|≤pmax , and hence |p(V1 )|+|p(V2 )|+
|p(V3 )|≤2pmax . Furthermore, if p(i)=±1 for all i∈V , hence pmax =1, then |p(V1 )|, |p(V2 )|≤pmax /2
implies that p(V1 )=p(V2 )=0, and therefore also p(V3 )=0. Thus, both claims will follow.
Assume u, v, w∈V and p(u), p(v), p(w)>0 (the case of negative p(u), p(v), p(w) is symmetric).
Since we want to separate u from v, we can assume without loss of generality that {u, v}∈E.
14

Using [4], there is a non-separating ear decomposition through the edge {u, v} and avoiding node w.
Ignore the ears that do not contain any internal nodes, and let Q0 ∪Q1 ∪· · ·∪Qr be the decomposition
consisting of the ears with nodes; we have w∈Qr . Let Vi =V (Q0 )∪V (Q1 ) · · ·∪V (Qi ), let Gi =G[Vi ]
and Gi =G[V \Vi ]. We distinguish two cases, depending on whether p(V0 )≤0 or p(V0 )>0.
(i) If p(V0 )≤0, then consider an st-numbering between u and v in V0 , say u=v1 , v2 , . . . , vs =v.
(i)
Define V0 ={v1 , v2 , . . . , vi }. Since p(u), p(v)>0 and p(V0 )≤0, there must exist indices 1≤i∗ ≤
(i∗ )
(i∗ +1)
(j ∗ +1)
(j ∗ )
j ∗ <s such that p(V0 )>0, p(V0
)≤0 and p(V0 \V0
)>0, p(V0 \V0 )≤0.
(i∗ )

(i∗ +1)

(i∗ )

(a) If i∗ =j ∗ , since p(V0 )+p(vi∗ +1 )+p(V0 \V0
)=p(V0 )<0, we have p(V0
|p(vi∗ +1 )|. Now, one of the following three cases happens:
(i∗ )

(i∗ +1)

)+p(V0 \V0

)≤

(i∗ +1)

- If p(V0 )≤|p(vi∗ +1 )|/2 and p(V0 \V0
)≤|p(vi∗ +1 )|/2, then it is easy to see that
(i∗ )
(i∗ +1)
V1 =V0 , V2 =V0 \V0
, and V3 =V \(V1 ∪V2 ) is a good partition.
(i∗ )

(i∗ +1)

(i∗ )

- If p(V0 )>|p(vi∗ +1 )|/2 and p(V0 \V0
)≤|p(vi∗ +1 )|/2, then p(V0 )+p(vi∗ +1 )=
(i∗ +1)
(i∗ +1)
(i∗ +1)
∗
p(V0
)≤|p(vi +1 )|/2. Hence, V1 =V0
, V2 =V0 \V0
, and V3 =V \V0 is a good
partition.
(i∗ )

(i∗ +1)

(i∗ +1)

- If p(V0 )≤|p(vi∗ +1 )|/2 and p(V0 \V0
)>|p(vi∗ +1 )|/2, then p(V0 \V0
)+p(vi∗ +1 )=
(i∗ )
(i∗ )
(i∗ )
p(V0 \V0 )≤|p(vi∗ +1 )|/2. Hence, V1 =V0 , V2 =V0 \V0 , and V3 =V \V0 is a good
partition.
(i∗ )

(i∗ +1)

(b) If i∗ <j ∗ , then either p(V0 )≤|p(vi∗ +1 )|/2 or |p(V0
)|≤|p(vi∗ +1 )|/2, accordingly set
(i∗ )
(i∗ +1)
(j ∗ +1)
(j ∗ )
V1 =V0 or V1 =V0
. Similarly, either p(V0 \V0
)≤|p(vj ∗ +1 )|/2 or |p(V0 \V0 )|≤
(j ∗ +1)
(j ∗ )
|p(vj ∗ +1 )|/2, so accordingly set V2 =V0 \V0
or V2 =V0 \V0 . Set V3 =V \(V1 ∪V2 ). It
is easy to check that (V1 , V2 , V3 ) is a good partition.
(ii) If p(V0 )>0, then since p(w)>0 and therefore p(Vr−1 )<0, there must exist an index 0≤j<r−1
such that p(Vj )>0 and p(Vj+1 )≤0. Consider an st-numbering between u and v in G[Vj ]
(i)
as u=v1 , v2 , . . . , vs =v and define Vj ={v1 , v2 , . . . , vi }. The ear Qj+1 is a path of new nodes
q1 , q2 , . . . , qt attached to two (distinct) nodes vx , vy of G[Vj ] through edges {vx , q1 }, {qt , vy }∈E;
assume wlog that 1≤x<y≤s. For simplicity, we will use below Qj+1 to denote also the
(i)
set {q1 , q2 , . . . , qt } of internal (new) nodes of the ear. Also define Qj+1 ={q1 , q2 , . . . , qi } and
(0)

Qj+1 =∅. One of the following cases must happen:
(i∗ )

(a) Suppose there is an index 1≤i∗ <(y−1) such that p(Vj

(i∗ +1)

)>0 and p(Vj

)≤0 or there is

(i∗ −1)
(i∗ )
an index
such that p(Vj \Vj
)>0 and p(Vj \Vj )≤0. Let’s assume there is
(i∗ )
(i∗ +1)
an index 1≤i∗ <(y−1), such that p(Vj )>0 and p(Vj
)≤0 (the other case is exactly
(i∗ )
(i∗ +1)
similar). Then either p(Vj )≤|p(vi∗ +1 )|/2 or |p(Vj
)|≤|p(vi∗ +1 )|/2, accordingly set
(i∗ )
(i∗ +1)
0
either V1 =Vj
or V1 =Vj
. Set V2 =Vj \V1 . One of the following cases happens:

x+1<i∗ <s

(i∗ )

(i∗ +1)

(i∗ +1)

- If V1 =Vj and p(V20 )≤0, then since p(Vj
)≤0, we have p(Vj \Vj
)>0. Hence,
0
0
0
p(V2 \{vi∗ +1 })>0. So, it is either |p(V2 )|≤|p(vi∗ +1 )|/2 or p(V2 \{vi∗ +1 })≤|p(vi∗ +1 )|/2.
Now if p(V20 \{vi∗ +1 })≤|p(vi∗ +1 )|/2, since also p(V1 )≤|p(vi∗ +1 )|/2, p(Vj )≤0 which
contradicts with the assumption. Therefore, |p(V20 )|≤|p(vi∗ +1 )|/2. Set V2 =V20 and
V3 =V \(V1 ∪V2 ). It is easy to check that (V1 , V2 , V3 ) is a good partition.
(i∗ )

- If V1 =Vj

and p(V20 )>0, then since p(Vj ∪Qj+1 )<0, there is an index 0<t∗ ≤t,
(t∗ )

(t∗ −1)

such that p(V20 ∪(Qj+1 \Qj+1 ))>0 and p(V20 ∪(Qj+1 \Qj+1 ))≤0. Hence, either p(V20 ∪
15

(t∗ )

(t∗ −1)

(Qj+1 \Qj+1 ))≤|p(qt∗ )|/2 or |p(V20 ∪(Qj+1 \Qj+1 ))|≤|p(qt∗ )|/2, accordingly set V2 =
(t∗ )

(t∗ −1)

V20 ∪(Qj+1 \Qj+1 ) or V2 =V20 ∪(Qj+1 \Qj+1 ). Set V3 =V \(V1 ∪V2 ). It is easy to see
that (V1 , V2 , V3 ) is a good partition.
(i∗ +1)

- If V1 =Vj

, then since p(V1 )≤0, we have p(V20 )>0. The rest is exactly like the
(i∗ )

previous case when V1 =Vj

and p(V20 )>0.
(i)

(i)

(b) Suppose that for every 1≤i<y, p(Vj )>0 and for every x<i<s, p(Vj \Vj )>0. Set
(y−1)

V10 =Vj

and V20 =Vj \V10 . Based on the assumption p(V10 ), p(V20 )>0. Since p(Vj+1 )≤
(i∗ )

(i∗ +1)

0, there are indices 0≤i∗ ≤j ∗ <t such that p(V10 ∪Qj+1 )>0, p(V10 ∪Qj+1 )≤0 and p(V20 ∪
(j ∗ +1)

(j ∗ )

(Qj+1 \Qj+1 ))>0, p(V20 ∪(Qj+1 \Qj+1 ))≤0. The rest of the proof is similar to case (i)
when p(V0 )≤0.

C

Missing Proofs from Section 3

Proof of Lemma 3. Set X={v, u, w}. Using [12], G has a convex X-embedding in R2 in general
position with mapping f :V →R2 such that f (u)=(0, 0), f (v)=(1, 0), and f (w)=(0, 1). In the Xembedding of the nodes, we have a freedom to set the elasticity coefficient vector ~c to anything that
we want (except a measure zero set of vectors). So for any edge {i, j}∈G[V10 ]∪G[V20 ], set cij =g; and
for any {i, j}∈E[V10 , V20 ], set cij =1. Assume L1 is the line y=0.5, L2 is the line x+2y=1, and L3 is
the line x=y.
First, we show that there exist a g for which all the nodes in V10 will be embedded above the line
L1 . To show
P this, from [12], we know the embedding is such that it minimizes the total potential
P (f, ~c)= {i,j}∈E cij kf (i)−f (j)k2 . Notice that we can independently minimize P on x-axis values
and y-axis values as below:
min P
f

= min Px +min Py
f1
f2
X
X
= min
cij (f1 (i)−f1 (j))2 +min
cij (f2 (i)−f2 (j))2
f1

f2

{i,j}∈E

{i,j}∈E

Now, notice that if we place all the nodes in V10 at point (0,1) and all the nodes in V20 on
the line uv, then Py ≤|E|. Hence, if f2 minimizes Py , then Py (f2 , c)≤|E|. Set g≥4|V |2 |E|. We
show that if f2 minimizes Py , then for all edges {i, j}∈G[V10 ]∪G[V20 ], (f2 (i)−f2 (j))2 ≤1/(4|V |2 ).
By contradiction, assume there is an edge {i, j}∈G[V10 ]∪G[V20 ] such that (f2 (i)−f2 (j))2 >1/(4|V |2 ).
Then, cij (f2 (i)−f2 (j))2 =g(f2 (i)−f2 (j))2 >|E|. Hence, Py (f2 , c)>|E| which contradicts with the
fact the f2 minimizes Py . Therefore, if g≥4|V |2 |E|, then for all {i, j}∈G[V10 ]∪G[V20 ], |f2 (i)−f2 (j)|≤
1/(2|V |). Now, since G[V10 ] is connected, all the nodes in V10 are connected to w with a path of
length (in number of hops) less than |V |−1. Hence, using the triangle inequality, for all i∈V10 :
|f2 (w)−f2 (i)|≤(|V |−1)/(2|V |)<1/2⇒|1−f2 (i)|<1/2,
which means that all the nodes in V10 are above L1 .
With the very same argument, if g≥t2 |V |2 |E|, then for all i∈V20 , f2 (i)<1/t.
Now, we want to prove that there is a g such that all the nodes in V20 will be embedded below
the lines L2 and L3 . Define n1 (i):=|N (i)∩V10 | and n2 (i):=|N (i)∩V20 |. From [12], we know the
16

P
P
embedding is such that for all i∈V \{u, v, w}, f (i)=1/ci j∈N (i) cij f (j), where cj = j∈N (i) cij f (j).
Since G[V20 ] is connected, for any i∈V20 there is a path i=v1 , v2 , . . . , vr =v in V20 . Using this ordering:
(
1
f1 (vj )≥ n2 (vj )g+n
gf1 (vj+1 )≥(1/|V |)f1 (vj+1 ), ∀j∈{1, . . . , r−1}
1 (vj )
f1 (vr )=f1 (v)=1
⇒∀i∈V20 \{u, v}: f1 (i)≥(1/|V |)r ≥(1/|V |)|V | .
On the other hand, from the previous part, if we set g≥|V |2|V |+2 |E|, then for all i∈V20 , f2 (i)≤
(1/|V |)|V | . Hence, for all i∈V20 , f2 (i)≤f1 (i), which means that all the nodes in V20 will be placed
below the line L3 .
With the very same idea, we show that there exist a g for which all the nodes in V20 will be placed
below the line L2 . Since G[V20 ] is connected, for P
any i∈V20 there is a path u=u1 , v2 , . . . , ut =i in V20 .
Notice that for all i∈V \{u, v, w}, 1−f1 (i)=1/ci j∈N (i) cij (1−f1 (j)). Hence, since ∀j∈V :f1 (j)≤1,
we have,
(
1
1−f1 (uj )≥ n2 (uj )g+n
g(1−f1 (ui−1 ))≥(1/|V |)(1−f1 (ui−1 )), ∀j∈{2, . . . , t}
1 (uj )
1−f1 (u)=1−f1 (u1 )=1
⇒∀i∈V20 \{u, v}: 1−f1 (i)≥(1/|V |)t ≥(1/|V |)|V | .
From the previous part, if we set g≥4|V |2|V |+2 |E|, then for all i∈V20 , f2 (i)≤1/2(1/|V |)|V | . Hence,
for i∈V20 , f1 (i)+2f2 (i)≤1, which means that all the nodes in V20 will be placed below the line L3 .
Therefore, if we set g≥4|V |2|V |+2 |E|, then we will get an embedding as depicted in Fig. 3. Note
that a polynomial number of bits suffices for g.
Notice that if ~c is a “good” vector, then so is ~c+~ in which ~ is a vector with very small
Euclidean norm. Hence, we can always find a “good” vector ~c which result in a X-embedding in
general position.
Proof of Theorem 1. Assume that |V |≡0(mod 4); the proof for the case |V |≡2(mod 4) is similar.
Using Lemma 2, we can find {u, v, w}∈V and a partition (V10 , V20 ) of V with properties described in
the Lemma. Set X={u, v, w}. Using Lemma 3, we can find a convex X-embedding of G in general
position with properties described in the Lemma as depicted in Fig. 3. The rest of the proof is
very similar to the proof of Lemma 1. We consider again a circle C around f (u), f (v), f (w) in R2
as shown in Fig. 3. Also consider a directed line L tangent to the circle C at point A. If we project
the nodes of G onto the line L, this time the order of the nodes projection gives an st-numbering
between the first and the last node only if u and v are the first and last node. However, if we set V1
to be the |V |/2 nodes whose projections come first and V2 are the |V |/2 nodes whose projections
come last, then G[V1 ] and G[V2 ] are both connected even when u and v are not the first and last
nodes. The reason lies on the special embedding that we considered here. Assume for example w
and v are the first and the last projected nodes, and V1 and V2 are set of the |V |/2 nodes which
projections come first and last, respectively. Two cases might happen:
(i) If u, w∈V1 and v∈V2 , then since {u, w}∈E, both G[V1 ] and G[V2 ] are connected because of
the properties of the embedding.
(ii) If w∈V1 and u, v∈V2 , since |V20 |≤|V |/2 and |V2 |=|V |/2, then either V2 =V20 or V2 ∩V10 6=∅. If
V2 =V20 , and hence V1 =V10 then there is nothing to prove. So assume there is a node z∈V2 ∩V10 .
From the properties of the embedding, the triangle {z, u, v} contains all the nodes of V20 .
17

Since {z, u, v}∈V2 , and V2 contains all the nodes that are on a same side of a halfplane, we
should also have V20 ⊂V2 . Now, from the properties of the embedding, it is easy to see that
every node in V2 has a path either to u or v. Since V20 ⊂V2 , there is also a path between u
and v. Thus, G[V2 ] is connected. From the properties of the embedding, G[V1 ] is connected
as before.
The rest of the proof is exactly the same as the proof of Lemma 1. We move L from being tangent
at point A to point B (AB is a diameter of the circle C) and consider the resulting partition. Notice
that if at point A, p(V1 )>0, then at point B since V1 and V2 completely switch places compared to
the partition at point A, p(V1 )<0. Hence, as we move L from being tangent at point A to point
B and keep it tangent to the circle, in the resulted partitions, p(V1 ) goes from some positive value
to a negative value. Notice that the partition (V1 , V2 ) changes only if L passes a point D on the
circle such that at D, L is perpendicular to a line that connects f (i) to f (j) for i, j∈V . Now, since
the embedding is in general position, there are exactly two points on every line that connects two
points f (i) and f (j), so V1 changes at most by one node leaving V1 and one node entering V1 .
Hence, p(V1 ) changes by either ±2 or 0 value at each change. Now, since |V |≡0(mod 4), p(V1 ) has
an even value in all the resulting partitions. Therefore, as we move L from being tangent at point
A to point B, there should be a point D such that in the resulted partition p(V1 )=p(V2 )=0.

Proof of Corollary 2. Every series-parallel graph G has a separation pair {u, v} such that every
connected component of G[V \{u, v}] has less that 2|V |/3 nodes, and furthermore, such a separation
pair can be found in linear time. To see this, consider the derivation tree T of the construction of
G. The root of T corresponds to G, the leaves correspond to the edges, and every internal node i
corresponds to a subgraph Gi =(Vi , Ei ) that is the series or parallel composition of the subgraphs
corresponding to its children. Starting at the root of T , walk down the tree following always
the edge to the child corresponding to a subgraph with the maximum number of nodes until the
number of nodes becomes ≤2|V |/3. Thus, we arrive at a node i of the tree such that |Vi |>2|V |/3
and |Vj |≤2|V |/3 for all children j of i. Let ui , vi be the terminals of Gi . Note that ui , vi separate all
the nodes of Gi from all the nodes that are not in Gi . Since |Vi |>2|V |/3, we have |V \Vi |<|V |/3. If
Gi is the parallel composition of the graphs corresponding to the children of i, then the separation
pair {ui , vi } has the desired property, i.e. all the components of G[V \{u, v}] have less than 2|V |/3
nodes.
Suppose Gi is the series composition of the graphs Gj , Gk corresponding to the children j, k of
i, and let w be the common terminal of Gj , Gk ; thus, Gi has terminals ui , w, and Gk has terminals
w, vi . Assume wlog that |Vj |≥|Vk |. Then |V |/3<|Vj |≤2|V |/3. The pair {ui , w} of terminals of Gj
separates all the nodes of Vj \{ui , w} from all the nodes of V \Vj , and both these sets have less than
2|V |/3 nodes. Thus, {ui , w} has the required property.
Proof of Theorem 2. Using Lemma 5 for q=4, we consider two cases:
(i) There is a separation pair {u, v}∈V such that if G1 , . . . , Gk are the connected components of
G\{u, v}, for any i, |Vi |<3|V |/4. In this case Lemma 4 for q=4 proves the theorem.
(ii) After a set of contractions, G can be transformed into a 3-connected graph G∗ =(V ∗ , E ∗ ) with
weighted edges such that for any edge e∗ ∈E ∗ , w(e∗ )<|V |/4. In this case the proof is similar to
the proof of Theorem 1. Notice that if G∗ contains a triangle then the proof is much simpler
18

as in the proof of Lemma 1 but here to avoid repetition, we use the approach in the proof of
Theorem 1 and prove the theorem once for all cases of G∗ .
Recall that for each edge in G∗ , its weight represents the number of nodes in the contracted
subgraph that it represents. So if e∗ ∈E ∗ represents an induced subgraph of G with l nodes,
then w(e∗ )=l; and if e∗ ∈E∩E ∗ then w(e∗ )=0. Using Lemma 2, we can find {u, v, w}∈V ∗
and a partition (V1∗ , V2∗ ) of V ∗ with properties described in the Lemma. Since in G∗ edges
have weights
that actually represent nodes in G, we want a partition such that we also have
P
|V2∗ |+ e∈G[V ∗ ] w(e)≤|V |/2. Notice that we can modify the proof of Lemma 2 to take into
2
P
account the weights for the edges and find a partition such that |V2∗ |+ e∈G[V ∗ ] w(e)≤|V |/2
2
as follows. Again, using the algorithm presented in [4], we can find a non-separating proper
cycle C0 in G∗ such that every node in C0 has a neighbor in G∗ \C0 . We consider three cases:
P
(a) If |C0 |+ e∈G[C0 ] w(e)≤|V |/2+1, then the proof is as in the proof of Lemma 2. Select
any three consecutive nodes (u, w, v) of C0 and set V2∗ =C0 \{w} and V1∗ =V ∗ \V2∗ .
P
(b) If |C0 |>|V ∗ |/2 and |C0 |+ e∈G[C0 ] w(e)>|V |/2+1, then as in the proof of Lemma 2,
since |C0 |>|V ∗ \C0 | and every node is C0 has a neighbor in V ∗ \C0 , there exist a node
w∈V ∗ \C0 such that |N (w)∩C0 |≥2. Select two
P nodes u, v∈N (w)∩C0 . There exists a
path P in C0 between u and v such that |P |+ e∈G[P ] w(e)<|V |/2−1. Set V2∗ ={u, v}∪P
and V1∗ =V ∗ \V2∗ .
P
(c) If |C0 |≤|V ∗ |/2 and |C0 |+ e∈G[C0 ] w(e)>|V |/2+1, then if there exist a node w∈V ∗ \C0
such that |N (w)∩C0 |≥2, the proof is as in the previous part. So assume for all w∈V ∗ \C0 ,
|N (w)∩C0 |≤1. Assume w1 , w2 , . . . , wt ∈V ∗ \C0 are all the nodes with |N (wi )∩C0 |=1. We
show that there is a 1≤i≤t, such that wi is not a cut-point of G∗ [V ∗ \C0 ]. Let T be a
spanning tree of G∗ [V ∗ \C0 ]. If there is a 1≤i≤t, such that wi is a leaf of T , then wi is not
a cut-point of G∗ [V ∗ \C0 ] and there is nothing left to prove. So assume none of wi s is a
leaf of T . Suppose 1≤p, q≤t are such that the path between wp and wq in T is the longest
between all pairs of wi s. We show that wp and wq cannot be cut-points of G∗ [V ∗ \C0 ].
Assume for example wp is a cut-point of G∗ [V ∗ \C0 ] and G∗q̄ is a connected component of
G∗ [V ∗ \C0 ]\{wp } such that wq ∈G
/ ∗q̄ . Since the path between wp and wq in T is the longest
between all pairs of wi s, ∀1≤i≤t:wi ∈G
/ ∗q̄ , otherwise we can find a longer path from wq
to some other wi . On the other hand, if ∀1≤i≤t:wi ∈G
/ q̄ , in G∗ \{wp } the cycle C0 is
∗
disconnected from Gq̄ which contradicts with the 3-connectedness of G∗ . Hence, there
should be at least a noncut-point w∈V ∗ \C0 with |N (w)∩C0 |=1. Since G∗ is 3-connected,
each node has degree at least 3. Hence, there are two nodes u, v∈N (w)∩(V ∗ \C0 ). Set
V1∗ =C0 ∪{w} and V2∗ =V ∗ \V1∗ . (V1∗ , V2∗ ) is a desirable partition for V ∗ .
Hence, we can find {u, v, w}∈V ∗ andPa partition (V1∗ , V2∗ ) of V ∗ with properties described in
the Lemma 2 as well as having |V2∗ |+ e∈G[V ∗ ] w(e)≤|V |/2. Set X={u, v, w}. Using Lemma 3,
2
G∗ has a convex X-embedding in general position like f ∗ :V ∗ →R2 as described in the lemma
and depicted in Fig. 3. Now, from this embedding, we get a convex X-embedding for G
like f :V →R2 as follows. For any i∈V ∩V ∗ , f (i)=f ∗ (i). For any edge {i, j}∈E ∗ such that
{i, j} represents an induced subgraph of G, we represent it by a pseudo-path between i and
j in G like P and place the nodes in P in order on random places on the line segment that
connects f (i) to f (j). If the edge {i, j}∈E ∗ is between a node in V1∗ and a node in V2∗ and
represents a pseudo-path P in G , we place the nodes in P in order on random places on the
segment that connects f (i) to f (j) but above the line L1 . Hence, by this process, we get a
convex X-embedding for G which is in general position (almost surely) except for the nodes
19

that are part of a pseudo-path (which we know have length less than |V |/4). Notice that if
V20 ⊂V contains all the nodes in V2∗ and all the nodes that are part of a pseudo-path between
the nodes of V2∗ (represented by weighted edges in G∗ ) in G, and V10 =V \V20 , then (V10 , V20 ) is
partition of G with all the properties of Lemma 2. Moreover, the X-embedding f of G that
we derived from f ∗ for G∗ , has all the properties of Lemma 3 for the partition (V10 , V20 ).
The rest of the proof is similar to the proof of Theorem 1. We consider again a circle C
around f (u), f (v), f (w) in R2 as shown in Fig. 3. Also consider a directed line L tangent to
the circle C at point A and project nodes of G onto the line L. With the same argument as
in the proof of Theorem 1, since the embedding f has the properties in Lemma 2 and 3, if we
set V1 to be the |V |/2 nodes whose projections come first and V2 are the |V |/2 nodes whose
projections come last, then G[V1 ] and G[V2 ] are both connected. If |p(V1 )|≤1, then (V1 , V2 ) is
a good partition and there is nothing left to prove. Otherwise, we move L from being tangent
at point A to point B (AB is a diameter of the circle C) and consider the resulting partition.
Notice that if at point A, p(V1 )>0, then at point B since V1 and V2 completely switch places
compared to the partition at point A, p(V1 )<0. Hence, as we move L from being tangent at
point A to point B and keep it tangent to the circle, in the resulting partitions, p(V1 ) goes
from some positive value to a negative value. Notice that the partition (V1 , V2 ) changes only
if L passes a point D on the circle such that at D, L is perpendicular to a line that connects
f (i) to f (j) for i, j∈V . Now, since the embedding is in general position except for few lines
∗ or {i, j}∈E∩E ∗ there are exactly two points on
that contain a pseudo-path, if {i, j}∈E∪E
/
the line that connects f (i) and f (j), so V1 changes at most by one node leaving V1 and one
node entering V1 . Thus, in this case p(V1 ) changes by at most 2. However, if {i, j}∈E ∗ , then
since there can be at most |V |/4−1 points on the line that connects f (i) to f (j), p(V1 ) may
change by |V |/4−1. So let’s consider that L is perpendicular to the line that connects f (i)
and f (j) at point D and p(V1 )>0 slightly before L passes point D and p(V1 )≤0 slightly after
L passes point D. We consider 2 cases:
∗ or {i, j}∈E∩E ∗ . In this case since V changes by at most 2,
(a) Suppose {i, j}∈E∪E
/
1
therefore, p(V1 ) slightly after L passes D is either 0 or −1. Hence, the partition (V1 , V2 )
that we get after L passes D is a good partition with |V1 |=|V2 |=|V |/2.

(b) Suppose {i, j}∈E ∗ . Let (Vb1 , Vb2 ) be the partition slightly before L passes D and let
(Va1 , Va2 ) be the partition slightly after. Assume P0 is the pseudo-path between i and j
and P =P0 ∪{i, j}. It is easy to see that (Vb1 \P, Vb2 \P )=(Va1 \P, Va2 \P ). If p(Vb1 \P )=0,
since |P0 |<|V |/4, then V1 =Vb1 \P and V2 =V \V1 is a good partition and there is nothing
left to prove. So either p(Vb1 \P )>0 or p(Vb1 \P )<0.
If p(Vb1 \P )>0, since p(Va1 )≤0 and Vb1 \P =Va1 \P , we can add a set of nodes from P ∩Va1 ,
say P 0 , to Va1 \P to get p((Va1 \P )∪P 0 )=0. Now since |P0 |<|V |/4, V1 =(Va1 \P )∪P 0 and
V2 =V \V1 is a good partition.
If p(Vb1 \P )<0, since p(Vb1 )>0, we can add a set of nodes from P ∩Vb1 , say P 0 , to Vb1 \P
to get p((Vb1 \P )∪P 0 )=0. Now since |P0 |<|V |/4, V1 =(Vb1 \P )∪P 0 and V2 =V \V1 is a good
partition.

20

D

Missing Proofs from Section 4

Proof of Corollary 4. Suppose without loss of generality that nr ≥nb and let nr −nb =2t and nr +nb =
n=2m. Set p(i)=1 for i∈R and p(i)=−1 for i∈B. Then p(V )=2t. From the equations, we have
nr =m+t and nb =m−t.
From Corollary 1 we can find a partition (V1 , V2 ) such that |V1 |=|V2 | and |p(V1 )−p(V )/2|, |p(V1 )−
p(V )/2|≤1. Let r1 =|R∩V1 | and b1 =|B∩V1 |. We have r1 +b1 =n/2=m and t−1≤r1 −b1 ≤t+1. Therefore, (m+t)/2−(1/2)≤r1 ≤(m+t)/2+(1/2). Since r1 is an integer and nr =m+t is even, it follows
that r1 =(m+t)/2=nr /2. Hence, b1 =(m−t)/2=nb /2. Therefore, V2 also contains nr /2 red nodes
and nb /2 blue nodes.

References
[1] D. Bienstock. Electrical Transmission System Cascades and Vulnerability: An Operations
Research Viewpoint, volume 22. SIAM, 2016.
[2] J. Bondy and U. Murty. Graph theory, 2nd printing, 2008.
[3] F. Chataigner, L. R. Salgado, and Y. Wakabayashi. Approximation and inapproximability
results on balanced connected partitions of graphs. DMTCS, 9(1):177–192, 2007.
[4] J. Cheriyan and S. Maheshwari. Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms, 9(4):507–537, 1988.
[5] J. Chlebı́ková. Approximating the maximally balanced connected partition problem in graphs.
Inform. Process. Lett., 60(5):225–230, 1996.
[6] M. Dyer and A. Frieze. On the complexity of partitioning graphs into connected subgraphs.
Discrete Applied Math., 10:139–153, 1985.
[7] S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science,
2(3):339–344, 1976.
[8] N. Fan, D. Izraelevitz, F. Pan, P. M. Pardalos, and J. Wang. A mixed integer programming
approach for optimal power grid intentional islanding. Energy Systems, 3(1):77–93, 2012.
[9] E. Gyori. On division of graphs to connected subgraphs. In Combinatorics (Proc. Fifth
Hungarian Colloq., Keszthely, 1976), volume 1, pages 485–494, 1976.
[10] J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J.
Comput., 2(3):135–158, 1973.
[11] A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In
Theory of graphs: International symposium, volume 67, pages 215–232. Gordon and Breach,
New York, 1967.
[12] N. Linial, L. Lovasz, and A. Wigderson. Rubber bands, convex embeddings and graph connectivity. Combinatorica, 8(1):91–102, 1988.
[13] L. Lovász. A homology theory for spanning tress of a graph. Acta Mathematica Hungarica,
30(3-4):241–251, 1977.

21

[14] S. Pahwa, M. Youssef, P. Schumm, C. Scoglio, and N. Schulz. Optimal intentional islanding
to enhance the robustness of power grid networks. Physica A, 392(17):3741–3754, 2013.
[15] C. H. Papadimitriou and M. Yannakakis. The complexity of restricted spanning tree problems.
JACM, 29(2):285–309, 1982.
[16] R. J. Sánchez-Garcı́a, M. Fennelly, S. Norris, N. Wright, G. Niblo, J. Brodzki, and J. W. Bialek.
Hierarchical spectral clustering of power grids. IEEE Trans. Power Syst., 29(5):2229–2237,
2014.
[17] K. Sun, Q. Zhao, D.-Z. Zheng, J. Ma, and Q. Lu. A two-phase method based on obdd for
searching for splitting strategies of large-scale power systems. In Proc. IEEE PowerCon’02,
2002.
[18] H. Suzuki, N. Takahashi, and T. Nishizeki. A linear algorithm for bipartition of biconnected
graphs. Inform. Process. Lett., 33(5):227–231, 1990.
[19] W. T. Tutte. How to draw a graph. Proc. London Math. Soc, 13(3):743–768, 1963.
[20] K. Wada and K. Kawaguchi. Efficient algorithms for tripartitioning triconnected graphs and
3-edge-connected graphs. In Graph-Theoretic Concepts in Computer Science, pages 132–143.
Springer, 1994.
[21] D. B. West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River,
2001.

22

