Contraction Bidimensionality of Geometric Intersection Graphs

Abstract

Given a graph $G$, we define $\mathbf{bcg}(G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid ${\Gamma }_k$. A graph class $\mathcal{G}$ has the SQG$\mathbf{C}$ property if every graph $G\in \mathcal{G}$ has treewidth $\mathcal{O}(\mathbf{bcg}(G{)}^c)$ for some $1\le c<2$. The SQG$\mathbf{C}$ property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQG$\mathbf{C}$ property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.