|We introduce a new framework for designing fixed-parameter algorithms with
subexponential running time---2^O(sqrt k) n^O(1). Our results apply to a broad
family of graph problems, called bidimensional problems, which includes many
domination and covering problems such as vertex cover, feedback vertex set,
minimum maximal matching, dominating set, edge dominating set,
clique-transversal set, and many others restricted to bounded genus graphs.
Furthermore, it is fairly straightforward to prove that a problem is
bidimensional. In particular, our framework includes as special cases all
previously known problems to have such subexponential algorithms. Previously,
these algorithms applied to planar graphs, single-crossing-minor-free graphs,
and/or map graphs; we extend these results to apply to bounded-genus graphs as
well. In a parallel development of combinatorial results, we establish an
upper bound on the treewidth (or branchwidth) of a bounded-genus graph that
excludes some planar graph H as a minor. This bound depends linearly on the
size |V(H)| of the excluded graph H and the genus g(G) of the graph G, and
applies and extends the graph-minors work of Robertson and Seymour.
Building on these results, we develop subexponential fixed-parameter algorithms
for dominating set, vertex cover, and set cover in any class of graphs
excluding a fixed graph H as a minor. In particular, this general category of
graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free
graphs, and any class of graphs that is closed under taking minors.
Specifically, the running time is 2^O(sqrt k) n^h, where h is a constant
depending only on H, which is polynomial for k = O(log^2 n). We introduce a
general approach for developing algorithms on H-minor-free graphs, based on
structural results about H-minor-free graphs at the heart of Robertson and
Seymour's graph-minors work. We believe this approach opens the way to further
development on problems in H-minor-free graphs.