Over the last few years, the theory of parameterized complexity has developed into a useful framework for a refined analysis of hard algorithmic problems. Several researchers have obtained exponential speedups in fixed-parameter algorithms for various problems on several classes of graphs. This paper introduces a framework for extending algorithms for planar graphs to apply to H-minor-free graphs for any fixed H. The authors design subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover problems for H-minor-free graphs. The framework developed in the paper is basically rooted in fine-structure investigations on graph minors.

First, previous results for planar graphs are extended to bounded-genus graphs. Second, almost-embeddable graphs are studied, namely, graphs that can be drawn in a bounded-genus surface, except for a bounded number of “local areas of nonplanarity” (in terms of graph minor theory vortices). Third, the results of Robertson and Seymour [1] are used, which characterize H-minor-free graphs as a tree structure of pieces, where each piece is an almost-embeddable graph. Here, special clique-sum decompositions are introduced, and are used to improve the algorithms. A byproduct of the results is a generalization of the “quickly excluding a planar graph” theorem [2]. Another interesting concept developed in the paper is the concept of bidimensionality.