Families of graphs that are closed under the operation of taking
minors have a deep and mysterious
structure theory, in which the graphs in the family can be formed by
clique-sums of bounded-genus graphs with finitely many "apexes" and "whorls". But in some cases, the structure can be greatly simplified: if one of the
forbidden minors of the family can be drawn in the plane with only one
crossing, then the graphs in the family can be formed from clique-sums that only involve planar graphs and constant-sized graphs.
For instance, the K
5-free graphs are formed by gluing together planar graphs and copies of the eight-vertex
Wagner graph at their vertices, edges, or triangles. A similar decomposition is known for the K
3,3-free graphs, with K
5 taking the place of the Wagner graph.
We know how to solve the
maximum flow problem in planar graphs quite efficiently, in part because it's closely related through planar graph duality to easier shortest path problems. For instance, Borradaile and Klein (
JACM 2009) showed how to solve planar directed flow problems in O(n log n) time. It would be nice if we could extend these speedups to broader classes of graphs. Some such extensions are known: Chambers, Erickson, and Nayyeri, in two papers at
SoCG'09 and
STOC'09, found efficient algorithms for flow problems in bounded genus graphs, and Hochstein and Weihe at
SODA'07 showed how to solve flows efficiently for graphs that can be drawn in the plane with a bounded number of crossings. But none of these techniques seemed to extend to more general minor-closed families.
My new preprint with
Erin Chambers, "
Flows in One-Crossing-Minor-Free Graphs" (arXiv:1007.1484) extends the planar flow algorithms in a different direction, to one-crossing-minor-free graphs. The basic idea is to apply a technique from Hagerup, Katajainen, Nishimura, and Ragde (
JCSS 1998) for flows in graphs of bounded
treewidth. Bounded-treewidth graphs are, essentially, the graphs that you get from clique-sums of constant-sized graphs, and the idea of Hagerup et al. is to repeatedly replace the subgraph on one side of a clique-sum by a constant-sized "mimicking network" with the same flow properties. With some care in how the replacements are ordered and in the construction of the mimicking networks, the same idea turns out to work for the clique-sums in the structural decomposition of one-crossing-minor-free graphs. The Hochstein-Weihe result also comes into play, because as the sequence of replacements progresses we need to compute flows in planar graphs with constant-sized replacement graphs glued into them, which are a special case of graphs with a constant number of crossings.
The real goal is to handle arbitrary minor-closed graph families, but to do that we'd need to extend our techniques in three ways: we need to handle clique-sums of bounded-genus but nonplanar graphs, we need to handle apexes, and we need to handle whorls. There are some technical reasons why our methods don't immediately extend to the bounded genus case, involving the possibility that the triangles that components of a clique-sum are glued together along might not be separating. And since whorls involve bounded
pathwidth there's some hope of progress there. But the apexes seem to be a problem. A single apex can introduce an unbounded number of crossings. And, even finding maximum flows in planar graphs with apexes, without all the other aspects of the structure theory, would be interesting: it would allow us to solve planar problems with multiple sources and multiple sinks, by connecting all these terminals together to new apex nodes.