<figure><img src="image_1.png" /></figure>

HAL
open science

# Contraction Bidimensionality of Geometric Intersection Graphs

Julien Baste, Dimitrios M. Thilikos

► To cite this version:

Julien Baste, Dimitrios M. Thilikos. Contraction Bidimensionality of Geometric Intersection Graphs. Algorithmica, 2022, 84 (2), pp.510-531. 10.1007/s00453-021-00912-w. hal-03541133

HAL Id: hal-03541133

https://hal.science/hal-03541133

Submitted on 16 Jul 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Contraction Bidimensionality of Geometric Intersection Graphs*,†

Julien Baste‡

Dimitrios M. Thilikos*,§

## Abstract

Given a graph $G$, we define $bcg(G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $\Gamma_k$. A graph class $G$ has the SQGC property if every graph $G \in G$ has treewidth $\mathcal{O}(bcg(G)^c)$ for some $1 \le c < 2$. The SQGC 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 SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

**Keywords:** Treewidth, Bidimensionality, Parameterized Algorithms

## 1 Introduction

Treewidth is one of most well-studied parameters in graph algorithms. It serves as a measure of how close a graph is to the topological structure of a tree (see Section 2 for the formal definition). Gavril is the first to introduce the concept in [30] but it obtained its name in the second paper of the Graph Minors series of Robertson and Seymour in [38]. Treewidth has extensively used in graph algorithm design due to the fact that a wide class of intractable problems in graphs becomes tractable when restricted on graphs of bounded treewidth [1, 5, 6]. Before we present some key combinatorial properties of treewidth, we need some definitions.

**Graph contractions and minors.** Our first aim is to define two parameterized versions of the contraction relation on graphs.

**Definition 1 (Contractions).** Given a non-negative integer $c$, two graphs $H$ and $G$, and a surjection $\sigma : V(G) \to V(H)$ we write $H \leq_{\sigma}^{c} G$ if

* for every $x \in V(H)$, the graph $G[\sigma^{-1}(x)]$ is a non-empty graph (i.e., a graph with at least one vertex) of *diameter* at most $c$ and

* for every $x, y \in V(H)$, $\{x, y\} \in E(H) \iff G[\sigma^{-1}(x) \cup \sigma^{-1}(y)]$ is connected.

<footnote>*Corresponding author: Dimitrios M. Thilikos, Email: sedthilk@thilikos.info.</footnote>

<footnote>†An extended abstract of this article appeared in the *Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria* [2]. The first author was supported by ANR projects DEMOGRAPH (ANR-16-CE40-0028). The second author was supported by the ANR projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).</footnote>

<footnote>‡Univ Lille, Centrale Lille, CRISTAL, Lille, France, Email: julien.baste@univ-lille.fr.</footnote>

