Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Decomposition of Map Graphs with Applications   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.

11
The categories of this paper are: hep-lat
18
The categories of this paper are: econ
21
The categories of this paper are: adap-org
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th
27
The categories of this paper are: comp-gas
10
The categories of this paper are: q-bio
28
The categories of this paper are: alg-geom
37
The categories of this paper are: supr-con
3
The categories of this paper are: physics
4
The categories of this paper are: cond-mat
19
The categories of this paper are: eess
8
The categories of this paper are: hep-ex
35
The categories of this paper are: mtrl-th
34
The categories of this paper are: chem-ph