  Bidimensionality is the most common technique to design subexponential-time
parameterized algorithms on special classes of graphs, particularly planar
graphs. The core engine behind it is a combinatorial lemma of Robertson,
Seymour and Thomas that states that every planar graph either has a
$\sqrt{k}\times \sqrt{k}$-grid as a minor, or its treewidth is $O(\sqrt{k})$.
However, bidimensionality theory cannot be extended directly to several
well-known classes of geometric graphs. Nevertheless, a relaxation of this
lemma has been proven useful for unit disk graphs. Inspired by this, we prove a
new decomposition lemma for map graphs. Informally, our lemma states the
following. For any map graph $G$, there exists a collection $(U_1,\ldots,U_t)$
of cliques of $G$ with the following property: $G$ either contains a
$\sqrt{k}\times \sqrt{k}$-grid as a minor, or it admits a tree decomposition
where every bag is the union of $O(\sqrt{k})$ of the cliques in the above
collection. The new lemma appears to be a handy tool in the design of
subexponential parameterized algorithms on map graphs. We demonstrate its
usability by designing algorithms on map graphs with running time
$2^{O({\sqrt{k}\log{k}})} \cdot n^{O(1)}$ for the Connected Planar $\cal
F$-Deletion problem (that encompasses problems such as Feedback Vertex Set and
Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and
Cycle Packing is more challenging. We have to construct tree decompositions
with more powerful properties and to prove sublinear bounds on the number of
ways an optimum solution could "cross" bags in these decompositions.
  For Longest Cycle/Path, these are the first subexponential-time parameterized
algorithms on map graphs. For Feedback Vertex Set and Cycle Packing, we improve
upon known $2^{O({k^{0.75}\log{k}})} \cdot n^{O(1)}$-time algorithms on map
graphs.
