Killing a vortex

We provide a 'vortex-free' refinement of the seminal structure theorem for Kt-minor free graphs by Robertson and Seymour as follows: we identify a (parameterized) graph Ht and we prove that if we replace Kt by Ht, then the resulting decomposition becomes 'vortex-free'. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the single-crossing minor-free graphs. This result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some Ht, the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an Ht-minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. This algorithm yields, on Ht-minor-free graphs, polynomial algorithms for computational problems such as the dimer problem, the exact matching problem, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are precisely those graph classes that do not contain every Ht as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.