1. Introduction
The Klein-Plotkin-Rao (KPR) Theorem is a powerful statement about the geometry of planar graphs and their generalizations. Here, I’ll present a new, very simple proof of the theorem that was discovered in joint work with Cyrus Rashtchian. (This will appear in a preprint soon, together with some new results.) In the next post, I’ll give some applications in geometry and algorithms.
Recall that a graph is planar if it can be drawn in the plane without any edge crossings. Wagner’s theorem gives an intrinsic characterization of planar graphs in terms of excluded minors. Recall that a graph is a minor of a graph
if
can be obtained from
by a sequence of (i) edge and vertex deletions and (ii) contraction of edges. A graph
excludes
as a minor if
is not a minor of
. Kuratowki’s theorem states that planar graphs are precisely those which exclude both
and
as minors, where we use
and
to denote the complete graph on
vertices and the complete
-by-
bipartite graph, respectively. In this post, we are particularly concerned with
-minor-free graphs, i.e. those which exclude
as a minor for some
.
I’ll first state and prove a simpler version of the KPR theorem. In the next post, I’ll discuss a stronger statement (in the language of random partitions) that follows directly from the proof. Then using these partitions, we will show that the observable diameter of every -minor-free graph is “large,” and use that fact to prove an upper bound on the uniform multi-commodity flow gap in such graphs.
2. Low-diameter graph partitioning
Consider a finite graph equipped with its shortest-path metric
(much of what we say here extends to infinite graphs). For now, all the edges of
will have length one, although we will generalize to arbitrary weighted graphs for some applications in the next post.
Given a subset , we write
A weak but simpler version of the KPR Theorem can be stated as follows.
Theorem 1 Let
be a graph that excludes
as a minor. Then for every number
, there exists a partition
such that
for every
and at most an
-fraction of edges of
go between different sets in the partition.
The theorem was originally proved with a dependence of , but this was improved to
by Fakcharoenphol and Talwar. Today I will prove the
bound. The partitioning will be accomplished via an iterative operation which we will call chopping.
Consider any connected graph and a number
. We will describe an operation which we call a
-chop of
. Let
be any node of
, which we will call the “root node” of the chop, and let
(the “initial offset”).

The chopping operation is as follows: We partition , where
, and the rest of the sets are the disjoint annuli,
for . See Figure 1 for an example of these cuts (the red and blue alternating regions) on a grid graph. Of course, since
is finite, eventually the annuli are empty.
We define a -chop on a possibly disconnected graph as the partition arising from doing a
-chop on each of its connected components. Finally, we define a
-chop on a sequence of disjoint sets
as the result of doing a
-chop on each of the induced graphs
for
. Thus if we have an initial partition
of
, then a
-chop of
produces a refined partition
of
. See Figure 2 for the result of two iterated
-chops applied to the grid graph. The yellow circles represent the root nodes in the second chop.

We can now state the main technical result needed to prove Theorem 1.
Lemma 2 If
excludes
as a minor, then for any
, any sequence of
iterated
-chops on
results in a partition
such that
for each
.
Observe that refers to the diameter in
, the shortest-path metric on
. Also, note that we do not constrain the root node or the initial offset of the chops. Klein, Plotkin, and Rao prove this lemma with a dependence of
on the diameter. FT use a more complicated approach.
To see how Lemma 2 implies Theorem 1, one proceeds as follows. First, let be large enough so that setting
in Lemma 2 yields a partition into sets of diameter at most
. After fixing the root node for a
-chop of
, one can consider the initial offsets
. An edge
can be cut (i.e.
and
end up in distinct sets of the partition) in at most one of these offsets. Thus there exists an offset that cuts only a
-fraction of edges. Since we perform
iterated
-chops, there exists a choice of initial offsets that cuts at most
-fraction of edges. That completes the reduction.
3. A sketch
Before moving onto the formal argument, I’ll present a simple sketch that contains the main ideas. The proof is by contradiction; if we perform a sequence of
-chops and the diameter of any remaining piece fails to be
, then we will construct a
minor in
.
First, we give an equivalent characterization of when a graph has a graph
as a minor: There exist disjoint connected subsets
, one corresponding to each vertex of
. We call these supernodes. Furthermore, there should be an edge between supernodes whenever there is an edge between the corresponding vertices in
.

Now, the proof is by induction. Note that the base case is trivial since a
minor is a single vertex. By induction, we can assume that if a sequence of
chops fails, then there must be a
minor contained in some offending annulus. See Figure 3. If we could ensure that every supernode of the minor touched the upper boundary of the annulus as in Figure 3, we could easily construct a
minor and be done, by simplying choosing the
-st supernode to be a ball around
.
Thus we need to enforce this extra property of our minor. The (very simple) idea is contained in Figure 4.

