Decomposition of Map Graphs with Applications Bidimensionality is the most common technique to design subexponentialtime 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 sqrtktimes sqrtkgrid as a minor, or its treewidth is O(sqrtk). However, bidimensionality theory cannot be extended directly to several wellknown 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 sqrtktimes sqrtkgrid as a minor, or it admits a tree decomposition where every bag is the union of O(sqrtk) 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 2O(sqrtklogk) cdot nO(1) for the Connected Planar cal FDeletion problem (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest CyclePath 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.  Longest :240,CyclePath, these are the first subexponentialtime parameterized algorithms on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known 2O(k0.75logk) cdot nO(1)time algorithms on map graphs.

Hitting minors on bounded treewidth graphs. II. Singleexponential algorithms Abstract   For a finite collection of graphs    F   , the    F    MDeletion  (resp.    F    TMDeletion ) problem consists in, given a graph G and an integer k, decide whether there exists    S  xe2x8ax86  V  (  G  )    with      S    xe2x89xa4  k    such that    G  xe2x88x96  S    does not contain any of the graphs in    F    as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G, denoted by    tw   , and specifically in the cases where    F    contains a single connected planar graph H. We present algorithms running in time      2    O  (   tw   )    xe2x8bx85    n    O  (  1  )     , called singleexponential, when H is either      P    3     ,      P    4     ,      C    4     , the  paw , the  chair , and the  banner  for both      H      MDeletion  and      H      TMDeletion , and when    H      K    1  ,  i     , with    i  xe2x89xa5  1   , for      H      TMDeletion . Some of these algorithms use the rankbased approach introduced by Bodlaender et al. (2015)  7 . This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of      H      MDeletion  in terms of H.