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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/