  We introduce and study the Doubly Balanced Connected graph Partitioning
(DBCP) problem: Let $G=(V,E)$ be a connected graph with a weight
(supply/demand) function $p:V\rightarrow \{-1,+1\}$ satisfying $p(V)=\sum_{j\in
V} p(j)=0$. The objective is to partition $G$ into $(V_1,V_2)$ such that
$G[V_1]$ and $G[V_2]$ are connected, $|p(V_1)|,|p(V_2)|\leq c_p$, and
$\max\{\frac{|V_1|}{|V_2|},\frac{|V_2|}{|V_1|}\}\leq c_s$, for some constants
$c_p$ and $c_s$. When $G$ is 2-connected, we show that a solution with $c_p=1$
and $c_s=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(V_1)=p(V_2)=0$ and $|V_1|=|V_2|$, if $|V|\equiv 0
(\mathrm{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 $\pm 1$), and to the case that $p(V)\neq 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.
