grid theorem is an analogous excluded grid theorem for infinite graphs. Subexponential parameterized algorithms Let be a minor-bidimensional problem such that for any graph G excluding some fixed graph as a minor and of treewidth at most t, deciding whether can be done in time . Then for every graph G excluding some fixed graph as a minor, deciding whether can be done in time . Similarly, for contraction-bidimensional problems, for graph G excluding some fixed apex graph as a minor, inclusion can be decided in time . Thus many bidimensional problems like Vertex Cover, Dominating Set, k-Path, are solvable in time on graphs excluding some fixed graph as a minor. Polynomial time approximation schemes Bidimensionality theory has been used to obtain polynomial-time approximation schemes for many bidimensional problems. If a minor (contraction) bidimensional problem has several additional properties then the problem poses efficient polynomial-time approximation schemes on (apex) minor-free graphs. In particular, by making use of bidimensionality, it was shown that feedback vertex set, vertex cover, connected vertex cover, cycle packing, diamond hitting set, maximum induced forest, maximum induced bipartite subgraph and maximum induced planar subgraph admit an EPTAS on H-minor-free graphs. Edge dominating set, dominating set, r-dominating set, connected dominating set, r-scattered set, minimum maximal matching, independent set, maximum full-degree spanning tree, maximum induced at most d-degree subgraph, maximum internal spanning tree, induced matching, triangle packing, partial r-dominating set and partial vertex cover admit an EPTAS on apex-minor-free graphs. Kernelization A parameterized problem with a parameter k is said to admit a linear vertex kernel if there is a polynomial time reduction, called a kernelization algorithm, that maps the input instance to an equivalent instance with at most O(k) vertices. Every minor-bidimensional problem with additional properties, namely, with the separation property and with finite integer index, has a linear vertex kernel on graphs excluding some fixed graph as a minor. Similarly, every contraction-bidimensional problem with the separation property and with finite integer index has a linear vertex kernel on graphs excluding some fixed apex graph as a minor. Notes References . . . . . . . . . Further reading Analysis of algorithms Approximation algorithms Graph minor theory Parameterized complexity