  In this paper we show how to combine two algorithmic techniques to obtain
linear time algorithms for various optimization problems on graphs, and present
a subroutine which will be useful in doing so.
  The first technique is iterative shrinking. In the first phase of an
iterative shrinking algorithm, we construct a sequence of graphs of decreasing
size $G_1,\ldots,G_\ell$ where $G_1$ is the initial input, $G_\ell$ is a graph
on which the problem is easy, and $G_i$ is obtained from $G_{i+1}$ via some
shrinking algorithm. In the second phase we work through the sequence in
reverse, repeatedly constructing a solution for a graph from the solution for
its successor. In an iterative compaction algorithm, we insist that the graphs
decrease by a constant fraction of the entire graph.
  Another approach to solving optimization problems is to exploit the
structural properties implied by the connectivity of the input graph. This
approach can be used on graphs which are not highly connected by decomposing an
input graph into its highly connected pieces, solving subproblems on these
specially structured pieces and then combining their solutions.
  We combine these two techniques by developing compaction algorithms which
when applied to the highly connected pieces preserve their connectivity
properties. The structural properties this connectivity implies can be helpful
both in finding further compactions in later iterations and when we are
manipulating solutions in the second phase of an iterative compaction
algorithm.
  To illustrate how this compaction algorithm can be used as a subroutine, we
present a linear time algorithm that given four vertices $\{s_1,s_2,t_1,t_2\}$
of a graph $G$, either finds a pair of disjoint paths $P_1$ and $P_2$ of $G$
such that $P_i$ has endpoints $s_i$ and $t_i$, or returns a planar embedding of
an auxiliary graph which shows that no such pair exists.
