  We prove the following theorem. Given a planar graph $G$ and an integer $k$,
it is possible in polynomial time to randomly sample a subset $A$ of vertices
of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of
treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph
$H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole
vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot
n^{\mathcal{O}(1)})^{-1}$, where $n$ is the number of vertices of $G$.
  Together with standard dynamic programming techniques for graphs of bounded
treewidth, this result gives a versatile technique for obtaining (randomized)
subexponential parameterized algorithms for problems on planar graphs, usually
with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)}
n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as
searching for a small, connected pattern with a prescribed property in a large
host graph, examples of such problems include Directed $k$-Path, Weighted
$k$-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up
to this point, it was open whether these problems can be solved in
subexponential parameterized time on planar graphs, because they are not
amenable to the classic technique of bidimensionality. Furthermore, all our
results hold in fact on any class of graphs that exclude a fixed apex graph as
a minor, in particular on graphs embeddable in any fixed surface.
