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.
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.)