Killing a vortex

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H, every H-minor-free graph can be obtained by clique-sums of "almost embeddable" graphs. Here a graph is "almost embeddable" if it can be obtained from a graph of bounded Eulergenus by pasting graphs of bounded pathwidth in an "orderly fashion" into a bounded number of faces, called the vortices, and then adding a bounded number of additional vertices, called apices, with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end we identify a (parametric) graph S t and prove that all S t -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H-minor-free graphs, whenever H is not a minor of S t for some t ∈ N.

Using our new structure theorem, we design an algorithm that, given an S t -minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minorclosed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every S t as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.