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.




Comments:

None:
2010-07-12T14:33:49Z

Nice and informative post, thanks.

I have one general question about 'minor-closed algorithmics', i.e., algorithms which solve some combinatorial problem (e.g. max flow) fast on a graph which is promised to come from a minor-closed class.

Namely: do such algorithms usually rely on first having or finding a structure-decomposition for the input graph? Or are there cases where the algorithm can 'take it on faith'?

As a simpler, related question: are there graph algorithms solving problems on planar graphs, that are faster than finding the planar embedding first and then solving the problem? Apologies if this question is overly-general.

thanks,
Andy D

11011110:
2010-07-12T15:31:08Z

In this case we needed a structural decomposition explicitly, but I think most algorithms in this area don't. The thing to watch out for with algorithms on minor-closed families is that they often have O-notation that looks nice but that hides astronomical constant factors, making them practically not so useful.

As for whether there are algorithms on planar graphs that don't rely on having a planar embedding of the graph: yes, sometimes all that is needed is that the graph is sparse. For instance my recent post on clique-finding applies to planar graphs without needing an embedding. You can 6-color (possibly 5-color, I'm not sure, but 6 is easy) a planar graph in linear time without going through the embedding or the 4-color theorem. But it depends on what problem you want to solve.