Killing a Vortex

Abstract

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 embeddablegraphs. Here a graph is almost embeddableif it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an orderly fashioninto 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 and prove that all -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 for some . Using our new structure theorem, we design an algorithm that, given an -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 minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. © 2024 Copyright held by the owner/author(s). Publication rights licensed 1to ACM.