  Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin,
M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on
graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005),
pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms
on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality:
new connections between FPT algorithms and PTASs, in Proceedings of the 16th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005,
pp.590--601] this theory was extended in order to obtain polynomial time
approximation schemes (PTASs) for bidimensional problems. In this work, we
establish a third meta-algorithmic direction for bidimensionality theory by
relating it to the existence of linear kernels for parameterized problems. In
particular, we prove that every minor (respectively contraction) bidimensional
problem that satisfies a separation property and is expressible in Countable
Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs
that exclude a fixed graph (respectively an apex graph) H as a minor. Our
results imply that a multitude of bidimensional problems g graph classes. For
most of these problems no polynomial kernels on H-minor-free graphs were known
prior to our work.
