The newly developing theory of bidimensional graph problems provides general
techniques for designing efficient fixed-parameter algorithms and
approximation algorithms for NP-hard graph problems in broad classes of
phs. This theory applies to graph problems that are \emph{bidimensional}
in the sense that (1) the solution value for the $k \times k$ grid graph
(and similar graphs) grows with $k$, typically as $\Omega(k^2)$, and
(2) the solution value goes down when contracting edges and optionally
when deleting edges. Examples of such problems include feedback vertex set,
vertex cover, minimum maximal matching, face cover, a series of vertex-removal
parameters, dominating set, edge dominating set, $r$-dominating set, connected
dominating set, connected edge dominating set, connected $r$-dominating set, and
unweighted TSP tour (a walk in the graph visiting all vertices). Bidimensional
problems have many structural properties; for example, any graph embeddable in a
surface of bounded genus has treewidth bounded above by the square root of the
problem's solution value. These properties lead to efficient---often
subexponential---fixed-parameter algorithms, as well as polynomial-time
approximation schemes, for many minor-closed graph classes. One type of
minor-closed graph class of particular relevance has \emph{bounded local
treewidth}, in the sense that the treewidth of a graph is bounded above in
terms of the diameter; indeed, we show that such a bound is always at most linear.
The bidimensionality theory unifies and improves several previous results.
The theory is based on algorithmic and combinatorial extensions to parts
of the Robertson-Seymour Graph Minor Theory, in particular initiating a
parallel theory of graph contractions. The foundation of this work is the
topological theory of drawings of graphs on surfaces.

This is joint work with Fedor Fomin, MohammadTaghi Hajiaghayi, and
Dimitrios Thilikos.