Bidimensionality

Bidimensionality is a theory, introduced by Erik Demaine, Fedor Fomin, Mohammad Taghi Hajiaghayi and Dimitrios Thilikos, that identifies a broad class of graph problems, called bidimensional problems, which admit efficient approximate, fixed-parameter or kernelization algorithms across a wide range of graph classes, including planar graphs, graphs of bounded genus, and graphs that exclude some fixed graph as a minor. Building on the graph minor theory of Robertson and Seymour, the theory yields subexponential parameterized algorithms for problems such as vertex cover and dominating set on minor-free graphs, polynomial-time approximation schemes for problems including feedback vertex set, vertex cover and dominating set on those same graphs, and linear-size kernels for bidimensional problems with certain additional properties. The framework's creators received the Nerode Prize in 2015 for this work.