Contraction Bidimensionality of Geometric Intersection Graphs

Julien Baste, Dimitrios M. Thilikos

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${\bf…