Prof. Meirav Zehavi

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 k×k-grid as a minor, or its treewidth is O(k). However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs. The reason is very simple: a clique on k-1 vertices has no k×k-grid as a minor and its treewidth is k-2, while classes of geometric graphs such as unit disk graphs or map graphs can have arbitrarily large cliques. Thus, the combinatorial lemma of Robertson, Seymour and Thomas is inapplicable to these 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, the intersection graphs of finitely many simply-connected and interior-disjoint regions of the Euclidean plane. Informally, our lemma states the following. For any map graph G, there exists a collection (U1,…,Ut) of cliques of G with the following property: Geither contains ak×k-grid as a minor, or it admits a tree decomposition where every bag is the union ofO(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 2O(klogk)·nO(1) for Connected PlanarF-Deletion (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 2O(k0.75logk)·nO(1)-time algorithms on map graphs.