After finding a minor that intersects the annuli, we extend the supernodes to touch the upper boundary of the annulus from the preceding chop (which is represented by the purple line in the picture). The point is that we can choose these paths to be contained above the red boundary (and thus disjoint from the
supernodes), and also each of length at most
since the width of the “purple” annulus is only
. The same can be done for
. (If we didn’t care that the paths have to be above the red boundary, we could choose them of length only
.)
The only issue is that we need these new paths to be disjoint. Since the paths are always short (length at most ), we can enforce this by making sure that each supernode contains a representative and these representatives are pairwise far apart; then we grow the paths from the representatives. Initially, the representatives will be
apart, and then as we go up the inductive chain, they will get closer by at most
at every step. By choosing the initial separation large enough, they will remain disjoint. That’s the sketch; it should be possible to reproduce the proof from the sketch alone, but we now present a more formal proof.
4. The proof
We need a couple definitions. First, given a subset of vertices and a number
, we say that a set
is
-dense in
if every element of
can reach an element of
by a path of length
that is contained completely in
(the induced graph on
). Second, we say that an
-minor is
-represented by
if every supernode of
contains a representative from
and these representatives are pairwise distance more than
apart in the metric
(the global shortest-path metric on
). We now state a lemma that we can prove by induction and implies Lemma 2.
Lemma 3 Let
and
be any numbers. Suppose
is a graph and there is any sequence of
iterated
-chops on
that leaves a component of diameter more than
. Then for any set
that is
-dense in
, one can find a
-minor that is
-represented by
.
One can recover Lemma 2 by setting and
.
Proof: We proceed by induction on . The case
is trivial since a
minor is simply a single vertex. Thus we may assume that
.
The following figure will be a useful reference.

In general, we argue as follows. Let be any set satisfying the assumptions of the lemma. Assume there is a sequence of
iterated
-chops that leaves a component of diameter more than
. Then there must be some annulus
of the first
-chop such that
iterated
-chops on
leaves a component of diameter more than
.
Suppose the first -chop has root node
and initial offset
. Let
be the set of nodes at distance exactly
, i.e. the upper boundary of
. Observe that
is
-dense in
by construction. Thus by induction, there is a
-minor in
that is
-represented by
. Let
be the supernodes of this minor, and let
be the representatives which are further than
apart.
We now extend this to a -minor which is
-represented by
. First, we may assume that
. Otherwise, all the points of
lie in a ball of radius at most
, and hence
has diameter at most
. In particular, we know that
for every
.
Now for each , we choose a point
such that
is connected to
by a path of length at most
in
. This can be done by first going up a shortest-path from
to
of length
to reach a point
, and then choosing any point of
within distance
of
(which can always be done since
is
-dense in
). We add this path to
to get a new supernode
. Observe that the sets
are all connected and pairwise disjoint since the new paths are outside the annulus
and the paths themselves are pairwise disjoint because they are each of length at most
, but they emanate from representatives that are more than
apart. In fact, this also shows that the representatives
are further than
apart, as required.
Finally, we construct a new supernode as follows. For each
, let
be the closest node to
, and let
be the closest node in
to
. For each
, let
be a shortest-path from
to
without its endpoint
, and let
be a shortest-path to
, including
. We now set
. We claim that
forms a
-minor which is
-represented by
. First, it is clear that
since
(again, because
is
-dense in
). For the same reason, the path
is disjoint from all the sets
.
Thus the only possible obstruction to having a valid -minor is if some path
intersects a set
for
. We now show that this cannot happen. We know that if
intersects
, then it must have already traveled distance at least
away from
. But
contains a node adjacent to
(by construction), which means it continues an additional distance of
(the distance between
and
. This additional distance is also moving away from
, implying that
intersects
, which is impossible. This completes the proof.
5. The dependence on 
The best-known lower bound requires the conclusion of Theorem 1 to cut at least an -fraction of edges. (One can take
to be an
-vertex 3-regular expander graph, which obviously excludes
as a minor. Now it is easy to see that for some constant
, partitioning into pieces of diameter at most
must cut at least an
-fraction of edges.) In some special cases, e.g. graphs of genus
(which exclude
as a minor for some constant
), one can reduce the bound to
(see this joint work with Sidiropoulos). This leads to the following open problem.
Open problem: Show that under the assumptions of Theorem 1, one can find a partition that cuts only an -fraction of edges.
A positive resolution would yield an optimal unifom multi-commodity flow/cut gap for -minor-free graphs. (See the next post for details.)