<footnote>§LIRMM, Univ Montpellier, CNRS, Montpellier, France.</footnote>
We say that $H$ is a $c$-diameter contraction of $G$ if there exists a surjection $\sigma : V(G) \to V(H)$ such that $H \leq_{\sigma}^{c} G$ and we write this $H \leq^{c} G$. Moreover, if $\sigma$ is such that for every $x \in V(H)$, $|\sigma^{-1}(x)| \leq c'$, then we say that $H$ is a $c'$-size contraction of $G$, and we write $H \leq^{(c')} G$. Given two graphs $G$ and $H$, if there exists an integer $c$ such that $H \leq^{c} G$, then we say that $H$ is a contraction of $G$, and we write $H \leq G$. Moreover, if there exists a subgraph $G'$ of $G$ such that $H \leq G'$, we say that $H$ is a minor of $G$ and we write this $H \leq G$. Given a graph $H$, we denote by $\mathrm{excl}(H)$ the class of graphs that exclude $H$ as a minor.

## 1.1 Combinatorics of treewidth

One of the most celebrated structural results on treewidth is the following:

**Proposition 2.** There is a function $f: \mathbb{N} \to \mathbb{N}$ such that every graph excluding a $(k \times k)$-grid as a minor has treewidth at most $f(k)$.

A proof of Proposition 2 appeared for the first time by Robertson and Seymour in [39]. Other proofs, with better bounds to the function $f$, appeared in [40] and later in [17] (see also [33,35]). Currently, the best bound for $f$ is due to Chuzhoy, who recently proved in [4] that $f(k) = k^9 \cdot \log^{\mathcal{O}(1)} k$. On the other hand, it is possible to show that Proposition 2 is not correct when $f(k) = \mathcal{O}(k^2 \cdot \log k)$ (see [43]).

The potential of Proposition 2 on graph algorithms has been capitalized by the theory of bidimensionality that was introduced in [10] and has been further developed in [9, 13, 14, 16, 21–23, 26, 29, 32]. This theory offered general techniques for designing efficient fixed-parameter algorithms and approximation schemes for NP-hard graph problems in broad classes of graphs (see [8, 11, 12, 15, 20]). In order to present the result of this paper we first give a brief presentation of this theory and of its applicability.

**Optimization parameters and bidimensionality.** A graph parameter is a function $p$ mapping graphs to non-negative integers. We say that $p$ is a minimization graph parameter if $p(G) = \min\{k \mid \exists S \subseteq V(G) : |S| \leq k \text{ and } \phi(G, S) = \text{true}\}$, where $\phi$ is a some predicate on $G$ and $S$. Similarly, we say that $p$ is a maximization graph parameter if in the above definition we replace $\min$ and $\leq$ by $\max$ and $\geq$ respectively. Minimization or maximization parameters are briefly called *optimization parameters*.

**Definition 3 (Bidimensionality).** Given two real functions $f$ and $g$, we use the term $f \gtrsim g$ to denote that $f(x) \geq g(x) - o(g(x))$. A graph parameter $p$ is minor-closed (resp. contraction-closed) when $H \leq G \Rightarrow p(H) \leq p(G)$ (resp. $H \leq G \Rightarrow p(H) \leq p(G)$). We can now give the two following definitions:

$p$ is minor-bidimensional if

* $p$ is minor-closed, and

* $p(\boxtimes_k) \gtrsim \delta \cdot k^2$.

$p$ is contraction-bidimensional if

* $p$ is contraction-closed, and

* $p(\Gamma_k) \gtrsim \delta \cdot k^2$.

for some $\delta > 0$. In the above definitions, we use $\boxtimes_k$ for the $(k \times k)$-grid and $\Gamma_k$ for the uniformly triangulated $(k \times k)$-grid (see Figure 1). If $p$ is a minimization (resp. maximization) graph parameter, we denote by $\Pi_p$ the problem that, given a graph $G$ and a non-negative integer $k$, asks whether $p(G) \leq k$ (resp. $p(G) \geq k$). We say that a problem is *minor/contraction-bidimensional* if it is $\Pi_p$ for some bidimensional optimization parameter $p$.

A (non exhaustive) list of minor-bidimensional problems is: VERTEX COVER, FEEDBACK VERTEX SET, LONGEST CYCLE, LONGEST PATH, CYCLE PACKING, PATH PACKING, DIAMOND HITTING SET, MINIMUM MAXIMAL MATCHING, FACE COVER, and MAX BOUNDED DEGREE CONNECTED SUBGRAPH. Some problems that are contraction-bidimensional (but not minor-bidimensional) are CONNECTED VERTEX COVER, DOMINATING SET, CONNECTED DOMINATING SET, CONNECTED FEEDBACK VERTEX SET, INDUCED MATCHING, INDUCED CYCLE PACKING, CYCLE DOMINATION, CONNECTED CYCLE DOMINATION, d-SCATTERED SET, INDUCED PATH PACKING, r-CENTER, CONNECTED r-CENTER, CONNECTED DIAMOND HITTING SET, UNWEIGHTED TSP TOUR (see [14,20,44]).
<figure><img src="image_3.png" /><figcaption>Figure 1: The graph $\Gamma_9$.</figcaption></figure>

**Subquadratic grid minor/contraction property.** In order to present the meta-algorithmic potential of bidimensionality theory we need to define some *property on graph classes* that defines the horizon of its applicability.

**Definition 4 (SQGC and SQGC).** Let $\mathcal{G}$ be a graph class. We say that $\mathcal{G}$ has the *subquadratic grid minor property* (SQGM property for short) if there exist a constant $1 \le c < 2$ such that every graph $G \in \mathcal{G}$ which excludes $\boxplus_t$ as a minor, for some integer $t$, has treewidth $\mathcal{O}(t^c)$. In other words, this property holds for $\mathcal{G}$ if Proposition 2 can be proven for a sub-quadratic $f$ on the graphs of $\mathcal{G}$.

Similarly, we say that $\mathcal{G}$ has the *subquadratic grid contraction property* (SQGC property for short) if there exist a constant $1 \le c < 2$ such that every graph $G \in \mathcal{G}$ which excludes $\Gamma_t$ as a contraction, for some integer $t$, has treewidth $\mathcal{O}(t^c)$. For brevity we say that $\mathcal{G} \in \text{SQGM}(c)$ (resp. $\mathcal{G} \in \text{SQGC}(c)$) if $\mathcal{G}$ has the SQGM (resp SQGC) property for $c$. Notice that $\text{SQGC}(c) \subseteq \text{SQGM}(c)$ for every $1 \le c < 2$.

## 1.2 Algorithmic implications

The meta-algorithmic consequences of bidimensionality theory are summarised as follows. Let $\mathcal{G} \in \text{SQGM}(c)$, for $1 \le c < 2$, and let $\mathbf{p}$ be a minor-bidimensional-optimization parameter.

[A] As it was observed in [10], the problem $\Pi_{\mathbf{p}}$ can be solved in $2^{o(k)} \cdot n^{\mathcal{O}(1)}$ steps on $\mathcal{G}$, given that the computation of $\mathbf{p}$ can be done in $2^{\mathcal{O}(\text{tw}(G))} \cdot n^{\mathcal{O}(1)}$ steps (here $\text{tw}(G)$ is the treewidth of the input graph $G$). This last condition can be implied by a purely meta-algorithmic condition that is based on some variant of *Modal Logic* [37]. There is a wealth of results that yield the last condition for various optimization problems either in classes satisfying the SQGM property [18, 18, 19, 41, 42] or to general graphs [3, 7, 24].

[B] As it was shown in [26] (see also [27]), when the predicate $\phi$ can be expressed in Counting Monadic Second Order Logic (CMSOL) and $\mathbf{p}$ satisfies some additional combinatorial property called *separability*, then the problem $\Pi_{\mathbf{p}}$ admits a *linear kernel*, that is a polynomial-time algorithm that transforms $(G, k)$ to an equivalent instance $(G', k')$ of $\Pi_{\mathbf{p}}$ where $G'$ has size $\mathcal{O}(k)$ and $k' \le k$.

[C] It was proved in [22] (see also [25] and [28]), that the problem of computing $\mathbf{p}(G)$ for $G \in \mathcal{G}$ admits a *Efficient Polynomial Approximation Scheme* (EPTAS) — that is an $\epsilon$-approximation algorithm running in $f(\frac{1}{\epsilon}) \cdot n^{\mathcal{O}(1)}$ steps — given that $\mathcal{G}$ is hereditary and $\mathbf{p}$ satisfies the separability property and some reducibility property (related to CMSOL expresibility).

All above results have their counterparts for *contraction-bidimensional* problems with the difference that one should instead demand that $\mathcal{G} \in \text{SQGC}(c)$. Clearly, the applicability of all above results is delimited by the SQGM/SQGC property. This is schematically depicted in Figure 2, where the green triangles
<figure><img src="image_4.png" /><figcaption>Figure 2: The applicability of bidimensionality theory. The green lines correspond the consequences [32] while the red lines correspond to the result of this paper.</figcaption></figure>

triangles indicate the applicability of minor-bidimensionality and the red triangle indicate the applicability of contraction-bidimensionality. The aforementioned $\Omega(k^2 \cdot \log k)$ lower bound to the function $f$ of Proposition 2, indicates that $\text{SQGM}(c)$ does not contain all graphs (given that $c < 2$).

As an example we mention the well known *d-Domination Set* problem (for some $d \ge 1$), asking whether a graph $G$ has a set $S$ of at most $k$ vertices such that every vertex in $G$ is within distance at most $d$ from some vertex of $S$. *d-Domination Set* is contraction bidimensional problem that satisfies the additional meta-algorithmic conditions in $[\text{A}]$, $[\text{B}]$, and $[\text{C}]$. This implies that it can be solved in $2^{O(\sqrt{k})} \cdot n$ time, it admits a linear kernel, and its optimization version admits an EPTAS on every graph class that has the SQGC property.

The emerging direction of research is to detect the most general classes in $\text{SQGM}(c)$ and $\text{SQGC}(c)$. Concerning the SQGM property, the following result was proven in [15].

**Proposition 5.** For every graph $H$, $\text{excl}(H) \in \text{SQGM}(1)$.

A graph $H$ is an *apex graph* if it contains a vertex whose removal from $H$ results to a planar graph. For the SQGC property, the following counterpart of Proposition 5 was proven in [21].

**Proposition 6.** For every *apex graph* $H$, $\text{excl}(H) \in \text{SQGC}(1)$.

Notice that both above results concern graph classes that are defined by excluding some graph as a minor. For such graphs, Proposition 6 is indeed optimal. To see this, consider $K_h$-minor free graphs where $h \ge 6$ (these graphs are not apex graphs). Such classes do not satisfy the SQGC property: take $\Gamma_k$, add a new vertex, and make it adjacent, with all its vertices. The resulting graph excludes $\Gamma_k$ as a contraction and has treewidth $> k$.

## 1.3 String graphs

An important step extending the applicability of bidimensionality theory further than $H$-minor free graphs, was done in [23] (see also [25]).

**Definition 7** (*String graphs*, *map graphs*, and *unit disk graphs*). *Unit disk graphs* are intersections graphs of unit disks in the plane and *map graphs* are intersection graphs of face boundaries of planar graph embeddings. We denote by $U_d$ the set of unit disk graphs (resp. of $M_d$ map graphs) of maximum degree $d$.

The following was proved in [23, 25].

**Proposition 8.** For every positive integer $d$, $U_d \in \text{SQGM}(1)$ and $M_d \in \text{SQGM}(1)$.

Proposition 8 was further extended for intersection graphs of more general geometric objects (in 2 dimensions) in [32]. To explain the results of [32] we need to define a more general model of intersection graphs.
**Definition 9.** (String graphs) Let $\mathcal{L} = \{L_1, \dots, L_k\}$ be a collection of lines in the plane. We say that $\mathcal{L}$ is normal if there is no point belonging to more than two lines. The intersection graph $G_{\mathcal{L}}$ of $\mathcal{L}$, is the graph whose vertex set is $\mathcal{L}$ and where, for each $i, j$ where $1 \le i < j \le k$, the edge $\{L_i, L_j\}$ has multiplicity $|L_1 \cap L_2|$. We denote by $S_d$ the set containing every graph $G_{\mathcal{L}}$ where $\mathcal{L}$ is a normal collection of lines in the plane and where each vertex of $G_{\mathcal{L}}$ has edge-degree at most $d$. i.e., is incident to at most $d$ edges. We call $S_d$ string graphs with edge-degree bounded by $d$.

It is easy to observe that $U_d \cup \mathcal{M}_d \subseteq S_{f(d)}$ for some quadratic function $f$. Indeed, given a graph $G$ in $U_d$, for each unit disk of its representation in the plane, we can create a string that corresponds to the perimeter of the disk. As all the disks are of the same size, the intersection graph of the strings is homeomorphic to $G$. The same applies for map graphs by considering the boundaries of the faces and creating a string for each of them. Moreover, apart from the classes considered in [23], $S_d$ includes a much wider variety of classes of intersection graphs [32]. As an example, consider $C_{d,\alpha}$ as the class of all graphs that are intersection graphs of $\alpha$-convex bodies<fnref n="1" /> in the plane and have edge-degree at most $d$. In [32], it was proven that $C_{d,\alpha} \subseteq S_c$ where $c$ depends (polynomially) on $d$ and $\alpha$. Another interesting class from [32] is $\mathcal{F}_{H,\alpha}$ containing all $H$-subgraph free intersection graphs of $\alpha$-fat<fnref n="2" /> families of convex bodies. Notice $U_d$ can be seen as a special case of both $C_{d,\alpha}$ and $\mathcal{F}_{H,\alpha}$. (See [36] for other examples of classes included in $S_d$.)

<figure><img src="image_5.png" /><figcaption>Figure 3: A graphical representation of the definition of $\mathcal{G}^{(c_1,c_2)}$.</figcaption></figure>

## 1.4 Our contribution

### Graph class extensions.

**Definition 10** (($c_1, c_2$)-extension). Given a class of graph $\mathcal{G}$ and two integers $c_1$ and $c_2$, we define the ($c_1, c_2$)-extension of $\mathcal{G}$, denoted by $\mathcal{G}^{(c_1,c_2)}$, as the set containing every graph $H$ such that there exist a graph $G \in \mathcal{G}$ and a graph $J$ that satisfy $G \le^{(c_1)} J$ and $H \le^{c_2} J$ (see Figure 3 for a visualization of this construction). Keep in mind that $\mathcal{G}^{(c_1,c_2)}$ and $\mathcal{G}^{(c_2,c_1)}$ are two different graph classes. We also denote by $\mathcal{P}$ the class of all planar graphs.

Using the above notation, the two combinatorial results in [32] can be rewritten as follows:

**Proposition 11.** Let $c_1 \ge 1$ and $c_2 \ge 0$ be two integers. If $\mathcal{G} \in \text{SQGC}(c)$ for some $1 \le c < 2$, then $\mathcal{G}^{(c_1,c_2)} \in \text{SQGM}(c)$.

**Proposition 12.** For every $d \in \mathbb{N}$, $S_d \subseteq \mathcal{P}^{(1,d)}$.

We visualise the idea of the proof of Proposition 12 by some example, depicted in Figure 4. In Lemma 25 we use the same idea for a more general result. Figure 4 motivates the definition of the ($c_1, c_2$)-extension of a graph class. Intuitively, the fact that $H \in \mathcal{G}^{(c_1,c_2)}$ expresses the fact that $H$ can be seen as a “bounded” distortion of a graph in $\mathcal{G}$ (after a fixed number of “de-contractions” and contractions).

<footnote n="1">¹We call a set of points in the plane a *body* if it is homeomorphic to the closed disk $\{(x, y) | x^2 + y^2 \le 1\}$. A 2-dimensional body $B$ is a $\alpha$-convex if every two of its points can be the extremes of a line $L$ consisting of $\alpha$ straight lines and where $L \subseteq B$. Convex bodies are exactly the 1-convex bodies.</footnote>

<footnote n="2">²A collection of convex bodies in the plane is $\alpha$-fat if the ratio between the maximum and the minimum radius of a circle where all bodies of the collection can be circumscribed and inscribed respectively, is upper bounded by $a$.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 4: An example of the proof of Proposition 12. In the leftmost figure we we a collection of lines in the plane $\mathcal{L} = \{L_1, \dots, L_k\}$ whose intersection graph $G_{\mathcal{L}}$ is depicted in the rightmost figure and has maximum edge degree 9 because of line $c$ that meets other lines in 9 points, therefore $G_{\mathcal{L}} \in S_9$. To see why $G_{\mathcal{L}} \in \mathcal{P}^{(1,9)}$, one may see the leftmost figure are a planar graph $P \in \mathcal{P}$ where vertices of degree 1 are discarded. The vertices of this planar graph can be seen as the result of the contraction of the red edges (seen as subgraphs of diameter 1) in the graph $J$ in the middle, i.e., $P \leq^{(1)} J$. Finally, the intersection graph $G_{\mathcal{L}}$ can be seen as a result of the contraction in $J$ of each one of the paths, on at most 9 vertices, to a single vertex. Therefore $G_{\mathcal{L}} \leq^{\leq 9} J$, hence $G_{\mathcal{L}}$ belongs in the (1, 9)-extension of planar graphs.</figcaption></figure>

**Proposition 6**, combined with **Proposition 11**, provided the wider, so far, framework on the applicability of minor-bidimensionality: SQGM(1) contains $\mathrm{excl}(H)^{(c_1,c_2)}$ for every apex graph $H$ and positive integers $c_1, c_2$. As, by Proposition 6, $\mathcal{P} \in \mathrm{SQGC}(1)$, Proposition 11 and Proposition 12 directly classifies in SQGM(1) the graph class $S_d$, and therefore a large family of bounded degree intersection graphs (including $U_d$ and $M_d$). As a result of this, the applicability of bidimensionality theory for minor-bidimensional problems has been extended to much wider families (not necessarily minor-closed) of graph classes of geometric nature [32].

**Our main result.**

**Definition 13** (Intersection graphs). Given a graph $G$ and a set $S \subseteq V(G)$ we say that $S$ is a connected set of $G$ if $G[S]$ is a connected graph. We also define by $\mathcal{C}(G)$ the set of all connected subsets of $V(G)$. Given a $\mathcal{C} \subseteq \mathcal{C}(G)$, we define the intersection graph of $\mathcal{C}$ in $G$, denoted by $I_G(\mathcal{C})$, as the graph whose vertex set is $\mathcal{C}$, where two vertices $C_1$ and $C_2$ of $I_G(\mathcal{C})$ are connected by an edge if $C_1 \cap C_2 \neq \emptyset$, and, moreover, the multiplicity of the edge $\{C_1, C_2\}$ is equal to $|V(C_1 \cap C_2)|$. Given a graph class $\mathcal{G}$ we define the following class of graphs

$$ \mathrm{inter}(\mathcal{G}) = \bigcup_{G \in \mathcal{G}} \{I_G(\mathcal{C}) \mid \mathcal{C} \subseteq \mathcal{C}(G)\}. $$

In other words, $\mathrm{inter}(\mathcal{G})$ contains all the intersection graphs of the connected vertex subsets of each of the graphs in $\mathcal{G}$. Given a $d \in \mathbb{N}$, we define $\mathrm{inter}_d(\mathcal{G})$ as the set of graphs in $\mathrm{inter}(\mathcal{G})$ that have edge-degree at most $d$.

However, also the degree bound is maintained, as indicated by the following easy lemma.

**Lemma 14.** For every $d \in \mathbb{N}$, $S_d \subseteq \mathrm{inter}_d(\mathcal{P}) \subseteq S_{d'}$, for some $d' = O(d^2)$.

*Proof (sketch).* We deal with the less trivial statement that $\mathrm{inter}_d(\mathcal{P}) \subseteq S_{O(d^2)}$. For this, let $H \in \mathrm{inter}_d(\mathcal{P})$ such that $H = I_G(\mathcal{C})$ for some collection $\mathcal{C}$ of connected subsets of $V(G)$, for some $G \in \mathcal{P}$. We choose the planar graph $G$ so that $|V(G)| + |E(G)|$ is minimized. This means that for every $C \in \mathcal{C}$, $G[C]$ is a tree on at most $2d$ vertices. If we now replace each tree $G[C]$ by a string “surrounding” it is easy to observe that two such string cannot have more than $O(d^2)$ points in common. $\square$

Observe that Proposition 11 exhibits some apparent “lack of symmetry” as the assumption is “qualitatively stronger” than the conclusion. This does not permit the application of bidimensionality for contraction-bidimensional parameters on classes further than those of apex-minor free graphs. In other words, the results
<figure><img src="image_7.png" /><figcaption>Figure 5: The hierarchy of graph classes where Proposition 11 applies. $U_d$ and $M_d$ are the bounded-degree unit-disk and map graphs respectively (where the results of [23, 25] apply). $S_d$ are the bounded-degree string graphs, while $\text{inter}_d(\text{excl}(H))$ are the bounded-degree intersection graphs of connected sets of $H$-minor free graphs, where $H$ is an apex graph.</figcaption></figure>

in [32] covered, for the case of $S_d$, the green triangles in Figure 2 but left the red triangles open. The main result of this paper is to fill this gap by proving the following extension of Proposition 11. The main result of this paper is the following.

**Theorem 15.** Let $c_1$ and $c_2$ be two positive integers. If $G \in \text{SQGC}(c)$ for some $1 \le c < 2$, then $G^{(c_1, c_2)} \in \text{SQGC}(c)$.

**Consequences.** We call a graph class *monotone* if it is closed under taking of subgraphs, i.e., every subgraph of a graph in $G$ is also a graph in $\mathcal{G}$. A powerful consequence of Theorem 15 is the following (the proof is postponed in Section 3).

**Theorem 16.** If $G$ is a monotone graph class, where $G \in \text{SQGC}(c)$ for some $1 \le c < 2$, and $d \in \mathbb{N}$, then $\text{inter}_d(G) \in \text{SQGC}(c)$.

Combining Proposition 6 and Theorem 16 we obtain that $\text{SQGC}(1)$ contains $\text{inter}_d(\text{excl}(H))$ for every apex graph $H$. This extends the applicability horizon of contraction-bidimensionality further than apex-minor free graphs (see Figure 5). As a (very) special case of this, we have that $S_d \in \text{SQGC}(1)$. Therefore, on $S_d$, the results described in Subsection 1.2 apply for contraction-bidimensional problems as well.

This paper is organized as follows. In Section 2, we give the necessary definitions and some preliminary results. We prove Theorem 16 in Section 3 while Section 4 is dedicated to the proof of Theorem 15. We should stress that this proof is quite different than the one of Proposition 11 in [32]. Finally, Section 5 contains some discussion and open problems.

# 2 Definitions and preliminaries

We denote by $\mathbb{N}$ the set of all non-negative integers. Given $r, q \in \mathbb{N}$, we define $[r, q] = \{r, \dots, q\}$ and $[r] = [1, r]$.

All graphs in this paper are undirected, loop-less, and may have multiple edges. If a graph has no multiple edges, we call it *simple*. Given a graph $G$, we denote by $V(G)$ its vertex set and by $E(G)$ its edge set. Let $x$ be a vertex or an edge of a graph $G$ and likewise for $y$; their *distance* in $G$, denoted by $\text{dist}_G(x, y)$, is the smallest number of vertices of a path in $G$ that contains them both. Moreover if $G$ is a graph and $x \in V(G)$, we denote by $N_G^c(x)$, for each $c \in \mathbb{N}$, the set $\{y \mid y \in V(G), \text{dist}_G(x, y) \le c + 1\}$. For any set of vertices $S \subseteq V(G)$, we denote by $G[S]$ the subgraph of $G$ induced by the vertices from $S$. If $G[S]$ is connected, then we say that $S$ is a *connected vertex set of $G$*. We define the *diameter* of a connected subset $S$ as the maximum pairwise distance between any two vertices of $S$. The *edge-degree* of a vertex $v \in V(G)$ is the number of edges that are incident to it (multi-edges contribute with their multiplicity to this number).
<figure><img src="image_8.png" /><figcaption>Figure 6: The graph $\hat{\Gamma}_9$.</figcaption></figure>

**Definition 17 (Grids).** The $(k \times k)$-grid, denoted by $\boxtimes_k$, is the graph whose vertex set is $[0, k-1]^2$ and two vertices $(i, j)$ and $(i', j')$ are adjacent if $|i-i'| + |j-j'| = 1$. For $k \ge 3$, the graph $\Gamma_k$ (resp. $\hat{\Gamma}_k$), is defined if we add in $\boxtimes_k$ all the edges in $\{(i+1,j), (i,j+1)\} \mid (i,j) \in [0,k-2]^2\}$ as well as all the edges between $(k-1,k-1)$ (resp. a new vertex a) and the vertices in $\{(i,j) \mid [0,k-1]^2 \setminus [1,k-2]^2\}$ that have not been added already. For an example of $\Gamma_k$ (resp. $\hat{\Gamma}_k$), see Figure 1 (resp. Figure 6). Notice that $\Gamma_k$ is a triangulation of $\boxtimes_k$. In each of these graphs we denote the vertices of the underlying grid by their coordinates $(i,j) \in [0,k-1]^2$ agreeing that the upper-left corner (i.e., the unique vertex of degree 3) is the vertex (0,0). $\hat{\Gamma}_k$ has two vertices of degree 3, the top left and the bottom right of the grid part. We call $\Gamma_k$ the *uniformly triangulated grid* and $\hat{\Gamma}_k$ the *extended uniformly triangulated grid*.

**Definition 18 (Treewidth).** A tree-decomposition of a graph $G$, is a pair $(T, \mathcal{X})$, where $T$ is a tree and $\mathcal{X} = \{X_t : t \in V(T)\}$ is a family of subsets of $V(G)$, called *bags*, such that the following three properties are satisfied:

* $\bigcup_{t \in V(T)} X_t = V(G)$,

* for every edge $e \in E(G)$ there exists $t \in V(T)$ such that $e \subseteq X_t$, and

* $\forall v \in V(G)$, the set $T_v = \{t \in V(T) \mid v \in X_t\}$ is a connected vertex set of $T$.

The *width* of a tree-decomposition is the cardinality of the maximum size bag minus 1 and the *treewidth* of a graph $G$ is the minimum width over all the tree-decompositions of $G$. We denote the treewidth of $G$ by $\text{tw}(G)$.

**Lemma 19.** Let $G$ be a graph and let $H$ be a $c$-size contraction of $G$. Then $\text{tw}(G) \le (c+1) \cdot (\text{tw}(H)+1) - 1$.

*Proof.* By definition, since $H$ is a $c$-size contraction of $G$, there is a mapping between each vertex of $H$ and a connected set of at most $c$ edges in $G$, so that by contracting these edge sets we obtain $H$ from $G$. The endpoints of these edges form disjoint connected sets in $G$, implying a partition of the vertices of $G$ into connected sets $\{V_x \mid x \in V(H)\}$, where $|V_x| \le c+1$ for any vertex $x \in V(H)$.

Consider now a tree decomposition $(T, \mathcal{X})$ of $H$. We claim that the pair $(T, \mathcal{X}')$, where $X'_t := \bigcup_{x \in X_t} V_x$ for $t \in T$ is a tree decomposition of $G$. Clearly all vertices of $G$ are included in some bag, since all vertices of $H$ did. Every edge of $G$ with both endpoints in the same part of the partition is in a bag, as each of these vertex sets is placed as a whole in the same bag. If $e$ is an edge of $G$ with endpoints in different parts of the partition, say $V_x$ and $V_y$, then this implies that $\{x, y\} \in E(H)$. Thus, there is a node $t$ of $T$ for which $x, y \in X_t$ and therefore $e \subseteq X'_t$. Moreover, the continuity property remains unaffected, since for any vertex $x \in V(H)$ each vertex in $V_x$ induces the same subtree in $T$ that $x$ did. $\square$

In Table 1 we present all the notation that we use in this paper.
<table><caption>Table 1: Graphs, graph classes, and functions of the paper.</caption><thead><tr><th>Symbol</th><th>Combinatorial object</th><th>Definition</th></tr></thead><tbody><tr><td>⊕<sub>k</sub></td><td>(k × k)-grid</td><td>17</td></tr><tr><td>Γ<sub>k</sub></td><td>uniformly triangulated grid</td><td>17</td></tr><tr><td>Γ̃<sub>k</sub></td><td>extended uniformly triangulated grid</td><td>17</td></tr><tr><td>I<sub>G</sub>(C)</td><td>the intersection graph of a set C of connected subsets of the vertices of a graph G</td><td>13</td></tr><tr><td>G<sub>C</sub></td><td>the intersection graph of a collection C = {L<sub>1</sub>, ..., L<sub>k</sub>} of lines in the plane</td><td>13</td></tr><tr><td>P</td><td>planar graphs</td><td>10</td></tr><tr><td>S<sub>d</sub></td><td>d-bounded degree string graphs</td><td>9</td></tr><tr><td>M<sub>d</sub></td><td>d-bounded degree map graphs</td><td>7</td></tr><tr><td>U<sub>d</sub></td><td>d-bounded degree unit disk graphs</td><td>7</td></tr><tr><td>excl(H)</td><td>the class of graphs excluding the graph H as a minor</td><td>1</td></tr><tr><td>diss(G)</td><td>the graph class that is the dissolution closure of the graph class G</td><td>23</td></tr><tr><td>G<sup>(c<sub>1</sub>,c<sub>2</sub>)</sup></td><td>the graph class that is the (c<sub>1</sub>, c<sub>2</sub>)-extension of a graph class G</td><td>10</td></tr></tbody></table>

## 3 Proof of Theorem 16

We start with the following useful property of the contraction relation. We use $\delta(G)$ for the minimum number of edges that are incident to a vertex of the graph $G$. Given a vertex $v$ in $G$ incident to exactly two edges $e_1 = \{v, x\}$ and $e_2 = \{v, y\}$, the dissolution of $v$ in $G$ is the operation of removing $e_1$ and $e_2$ from $G$ and then we add the edge $\{x, y\}$. If the graph $H$ occurs from $G$ after applying some (possibly empty) sequence of vertex dissolutions, then we say that $H$ is a dissolution of $G$. We also say that $H$ is a topological minor of $G$ if $H$ the dissolution of some subgraph of $G$.

**Lemma 20.** Let $Q$ be a graph where $\delta(Q) \ge 3$ and let $H, G$ be graphs where $H$ is a dissolution of $G$. If $Q \le G$, then $Q \le H$.

*Proof.* As $Q \le G$ then there exist $\sigma: V(G) \to V(Q)$ such that for all $x \in V(Q)$, $G[\sigma^{-1}(x)]$ is a non-empty graph and for every $x, y \in V(Q)$, $\{x, y\} \in E(Q) \iff G[\sigma^{-1}(x) \cup \sigma^{-1}(y)]$ is connected.

Let $v$ be a vertex in $G$ incident to exactly two edges $e_1 = \{v, v'\}$ and $e_2 = \{v, v''\}$, and let $G'$ be the graph obtained from $G$ after the dissolution of $v$. Let $\sigma': V(G') \to V(Q)$ such that for all $z \in V(G')$, $\sigma'(z) = \sigma(z)$. As the dissolution maintains connectivity, we have that for every $x, y \in V(Q)$, $\{x, y\} \in E(Q) \iff G[\sigma'^{-1}(x) \cup \sigma'^{-1}(y)]$ is connected. Moreover, as $\delta(Q) \ge 3$, we know that for each $x \in V(Q)$, there exists $z \in \sigma^{-1}(x)$ such that $z$ has edge degree at least 3. In particular we know that $z$ is different from $v$. So we have that $G[\sigma'^{-1}(x)]$ is a non-empty graph. Thus $Q \le G'$. The lemma follows by iterating this argument. $\square$

**Definition 21** (The function **bcg**). Given a graph $G$, we define **bcg**($G$) as the maximum $k$ for which $G$ can be contracted to the uniformly triangulated grid $\Gamma_k$.

Notice that **bcg** is a contraction-closed parameter, i.e., if $H \le G$, then **bcg**($H$) $\le$ **bcg**($G$).

**Lemma 22.** Let $H$ and $G$ be two graphs. If $H$ is a dissolution of $G$, then $\text{bcg}(H) = \text{bcg}(G)$.

*Proof.* The fact that $\text{bcg}(H) \le \text{bcg}(G)$ follows from the fact that $H$ is also a contraction of $G$ and taking into account the contraction-closedness of $\text{bcg}$. The fact that $\text{bcg}(G) \le \text{bcg}(H)$ follows by taking into account that $\delta(\Gamma_k) \ge 3$ and applying inductively Lemma 20 to the vertices of degree 2 in $G$ that need to be dissolved in order to transform $G$ to $H$. $\square$

**Definition 23.** Given a graph class $\mathcal{G}$, we define the dissolution closure of $\mathcal{G}$ as the graph class $\text{diss}(\mathcal{G})$ containing all the dissolutions of the graphs in $\mathcal{G}$.
We observe the following.

**Lemma 24.** If $\mathcal{G} \in \mathbf{SQGC}(c)$ for some $1 \le c < 2$, then $\mathrm{diss}(\mathcal{G}) \in \mathbf{SQGC}(c)$.

*Proof.* Suppose that $\mathcal{G} \in \mathbf{SQGC}(c)$ for some $1 \le c < 2$, which implies that

$$ \forall G \in \mathcal{G} \ \mathrm{tw}(G) \le \lambda \cdot (\mathbf{bcg}(G))^c. \qquad (1) $$

Let $H \in \mathrm{diss}(\mathcal{G})$ and let $G \in \mathcal{G}$ such that $H$ is a dissolution of $G$. By Lemma 22, $\mathbf{bcg}(H) = \mathbf{bcg}(G)$ and from (1), $\mathrm{tw}(G) \le \lambda(\mathbf{bcg}(H))^c$. As $H$ is a minor of $G$, we have that $\mathrm{tw}(H) \le \lambda(\mathbf{bcg}(H))^c$ and the lemma follows. □

The next lemma uses as a departure point the same idea as the one of proof of Proposition 12, visualized by the example of Figure 4.

**Lemma 25.** If $\mathcal{G}$ is a graph class that is topological minor closed, then $\mathrm{inter}_d(\mathcal{G}) \subseteq \mathcal{G}^{(d+1,d-1)}$.

*Proof.* Let $H$ be a graph on $h$ vertices in $\mathrm{inter}_d(\mathcal{G})$, for some $d \in \mathbb{N}$. This means that there is a graph $G$ in $\mathcal{G}$ such that we can see the vertices of $H$ as a set $C = \{C_1, \dots, C_h\}$ of connected subsets of $G$ and each multi-edge $e = \{C_i, C_j\}$ of $H$ corresponds to two mutually intersecting subsets of $C$ and the multiplicity of $e$ is $|C_i \cap C_j|$. For every $\{i, j\} \in \binom{h}{2}$, we set $V_{i,j} = C_i \cap C_j$, $m_{i,j} = |C_i \cap C_j|$, and we assume that $e_{i,j} = \{C_i, C_j\}$ is a multi-edge of $H$ of multiplicity $m_{i,j}$ (if this edge does not exists in $H$, then the multiplicity of $e_{i,j}$ is 0).

We define $V_i = \cup_{j \in [h]} V_{i,j}$, for every $i \in [h]$ and also set $V = \cup_{i \in [h]} V_i$. Notice that, for each $i \in [h]$, $|V_i|$ is upper bounded by the edge-degree, in $H$, of the vertex $C_i$, therefore, $|V_i| \le d$ for each $i \in [h]$. Also, a vertex in $V$ cannot belong in more that $d+1$ distinct $C_i$'s as, otherwise $H$ would contain a clique with at least $d+2$ vertices. As $H \in \mathrm{inter}_d(\mathcal{G})$, this is not possible.

Recall that, for each $i \in [h]$, $V_i$ is a subset of $C_i$ and let $T_i$ be a minimum-size tree of $G[C_i]$ containing the vertices of $V_i$. We partition the set of vertices of $T_i$ into three sets $V_i, \bar{V}_i, D_i$ where among the vertices in $V(T_i) \setminus V_i, D_i$ are the vertices of degree 2 and $\bar{V}_i$ are the rest. By minimality, the leaves of $T_i$ belong in $V_i$. Moreover, there is no vertex in $\bar{V}_i$ that belongs to some other $\bar{V}_{i'}$, $i \in [h] \setminus \{i\}$. We denote by $\hat{T}_i$ the tree obtained from $T_i$ if we dissolve in $T_i$ all vertices of $D_i$. That way we can still partition the vertices of each $\hat{T}_i$, $i \in [h]$, into $V_i$ and $\bar{V}_i$. Also, it is easy to see that $\hat{T}_i$ has diameter at most $|V_i| - 1 \le d - 1$.

We define the graph $G' := \cup_{i \in [h]} \hat{T}_i$. Notice that $G'$ is obtained from $\cup_{i \in [h]} T_i$ (that is a subgraph of $G$) after we dissolve all vertices in $\cup_{i \in [h]} D_i$. Therefore $G'$ is a topological minor of $G$, thus $G' \in \mathcal{G}$. We consider the collection $\mathcal{T} = \{\hat{T}_1, \dots, \hat{T}_h\}$ of connected subgraphs of $G'$.

We define the graph $J$ to be the disjoint union of the $h$ trees in $\mathcal{T}$ in which, for each $x \in V$, we add a clique between all the copies of $x$. Notice that each added clique has size at least 2 and at most $d+1$.

Observe now that $G' \le (d+1)$, $J$, as $G'$ is obtained after contracting in $J$ the aforementioned pairwise disjoint cliques. Moreover, $H \le^{d-1} J$ as $H$ is obtained after we contract in $J$ each $\hat{T}_i$ (of diameter $\le d - 1$) to a single vertex. As $G' \in \mathcal{G}$, we conclude that $H \in \mathcal{G}^{(d+1,d-1)}$ as required. □

We are now ready to prove Theorem 16.

*Proof of Theorem 16.* Let $\mathcal{G}$ be a monotone graph class in $\mathbf{SQGC}(c)$ for some $1 \le c < 2$ and let $\mathcal{D} = \mathrm{diss}(\mathcal{G})$. From Lemma 24, $\mathcal{D} \in \mathbf{SQGC}(c)$ and by the monotonicity of $\mathcal{G}$, we have that $\mathrm{diss}(\mathcal{G})$ is closed under taking of topological minors. Therefore, from Lemma 25, $\mathrm{inter}_d(\mathcal{D}) \subseteq \mathcal{D}^{(d+1,d-1)}$ and from Theorem 15, $\mathrm{inter}_d(\mathcal{D}) \in \mathbf{SQGC}(c)$. The result follows because $\mathcal{G} \subseteq \mathcal{D}$, as this implies that $\mathrm{inter}_d(\mathcal{G}) \subseteq \mathrm{inter}_d(\mathcal{D})$. □

# 4 Proof of Theorem 15

Let $H$ and $G$ be graphs and $c$ be a non-negative integer. If $H \le_{\sigma}^c G$, then we say that $H$ is a $\sigma$-contraction of $G$, and denote this by $H \le_{\sigma} G$.

Before we proceed the the proof of Theorem 15 we make first the following three observations. (In all statements, we assume that $G$ and $H$ are two graphs and $\sigma: V(G) \to V(H)$ such that $H$ is a $\sigma$-contraction of $G$.)
*Observation 26.* Let $S$ be a connected subset of $V(H)$. Then the set $\bigcup_{x \in S} \sigma^{-1}(x)$ is connected in $G$.

*Observation 27.* Let $S_1 \subseteq S_2 \subseteq V(H)$. Then $\sigma^{-1}(S_1) \subseteq \sigma^{-1}(S_2) \subseteq V(G)$.

*Observation 28.* Let $S$ be a connected subset of $V(G)$. Then the diameter of $\sigma(S)$ in $H$ is at most the diameter of $S$ in $G$.

Given a graph $G$ and $S_1, S_2 \subseteq V(G)$ we say that $S_1$ and $S_2$ *touch* if either $S_1 \cap S_2 \neq \emptyset$ or there is an edge of $G$ with one endpoint in $S_1$ and the other in $S_2$.

We say that a collection $\mathcal{R}$ of paths of a graph is *internally disjoint* if none of the internal vertices, i.e., none of the vertex of degree 2, of some path in $\mathcal{R}$ is a vertex of some other path in $\mathcal{R}$. Let $\mathcal{A}$ be a collection of subsets of $V(G)$. We say that $\mathcal{A}$ is a *connected packing* of $G$ if its elements are connected and pairwise disjoint. If additionally $\mathcal{A}$ is a partition of $V(G)$, then we say that $\mathcal{A}$ is a *connected partition* of $G$ and if, additionally, all its elements have diameter bounded by some integer $c$, then we say that $\mathcal{A}$ is a *c-diameter partition* of $G$.

## 4.1 $\Lambda$-state configurations.

**Definition 29.** ($\Lambda$-state configurations) Let $G$ be a graph. Let $\Lambda = (\mathcal{W}, \mathcal{E})$ be a graph whose vertex set is a connected packing of $G$, i.e., its vertices are connected subsets of $V(G)$. A $\Lambda$-state configuration of a graph $G$ is a quadruple $\mathcal{S} = (\mathcal{X}, \alpha, \mathcal{R}, \beta)$ where

1. $\mathcal{X}$ is a connected packing of $G$,

2. $\alpha$ is a bijection from $\mathcal{W}$ to $\mathcal{X}$ such that for every $W \in \mathcal{W}$, $W \subseteq \alpha(W)$,

3. $\mathcal{R}$ is a collection of internally disjoint paths of $G$, and

4. $\beta$ is a bijection from $\mathcal{E}$ to $\mathcal{R}$ such that if $\{W_1, W_2\} \in \mathcal{E}$ then the endpoints of $\beta(\{W_1, W_2\})$ are in $W_1$ and $W_2$ and $V(\beta(\{W_1, W_2\})) \subseteq \alpha(W_1) \cup \alpha(W_2)$.

**Definition 30.** (States, freeways, clouds, and coverage) A $\Lambda$-state configuration $\mathcal{S} = (\mathcal{X}, \alpha, \mathcal{R}, \beta)$ of $G$ is *complete* if $\mathcal{X}$ is a partition of $V(G)$. We refer to the elements of $\mathcal{X}$ as the *states* of $\mathcal{S}$ and to the elements of $\mathcal{R}$ as the *freeways* of $\mathcal{S}$. We define $\text{indep}(\mathcal{S}) = V(G) \setminus \bigcup_{X \in \mathcal{X}} X$. Note that if $\mathcal{S}$ is a $\Lambda$-state configuration of $G$, $\mathcal{S}$ is complete if and only if $\text{indep}(\mathcal{S}) = \emptyset$.

Let $\mathcal{A}$ be a $c$-diameter partition of $G$. We refer to the sets of $\mathcal{A}$ as the $\mathcal{A}$-clouds of $G$. We define $\text{front}_{\mathcal{A}}(\mathcal{S})$ as the set of all $\mathcal{A}$-clouds of $G$ that are not subsets of some $X \in \mathcal{X}$. Given a $\mathcal{A}$-cloud $C$ and a state $X$ of $\mathcal{S}$ we say that $C$ *shadows* $X$ if $C \cap X \neq \emptyset$. The coverage $\text{cov}_{\mathcal{S}}(C)$ of an $\mathcal{A}$-cloud $C$ of $G$ is the number of states of $\mathcal{S}$ that are shadowed by $C$. A $\Lambda$-state configuration $\mathcal{S} = (\mathcal{X}, \alpha, \mathcal{R}, \beta)$ of $G$ is *$\mathcal{A}$-normal* if its satisfies the following conditions:

(A) If a $\mathcal{A}$-cloud $C$ intersects some $W \in \mathcal{W}$, then $C \subseteq \alpha(W)$.

(B) If a $\mathcal{A}$-cloud over $\mathcal{S}$ intersects the vertex set of at least two freeways of $\mathcal{S}$, then it shadows at most one state of $\mathcal{S}$.

We define $\text{cost}_{\mathcal{A}}(\mathcal{S}) = \sum_{C \in \text{front}_{\mathcal{A}}(\mathcal{S})} \text{cov}_{\mathcal{S}}(C)$. Given $S_1 \subseteq S_2 \subseteq V(G)$ where $S_1$ is connected, we define $\text{cc}_G(S_2, S_1)$ as the (unique) connected component of $G[S_2]$ that contains $S_1$.

## 4.2 Triangulated grids inside triangulated grids

The next lemma is the main combinatorial engine of our results. We assume that $H \leq^c G$ and $\Gamma_k \leq G$. Here $H$ should be seen as the result of a “shrink” of $G$ in the sense that $G$ can be contracted to $H$ so that each vertex of $H$ is created after a bounded number of contractions. The lemma states that if $G$ can be contracted to a uniformly triangulated grid, then $H$, as a “shrunk version” of $G$, can also be contracted to a uniformly triangulated grid that is no less than linearly smaller.
The proof strategy views the graph $G$ as being contracted into a uniformly triangulated grid $\Gamma_k$ (see Figure 7), we choose a scattered set of “capitals” in it (the black vertices in Figure 7). Then we set up a “conquest” procedure where each capital is trying to expand to a country. This procedure has three phases. The first phase is the expansion face where each country tries to incorporate unconquested territories around it (the limits of this expansion is depicted by the red cycles in Figure 7). The second phase is the clash face, where different countries are fighting for disputed territories. Finally, the third phase is the annex phase, where each country naturally incorporates remaining enclaves. The end of this war creates a set of countries occupying the whole $G$ that, when contracted, give rise to a uniformly triangulated grid $\Gamma_{k'}$, where $k' = \Omega(k)$.

**Lemma 31.** Let $G$ and $H$ be graphs and $c, k$ be non-negative integers such that $H \leq^c G$ and $\Gamma_k \leq G$. Then $\Gamma_{k'} \leq H$ where $k' = \lfloor \frac{k-1}{2c+1} \rfloor - 1$.

*Proof.* Let $k^* = 1 + (2c+1) \cdot (k' + 1)$ and observe that $k^* \leq k$, therefore $\Gamma_{k^*} \leq \Gamma_k \leq G$. For simplicity we use $\Gamma = \Gamma_{k^*}$. Let $\phi: V(G) \to V(H)$ such that $H \leq^c \phi G$ and let $\sigma: V(G) \to \bar{V}(\Gamma)$ such that $\Gamma \leq_{\sigma} G$. We define $\mathcal{A} = \{\phi^{-1}(a) | a \in V(H)\}$. Notice that $\mathcal{A}$ is a $c$-diameter partition of $G$.

For each $(i, j) \in [0, k' + 1]^2$, we define $b_{i,j}$ to be the vertex of $\Gamma$ with coordinate $(i(2c+1), j(2c+1))$. We set $Q_{\text{in}} = \{b_{i,j} \mid (i,j) \in [1, k']^2\}$ and $Q_{\text{out}} = \{b_{i,j} \mid (i,j) \in [0, k' + 1]^2\} \setminus Q_{\text{in}}$. Let also $Q = Q_{\text{in}} \cup \{b_{\text{out}}\}$ were $b_{\text{out}}$ is a new element that does not belong in $Q_{\text{in}}$. Here $b_{\text{out}}$ can be seen as a vertex that “represents” all vertices in $Q_{\text{out}}$.

Let $q, p$ be two different elements of $Q$. We say that $q$ and $p$ are linked if they both belong in $Q_{\text{in}}$ and their distance in $\Gamma$ is $2c+1$ or one of them is $b_{\text{out}}$ and the other is $b_{i,j}$ where $i \in \{1, k'\}$ or $j \in \{1, k'\}$.

For each $q \in Q_{\text{in}}$, we define $W_q = \sigma^{-1}(q)$. $W_q$ is connected by the definition of $\sigma$. In case $q = b_{\text{out}}$ we define $W_q = \bigcup_{q' \in Q_{\text{out}}} \sigma^{-1}(q')$. Note that as $Q_{\text{out}}$ is a connected set of $\Gamma$, then, by Observation 26, $W_{b_{\text{out}}}$ is connected in $G$. We also define $\mathcal{W} = \{W_q \mid q \in Q\}$. Given some $q \in Q$ we call $W_q$ the $q$-capital of $G$ and a subset $S$ of $V(G)$ is a capital of $G$ if it is the $q$-capital for some $q \in Q$. Notice that $\mathcal{W}$ is a connected packing of $V(G)$.

Let $q \in Q$. If $q \in Q_{\text{in}}$ then we set $N_q = N_{\Gamma}^c(q)$. If $q = b_{\text{out}}$, then we set $N_q = \bigcup_{q' \in Q_{\text{out}}} N_{\Gamma}^c(q')$. Note that for every $q \in Q$, $N_q \subseteq V(\Gamma)$. For every $q \in Q$, we define $X_q = \sigma^{-1}(N_q)$. Note that $X_q \subseteq V(G)$. We also set $\mathcal{X} = \{X_q \mid q \in Q\}$. Let $q$ and $p$ we two linked elements of $Q$. If both $q$ and $p$ belong to $Q_{\text{in}}$, and therefore are vertices of $\Gamma$, then we define $Z_{p,q}$ as the unique shortest path between them in $\Gamma$. If $p = b_{\text{out}}$ and $q \in Q_{\text{in}}$, then we know that $q = b_{i,j}$ where $i \in \{1, k'\}$ or $j \in \{1, k'\}$. In this case we define $Z_{p,q}$ as any shortest path in $\Gamma$ between $b_{i,j}$ and the vertices in $Q_{\text{out}}$. In both cases, we define $P_{p,q}$ by picking some path between $W_p$ and $W_q$ in $G[\sigma^{-1}(V(Z_{p,q}))]$ such that $|V(P_{p,q}) \cap W_q| = 1$ and $|V(P_{p,q}) \cap W_p| = 1$.

Let $\mathcal{E} = \{\{W_p, W_q\} \mid p \text{ and } q \text{ are linked}\}$ and let $\Lambda = (\mathcal{W}, \mathcal{E})$. Notice that $\Lambda$ is isomorphic to $\hat{\Gamma}_{k'}$ and consider the isomorphism that correspond each vertex $q = b_{i,j}$, $i, j \in [1, k']^2$ to the vertex with coordinates $(i, j)$. Moreover $b_{\text{out}}$ corresponds to the apex vertex of $\hat{\Gamma}_{k'}$.

Let $\alpha: \mathcal{W} \to \mathcal{X}$ such that for every $q \in Q$, $\alpha(W_q) = X_q$. Let also $\mathcal{R} = \{P_{p,q} \mid p, q \in Q, p \text{ and } q \text{ are linked}\}$. We define $\beta: \mathcal{E} \to \mathcal{R}$ such that if $q$ and $p$ are linked, then $\beta(W_q, W_p) = P_{p,q}$. We use notation $\mathcal{S} = (\mathcal{X}, \alpha, \mathcal{R}, \beta)$.

**Claim 32.** $\mathcal{S}$ is an $\mathcal{A}$-normal $\Lambda$-state configuration of $G$.

*Proof of Claim 32.* We first see that $\mathcal{S}$ is a $\Lambda$-state configuration of $G$. Condition 1 follows by the definition of $X_q$ and Observation 26. Condition 2 follows directly by the definitions of $W_q$ and $X_q$. For Condition 3, we first observe that, by the construction of $\Gamma$ and the definition of $Z_{p,q}$, for any two pairs $p, q$ and $p', q'$ of pairwise linked elements of $Q$, the paths $Z_{p,q}$ and $Z_{p',q'}$ are internally vertex disjoined paths of $\Gamma$. It implies that $P_{p,q}$ and $P_{p',q'}$ can intersect each other only on the vertices of $W_p \cup W_q \cup W_{p'} \cup W_{q'}$. But $P_{p,q}$ (resp. $P_{p',q'}$), by construction contains only two vertices of $W_p \cup W_q \cup W_{p'} \cup W_{q'}$ that are the extremities of $P_{p,q}$, (resp. $P_{p',q'}$). So $P_{p,q}$ and $P_{p',q'}$ are internally vertex disjoined, as required. For Condition 4, assume that $\{W_p, W_q\} \in \mathcal{E}$. The fact that the endpoints of $\beta(\{W_p, W_q\})$ are in $W_p$ and $W_q$ follows directly by the definition of $\beta(\{W_p, W_q\}) = P_{p,q}$. It remains to prove that $V(\beta(\{W_p, W_q\})) \subseteq \alpha(W_p) \cup \alpha(W_q)$ or equivalently, that $V(P_{p,q}) \subseteq X_p \cup X_q$. Observe that, if both $p, q \in Q_{\text{in}}$, then every vertex in the shortest
<figure><img src="image_9.png" /><figcaption>Figure 7: A visualization of the proof of Lemma 31. In this whole graph $\Gamma_k$, we initialize our reaserch of $\hat{\Gamma}_{k'}$ such that every internal red hexagon will become a vertex of $\hat{\Gamma}_{k'}$ and correspond to a state and the border, also circle by a red line will become the vertex $b_{\text{out}}$. The blue edges correspond to the freeways. Red cycles correspond to the boundaries of the starting countries. Blue paths between big-black vertices are the freeways. Big-black vertices are the capitals.</figcaption></figure>

path $Z_{p,q}$ should be within distance $c$ from either $p$ or $q$. Similarly, if $p \in Q_{\text{in}}$ and $q = b_{\text{out}}$, then every vertex in the shortest path $Z_{p,q}$ should be within distance $c$ from either $p$ or some vertex in $Q_{\text{out}}$. So for every $p, q \in Q$, with $p \neq q$, $Z_{p,q} \subseteq N_p \cup N_q$. By Observation 27, every vertex in $\sigma^{-1}(V(Z_{p,q}))$ belongs to $X_p \cup X_q$ and the required follows as $V(P_{p,q}) \subseteq \sigma^{-1}(V(Z_{p,q}))$. This completes the proof that $S$ is a $\Lambda$-state configuration of $G$.

We now prove that $S$ is $\mathcal{A}$-normal. Recall that $\mathcal{A}$ be a c-diameter partition of $G$. Let $C$ be a $\mathcal{A}$-cloud and let $C' = \sigma(C)$ be a subset of $V(\Gamma)$. As $C$ is of diameter at most $c$, then, from Observation 28, $C'$ is also of diameter at most $c$. Notice that if $C$ intersects some member $W$ of $\mathcal{W}$, then $C' = \sigma(C)$ also intersects $\sigma(W)$, therefore $C'$ intersects some element of $Q_{\text{in}} \cup Q_{\text{out}}$. Assume $C'$ contains $p \in Q_{\text{in}} \cup Q_{\text{out}}$, then $C' \subseteq N_p$. From Observation 26, $C \subseteq X_p = \alpha(W_p)$, therefore $C$ satisfies Condition (A).

By construction, the distance in $\Gamma$ between two elements of $Q_{\text{in}}$ is either $2c+1$ or at least $4c+2$. The distance in $\Gamma$ between on elements of $Q_{\text{in}}$ and any element of $Q_{\text{out}}$ is a multiple of $2c+1$. This implies that if $p, q \in Q$, $p \neq q$, $N_p \cap C' \neq \emptyset$, and $N_q \cap C' \neq \emptyset$, then $p$ and $q$ are linked.

By construction, if $p$ and $q$ are linked, then for every $r \in Q$ and every $u \in Z_{p,q}$, $\text{dist}_{\Gamma}(r, u) \ge$
$\min(\mathbf{dist}_{\Gamma}(r, p), \mathbf{dist}_{G}(r, q))$, where for every $x \in Q_{in}$, the quantity $\mathbf{dist}_{\Gamma}(x, b_{out})$ is interpreted as $\min\{\mathbf{dist}_{\Gamma}(x, q') | q' \in Q_{out}\}$. This implies that if $C'$ intersects $Z_{p,q}$ for some $p, q \in Q$, then for every $r \in Q \setminus \{p, q\}$, then $C'$ does not intersect $N_r$. We will use this fact in the next paragraph towards completing the proof of Condition (B).

We now claim that if $C'$ intersects two distinct paths in $\{Z_{p,q} | (p,q) \in Q^2, p \neq q\}$, then $C'$ intersects at most one of the sets in $\{N_{q'} | q' \in Q\}$. Let $Z_{p,q}$ and $Z_{p',q'}$ be two distinct paths intersected by $C'$. We argue first that $p, q, p', q'$ cannot be all different. Indeed, if this is the case, as $C'$ intersects $Z_{p,q}$ then $C'$ cannot intersect $N_{p'}$ or $N_{q'}$ as $p', q' \notin \{p, q\}$. As $Z_{p',q'} \subseteq N_{q'} \cup N_{p'}$, we have a contradiction. Assume now that $p = p'$ and $q \neq q'$. As $C'$ intersects $Z_{p,q}$, then it does not intersect $N_r$ for any $r \in Q \setminus \{p, q\}$, and as it intersects $Z_{p,q'}$, then it does not intersect $N_r$ for any $r \in Q \setminus \{p, q'\}$. We obtain that $C'$ intersects at most one of the sets in $\{N_r | r \in Q\}$ that is $N_p$. By definition of the states, we obtain that $C$ shadows at most one state that is $X_p$. That completes the proof of condition (B). $\diamond$

We define below three ways to transform a $\Lambda$-state configuration of $G$. In each of them, $S = (\mathcal{X}, \alpha, \mathcal{R}, \beta)$ is an $\mathcal{A}$-normal $\Lambda$-state configuration of $G$ and $C$ is an $\mathcal{A}$-cloud in $\text{front}_{\mathcal{A}}(S)$.

1. The expansion procedure applies when $C$ intersects at least two freeways of $S$. Let $X$ be the state of $S$ shadowed by $C$ (this state is unique because of property (B) of $\mathcal{A}$-normality). We define $(\mathcal{X}', \alpha', \mathcal{R}', \beta') = \text{expand}(S, C)$ such that

- $\mathcal{X}' = \mathcal{X} \setminus \{X\} \cup \{X \cup C\}$,

- for each $W \in \mathcal{W}$, $\alpha'(W) = X'$ where $X'$ is the unique set of $\mathcal{X}'$ such that $W \subseteq X'$,

- $\mathcal{R}' = \mathcal{R}$, and $\beta' = \beta$.

2. The clash procedure applies when $C$ intersects exactly one freeway $P$ of $S$. Let $X_1, X_2$ be the two states of $S$ that intersect this freeway. Notice that $P = \beta(\alpha^{-1}(X_1), \alpha^{-1}(X_2))$, as it is the only freeway with vertices in $X_1$ and $X_2$. Assume that $(C \cap V(P)) \cap X_1 \neq \emptyset$ (if, not, then swap the roles of $X_1$ and $X_2$). We define $(\mathcal{X}', \alpha', \mathcal{R}', \beta') = \text{clash}(S, C)$ as follows:

- $\mathcal{X}' = \{X_1 \cup C\} \cup \bigcup_{X \in \mathcal{X} \setminus \{X_1\}} \{cc_G(X \setminus C, \alpha^{-1}(X))\}$ (notice that $\alpha^{-1}(X) \subseteq X \setminus C$, for every $X \in \mathcal{X}$, because of property (A) of $\mathcal{A}$-normality),

- for each $W \in \mathcal{W}$, $\alpha'(W) = X'$ where $X'$ is the unique set of $\mathcal{X}'$ such that $W \subseteq X'$,

- $\mathcal{R}' = \mathcal{R} \setminus \{P\} \cup \{P'\}$, where $P' = P_1 \cup P^* \cup P_2$ is defined as follows: let $s_i$ be the first vertex of $C$ that we meet while traversing $P$ when starting from its endpoint that belongs in $W_i$ and let $P_i$ the subpath of $P$ that we traversed that way, for $i \in \{1, 2\}$. We define $P^*$ by taking any path between $s_1$ and $s_2$ inside $G[C]$, and

- $\beta' = \beta \setminus \{(W_1, W_2), P\} \cup \{\{W_1, W_2\}, P'\}$.

3. The annex procedure applies when $C$ intersects no freeway of $S$ and touches some country $X \in \mathcal{X}$. We define $(\mathcal{X}', \alpha', \mathcal{R}', \beta') = \text{anex}(S, C)$ such that

- $\mathcal{X}' = \{X_1 \cup C\} \cup \bigcup_{X \in \mathcal{X} \setminus \{X_1\}} \{cc_G(X \setminus C, \alpha^{-1}(X))\}$ (notice that $\alpha^{-1}(X) \subseteq X \setminus C$, for every $X \in \mathcal{X}$, because of property (A) of $\mathcal{A}$-normality),

- for each $W \in \mathcal{W}$, $\alpha'(W) = X'$ where $X'$ is the unique set of $\mathcal{X}'$ such that $W \subseteq X'$,

- $\mathcal{R}' = \mathcal{R}$, and $\beta' = \beta$.

**Claim 33.** Let $S = (\mathcal{X}, \alpha, \mathcal{R}, \beta)$ be an $\mathcal{A}$-normal $\Lambda$-state configuration of $G$, and $C \in \text{front}_{\mathcal{A}}(S)$. Let $S' = \text{action}(S, C)$ where $\text{action} \in \{\text{expand}, \text{clash}, \text{anex}\}$. Then $S'$ is an $\mathcal{A}$-normal $\Lambda$-state configuration of $G$ where $\text{cost}(S', \mathcal{A}) \le \text{cost}(S, \mathcal{A})$. Moreover, if $\text{cov}_S(C) \ge 1$, then $\text{cost}(S', \mathcal{A}) < \text{cost}(S, \mathcal{A})$ and if $\text{cov}_S(C) = 0$ (which may be the case only when $\text{action} = \text{anex}$), then $|\text{indep}(S')| < |\text{indep}(S)|$.
Proof of Claim 33. We first show that $S'$ is an $\mathcal{A}$-normal $\Lambda$-state configuration of $G$. In each case, the construction of $S'$ makes sure that $X'$ is a connected packing of $G$ and that the countries are updated in a way that their capitals remain inside them. Moreover, the highways are updated so to remain internally disjoint and inside the corresponding updated countries. We next prove that $S'$ is $\mathcal{A}$-normal. Condition (A) is invariant as the cloud we take into consideration cannot intersect any $W \in \mathcal{W}$ and a cloud intersecting some capital $W \in \mathcal{W}$ cannot be disconnected from $W$. It now remains to prove condition (B). Because of Condition 4 of the definition of a $\Lambda$-state configuration, if a cloud $C$ intersects a freeway, then it shadows at least one state. Now assume that a cloud $C$ intersects two freeways in $S'$, then by construction of $S'$, it also intersects at least the two same freeways in $S$. This along with the fact that $S$ satisfies Condition (B), implies that $S'$ satisfies condition (B) as well, as required.

Notice that, for any cloud $C^* \in \mathcal{A} \setminus \{C\}$, if $C^*$ does not intersect a state $X$ in $S$, then the corresponding state $X'$ in $S'$, i.e., the state $X' = \alpha'(\alpha^{-1}(X))$, also does not intersect $C^*$. This means that $\text{cost}(S', \mathcal{A}) \le \text{cost}(S, \mathcal{A})$.

Notice now that by the construction of $S'$, $C$ is not in $\text{front}_{\mathcal{A}}(S')$. In the case where $\text{cov}_S(C) \ge 1$ we have that $\text{cost}(S', \mathcal{A}) < \text{cost}(S, \mathcal{A})$.

Notice that the case where $\text{cov}_S(C) = 0$ happens only when action = anex and there is an edge with one endpoint in $C$ and one in some country $X^*$ of $S$ that does not intersect $C$. Moreover $\text{cc}_G(X \setminus C, \alpha^{-1}(X)) = X$, for every state $X$ of $S$. This implies that $\text{indep}(S') \subseteq \text{indep}(S)$. As $C \subseteq \text{indep}(S)$ and $C \cap \text{indep}(S') = \emptyset$, we conclude that $|\text{indep}(S')| < |\text{indep}(S)|$ as required. $\diamond$

To continue with the proof of Lemma 31 we explain how to transform the $\mathcal{A}$-normal $\Lambda$-state configuration $S$ of $G$ to a complete one. This is done in two phases. First, as long as there is an $\mathcal{A}$-cloud $C \in \text{front}(S)$ where $\text{cov}_S(C) \ge 1$, we apply one of the above three procedures depending on the number of freeways intersected by $C$. We again use $S$ to denote the $\mathcal{A}$-normal $\Lambda$-state configuration of $G$ that is created in the end of this first phase. Notice that, as there is no $\mathcal{A}$-cloud with $\text{cov}_S(C) \ge 1$, then $\text{cost}_{\mathcal{A}}(S) = 0$. The second phase is the application of $\text{anex}(S, C)$, as long as some $C \in \text{front}_{\mathcal{A}}(S)$ is touching some of the countries of $S$. We claim that this procedure will be applied as long as there are vertices in $\text{indep}(S)$. Indeed, if this is the case, the set $\text{front}_{\mathcal{A}}(S)$ is non-empty and by the connectivity of $G$, there is always a $C \in \text{front}_{\mathcal{A}}(S)$ that is touching some country of $S$. Therefore, as $\text{cost}_{\mathcal{A}}(S) = 0$ (by Claim 33), procedure $\text{anex}(S, C)$ will be applied again.

By Claim 33, $|\text{indep}(S)|$ is strictly decreasing during the second phase. We again use $S$ for the final outcome of this second phase. We have that $\text{indep}(S) = \emptyset$ and we conclude that $S$ is a complete $\mathcal{A}$-normal $\Lambda$-state configuration of $G$ such that $|\text{front}_{\mathcal{A}}(S)| = 0$.

We are now going to create a graph isomorphic to $\Lambda$ only by doing contractions in $G$. For this we use $S$, a complete $\mathcal{A}$-normal $\Lambda$-state configuration of $G$ such that $|\text{front}_{\mathcal{A}}(S)| = 0$, obtained as described before. We contract in $G$ every country of $S$ into a unique vertex. This can be done because the countries of $S$ are connected. Let $G'$ be the resulting graph. By construction of $S$, $G'$ is a contraction of $H$. Because of Condition 4 of $\Lambda$-state configuration, every freeway of $S$ becomes an edge in $G'$. This implies that there is a graph isomorphic to $\Lambda$ that is a subgraph of $G'$. So $\hat{\Gamma}_{k'}$ is isomorphic to a subgraph of $G'$ with the same number of vertices. Let see $\hat{\Gamma}_{k'}$ as a subgraph of $G'$ and let $e$ be an edge of $G'$ that is not an edge of $\hat{\Gamma}_{k'}$. As $e$ is an edge of $G'$, this implies that in $G$, there is two states of $S$ such that there is no freeway between them but still an edge. This is not possible by construction of $S$. We deduce that $G'$ is isomorphic to $\hat{\Gamma}_{k'}$. Moreover, as $|\text{front}_{\mathcal{A}}(S)| = 0$, then every cloud is a subset of a country. This implies that $G'$ is also a contraction of $H$. By contracting in $G'$ the edge corresponding to $\{a, (k' - 1, k' - 1)\}$ in $\hat{\Gamma}_{k'}$, we obtain that $\Gamma_{k'}$ is a contraction of $H$. Lemma 31 follows. $\square$

Proof of Theorem 15. Let $\lambda, c, c_1$, and $c_2$ be integers. It is enough to prove that there exists an integer $\lambda' = \mathcal{O}(\lambda \cdot c_1 \cdot (c_2)^c)$ such that for every graph class $G \in \text{SQGC}(c)$,

$$ \begin{array}{l} \forall G \in \mathcal{G} \quad \text{tw}(G) \le \lambda \cdot (\text{bcg}(G))^c \quad \Rightarrow \\ \forall F \in \mathcal{G}^{(c_1, c_2)} \quad \text{tw}(F) \le \lambda' \cdot (\text{bcg}(F))^c. \end{array} $$

Let $G \in \text{SQGC}(c)$ be a class of graph such that $\forall G \in \mathcal{G} \quad \text{tw}(G) \le \lambda \cdot (\text{bcg}(G))^c$. Let $H \in \mathcal{G}^{(c_1, c_2)}$ and let $G$ and $J$ be two graphs such that $G \in \mathcal{G}$, $G \le^{(c_1)} J$, and $H \le^{c_2} J$. $G$ and $J$ exist by definition of $\mathcal{G}^{(c_1, c_2)}$.
* By definition of $H$ and $J$, $\mathrm{tw}(H) \le \mathrm{tw}(J)$.

* By Lemma 19, $\mathrm{tw}(J) \le (c_1 + 1)(\mathrm{tw}(G) + 1) - 1$.

* By definition of $G$, $\mathrm{tw}(G) \le \lambda \cdot \mathbf{bcg}(G)^c$.

* By Lemma 31, $\mathbf{bcg}(G) \le (2c_2 + 1)(\mathbf{bcg}(H) + 2) + 1$.

If we combine these four statements, we obtain that

$$ \mathrm{tw}(H) \le (c_1 + 1)(\lambda \cdot [(2c_2 + 1)(\mathbf{bcg}(H) + 2) + 1]^c + 1) - 1. $$

As the formula is independent of the graph class, the Theorem 15 follows. □

# 5 Conclusions, extensions, and open problems

The main combinatorial result of this paper is that, for every $d$ and every apex-minor-free graph class $G$, the intersection class $\mathrm{inter}_d(G)$ has the SQGC property for $c = 1$. Certainly, the main general question is to detect even wider graph classes with the SQGM/SQGC property. In this direction, some insisting open issues are the following:

* Is the bound on the (multi-)degree necessary? Are there classes of intersection graphs with unbounded or “almost bounded” maximum degree that have the SQGM/SQGC property?

* All so far known results classify graph classes in SQGM(1) or SQGC(1). Are there (interesting) graph classes in SQGM(c) or SQGC(c) for some $1 < c < 2$ that do not belong in SQGM(1) or SQGC(1) respectively? An easy (but trivial) example of such a class is the class $Q_d$ of the q-dimensional grids, i.e., the cartesian products of $q \ge 2$ equal length paths. It is easy to see that the maximum $k$ for which an $n$-vertex graph $G \in Q_q$ contains a $(k \times k)$-grid as a minor is $k = \Theta(n^{\frac{1}{q}})$. On the other size, it can also be proven that $\mathrm{tw}(G) = \Theta(n^{\frac{q-1}{q}})$. These two facts together imply that $Q_q \in \mathrm{SQGM}(2 - \frac{2}{q})$ while $Q_q \notin \mathrm{SQGM}(2 - \frac{2}{q} - \epsilon)$ for every $\epsilon > 0$.

* Usually the graph classes in SQGC(1) are characterised by some “flatness” property. For instance, see the results in [31, 34, 34] for H-minor free graphs, where H is an apex graph. Can SQGC(1) be useful as an intuitive definition of the “flatness” concept? Does this have some geometric interpretation?

# References

[1] Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. *Journal of Algorithms*, 12:308–340, 1991. 1

[2] Julien Baste and Dimitrios M. Thilikos. Contraction-bidimensionality of geometric intersection graphs. In Daniel Lokshtanov and Naomi Nishimura, editors, *12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria*, volume 89 of LIPIcs, pages 5:1–5:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.IPEC.2017.5.1

[3] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. *Information and Computation*, 243:86–111, 2015. 3

[4] Julia Chuzhoy and Zihan Tan. Towards tight(er) bounds for the excluded grid theorem. *J. Comb. Theory, Ser. B*, 146:219–265, 2021. doi:10.1016/j.jctb.2020.09.010. 2
[5] Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. *Information and Computation*, 85(1):12–75, 1990. 1

[6] Bruno Courcelle. The expression of graph properties and graph transformations in monadic second-order logic. *Handbook of Graph Grammars*, pages 313–400, 1997. 1

[7] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In *Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011)*, pages 150–159, 2011. 3

[8] Erik D. Demaine. Algorithmic Graph Minors and Bidimensionality. In *Proceedings of the 36th International Conference on Graph-theoretic Concepts in Computer Science (WG 2010)*, pages 2–2, 2010. 2

[9] Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional parameters and local treewidth. *SIAM Journal on Discrete Mathematics*, 18(3):501–511, 2005. 2

[10] Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. *Journal of the ACM*, 52(6):866–893, 2005. 2, 3

[11] Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional structures: Algorithms, combinatorics and logic. *Dagstuhl Reports*, 3(3):51–74, 2013. 2

[12] Erik D. Demaine and MohammadTaghi Hajiaghayi. Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. In *Proceedings of the 12th International Symposium on Graph Drawing (GD 2004)*, volume 3383 of LNCS, pages 517–533, 2004. 2

[13] Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: New connections between FPT algorithms and PTASs. In *Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)*, pages 590–601, 2005. 2

[14] Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. *The Computer Journal*, 51(3):292–302, 2008. 2

[15] Erik D. Demaine and MohammadTaghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. *Combinatorica*, 28(1):19–36, 2008. 2, 4

[16] Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. The bidimensional theory of bounded-genus graphs. *SIAM Journal on Discrete Mathematics*, 20(2):357–371, 2006. 2

[17] Reinhard Diestel, Tommy R. Jensen, Konstantin Yu. Gorbunov, and Carsten Thomassen. Highly connected sets and the excluded grid theorem. *Journal of Combinatorial Theory. Series B*, 75(1):61–73, 1999. 2

[18] Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Fast subexponential algorithm for non-local problems on graphs of bounded genus. In *Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006)*, volume 4059 of LNCS, pages 172–183, 2006. 3

[19] Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Catalan structures and dynamic programming in H-minor-free graphs. In *Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008)*, pages 631–640, 2008. 3

[20] Fedor V. Fomin, Erik D. Demaine, and MohammadTaghi Hajiaghayi. Bidimensionality. In *Encyclopedia of Algorithms*. Springer, 2015. 2
[21] Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Contraction obstructions for treewidth. *Journal of Combinatorial Theory. Series B*, 101(5):302–314, 2011. 2, 4

[22] Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Bidimensionality and EPTAS. In *Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)*, pages 748–759, 2011. 2, 3

[23] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In *Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)*, pages 1563–1575, 2012. 2, 4, 5, 7

[24] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In *Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)*, pages 142–151, 2014. 3

[25] Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Excluded grid minors and efficient polynomial-time approximation schemes. *J. ACM*, 65(2):10:1–10:44, 2018. doi:10.1145/3154833. 3, 4, 7

[26] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In *Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, pages 503–510, 2010. 2, 3

[27] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. *CoRR*, abs/1606.05689, 2016. 3

[28] Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Approximation schemes via width/weight trade-offs on minor-free graphs. In Shuchi Chawla, editor, *Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020*, pages 2299–2318. SIAM, 2020. doi:10.1137/1.9781611975994.141. 3

[29] Fedor V. Fomin and Dimitrios M. Thilikos Petr Golovach and. Contraction bidimensionality: the accurate picture. In *17th Annual European Symposium on Algorithms*, volume 5757 of LNCS, pages 706–717. Springer, 2009. 2

[30] Fanica Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. *Journal of Combinatorial Theory, Series B*, 16(1):47–56, 1974. 1

[31] Archontia C. Giannopoulou and Dimitrios M. Thilikos. Optimizing the graph minors weak structure theorem. *SIAM Journal on Discrete Mathematics*, 27(3):1209–1227, 2013. 16

[32] Alexander Grigoriev, Athanassios Koutsonas, and Dimitrios M. Thilikos. Bidimensionality of Geometric Intersection Graphs. In *Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014)*, volume 8327 of LNCS, pages 293–305, 2014. 2, 4, 5, 6, 7

[33] Ken-ichi Kawarabayashi and Yusuke Kobayashi. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. In *Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)*, volume 14 of LIPIcs, pages 278–289, 2012. 2

[34] Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. New proof of the flat wall theorem. *Journal of Combinatorial Theory, Series B*, 2017. To appear. 16

[35] Alexander Leaf and Paul D. Seymour. Tree-width and planar minors. *Journal of Combinatorial Theory. Series B*, 111:38–53, 2015. 2

[36] Jiří Matoušek. String graphs and separators. In *Geometry, Structure and Randomness in Combinatorics*, pages 61–97. Springer, 2014. 5
[37] Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A log-ical approach. In *Proceedings of the 36th International Conference on Mathematical Foundations of Computer Science (MFCS 2011)*, pages 520–531, 2011. 3

[38] Neil Robertson and Paul D. Seymour. Graph Minors. II. Algorithmic aspects of tree-width. *Journal of Algorithms*, 7:309–322, 1986. 1

[39] Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. *Journal of Combinatorial Theory. Series B*, 41(1):92–114, 1986. 2

[40] Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a planar graph. *Journal of Combinatorial Theory. Series B*, 62(2):323–348, 1994. 2

[41] Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic programming for H-minor-free graphs. In *Proceedings of Computing and Combinatorics - 18th Annual International Conference, (COCOON 2012)*, pages 86–97, 2012. 3

[42] Juanjo Rué, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic programming for graphs on surfaces. *ACM Transactions on Algorithms*, 10(2):1–8, 2014. 3

[43] Dimitrios M. Thilikos. Graph minors and parameterized algorithm design. In *The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday*, pages 228–256, 2012. 2

[44] Dimitrios M. Thilikos. Bidimensionality and parameterized algorithms (invited talk). In *10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece*, pages 1–16, 2015. 2