  The irrelevant vertex technique provides a powerful tool for the design of
parameterized algorithms for a wide variety of problems on graphs. A common
characteristic of these problems, permitting the application of this technique
on surface-embedded graphs, is the fact that every graph of large enough
treewidth contains a vertex that is irrelevant, in the sense that its removal
yields an equivalent instance of the problem. The straightforward application
of this technique yields algorithms with running time that is quadratic in the
size of the input graph. This running time is due to the fact that it takes
linear time to detect one irrelevant vertex and the total number of irrelevant
vertices to be detected is linear as well. Using advanced techniques,
sub-quadratic algorithms have been designed for particular problems, even in
general graphs. However, designing a general framework for linear-time
algorithms has been open, even for the bounded-genus case. In this paper we
introduce a general framework that enables finding in linear time an entire set
of irrelevant vertices whose removal yields a bounded-treewidth graph, provided
that the input graph has bounded genus. Our technique consists in decomposing
any surface-embeddable graph into a tree-structured collection of
bounded-treewidth subgraphs where detecting globally irrelevant vertices can be
done locally and independently. Our method is applicable to a wide variety of
known graph containment or graph modification problems where the irrelevant
vertex technique applies. Examples include the (Induced) Minor Folio problem,
the (Induced) Disjoint Paths problem, and the $\mathcal{F}$-Minor-Deletion
problem.
