theoremdummy theorem propositiondummy proposition corollarydummy corollary
lemmadummy lemma definitiondummy definition sublemmadummy sublemma claimdummy
claim remarkdummy remark factdummy fact conjecturedummy conjecture
questiondummy question observationdummy observation problemdummy problem
notedummy note

# Contraction Bidimensionality of Geometric
Intersection Graphs††thanks: Corresponding author: Dimitrios M. Thilikos,
Email<EMAIL_ADDRESS>. ,††thanks: 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).

Julien Baste Univ Lille, Centrale Lille, CRIStAL, Lille, France, Email:
<EMAIL_ADDRESS>. Dimitrios M. Thilikos∗, LIRMM, Univ Montpellier,
CNRS, Montpellier, France.

###### Abstract

Given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(G)$ as the minimum
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k$
for which
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
can be contracted to the uniformly triangulated grid
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$.
A graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ has the SQGC property if every graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in{\cal
G}$ has treewidth
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{O}({\bf
bcg}(G)^{c})$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
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  (Contractions).

Given a non-negative integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$,
two graphs
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
and a surjection
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma:V(G)\rightarrow
V(H)$ we write
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq_{\sigma}^{c}G$
if

  * •

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

  * •

for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x,y\in
V(H),$
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{x,y\\}\in
E(H)\iff G[\sigma^{-1}(x)\cup\sigma^{-1}(y)]$ is connected.

We say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$-diameter
contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
if there exists a surjection
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma:V(G)\rightarrow
V(H)$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq_{\sigma}^{c}G$
and we write this
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{c}G$.
Moreover, if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma$
is such that for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x\in
V(H)$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|\sigma^{-1}(x)|\leq
c^{\prime}$, then we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c^{\prime}$-size
contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
and we write
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{(c^{\prime})}G$.
Given two graphs
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
if there exists an integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$
such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{c}G$,
then we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
and we write
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq
G$. Moreover, if there exists a subgraph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq
G^{\prime}$, we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a _minor_ of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and we write this
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\preceq
G$. Given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
we denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
excl}(H)$ the class of graphs that exclude
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
as a minor.

###  1.1 Combinatorics of treewidth

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

######  Proposition .

There is a function
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f:\mathbb{N}\rightarrow\mathbb{N}$
such that every graph excluding a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(k\times
k)$-grid as a minor has treewidth at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f(k)$.

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

The potential of Subsection 1.1 on graph algorithms has been capitalized by
the theory of bidimensionality that was introduced in [10] and has been
further developed in [13, 14, 9, 22, 26, 32, 21, 16, 29, 23]. 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 [11, 15, 20, 8, 12]). 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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}$ mapping graphs to non-negative integers. We say that p is a minimization
graph parameter if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}(G)=\min\\{k\mid\exists S\subseteq V(G):|S|\leq k\mbox{ and }\phi(G,S)={\tt
true}\\},$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\phi$
is a some predicate on
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$.
Similarly, we say that p is a maximization graph parameter if in the above
definition we we replace
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\min$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\leq$
by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\max$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\geq$
respectivelly. Minimization or maximization parameters are briefly called
optimization parameters.

######  Definition  (Bidimensionality).

Given two real functions
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}g$,
we use the term
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f\gtrsim
g$ to denote that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f(x)\geq
g(x)-o(g(x))$. A graph parameter p is minor-closed (resp. contraction-closed)
when
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\preceq
G\Rightarrow{\bf p}(H)\leq{\bf p}(G)$ (resp.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq
G\Rightarrow{\bf p}(H)\leq{\bf p}(G)$). We can now give the two following
definitions:

p is minor-bidimensional if

  * •

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}$ is minor-closed, and

  * •

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}(\boxplus_{k})\gtrsim\delta\cdot k^{2}.$

p is contraction-bidimensional if

  * •

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}$ is contraction-closed, and

  * •

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}(\Gamma_{k})\gtrsim\delta\cdot k^{2}.$

for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\delta>0$.
In the above definitions, we use
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\boxplus_{k}$
for the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(k\times
k)$-grid and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$
for the uniformly triangulated
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(k\times
k)$-grid (see Figure 1). If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}$ is a minimization (resp. maximization) graph parameter, we denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Pi_{\bf
p}$ the problem that, given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and a non-negative integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k$,
asks whether
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}(G)\leq k$ (resp.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}(G)\geq k$). We say that a problem is minor/contraction-bidimensional if it
is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Pi_{\bf
p}$ for some bidimensional optimization parameter
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}$.

Figure 1: The graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{9}$.

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,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$-Scattered
Set, Induced Path Packing,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r$-Center,
connected
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r$-Center,
Connected Diamond Hitting Set, Unweighted TSP Tour (see [14, 20, 44]).

#### 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  (SQGC and SQGC).

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ be a graph class. We say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ has the subquadratic grid minor property (SQGM property for short) if
there exist a constant
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$ such that every graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in{\cal
G}$ which excludes
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\boxplus_{t}$
as a minor, for some integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}t$,
has treewidth
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{O}(t^{c})$.
In other words, this property holds for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ if Subsection 1.1 can be proven for a sub-quadratic
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f$
on the graphs of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$.

Similarly, we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ has the subquadratic grid contraction property (SQGC property for short)
if there exist a constant
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$ such that every graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in{\cal
G}$ which excludes
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{t}$
as a contraction, for some integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}t$,
has treewidth
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{O}(t^{c})$.
For brevity we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGM}(c)$ (resp.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGC}(c)$) if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ has the SQGM (resp SQGC) property for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$.
Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(c)\subseteq\mbox{\rm SQGM}(c)$ for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$.

###  1.2 Algorithmic implications

The meta-algorithmic consequences of bidimensionality theory are summarised as
follows. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGM}(c)$, for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$, and let p be a minor-bidimensional-optimization parameter.

  * [A]

As it was observed in [10], the problem
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Pi_{\bf
p}$ can be solved in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}2^{o({k})}\cdot
n^{\mathcal{O}(1)}$ steps on
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$, given that the computation of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
p}$ can be done in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}2^{\mathcal{O}({\bf
tw}(G))}\cdot n^{\mathcal{O}(1)}$ steps (here
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
tw}(G)$ is the treewidth of the input graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}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 propety [42, 19, 18, 18, 41] or to general graphs
[7, 3, 24].

  * [B]

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

  * [C]

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

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.

All above results have their counterparts for contraction-bidimensional
problems with the difference that one should instead demand that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm 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 triangles indicate the applicability of minor-
bidimensionality and the red triangle indicate the applicability of
contraction-bidimensionality. The aforementioned
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Omega(k^{2}\cdot\log
k)$ lower bound to the function
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f$
of Subsection 1.1, indicates that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGM}(c)$ does not contain all graphs (given that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c<2$).

As an example we mention the well known
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$-Domination
Set problem (for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d\geq
1$), asking whether a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
has a set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
of at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k$
vertices such that every vertex in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
is within distance at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$
from some vertex of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$-Domination
Set is contraction bidimensional problem that satisfies the additional meta-
algorithmic conditions in [A], [B], and [C]. This implies that it can be
solved in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGM}(c)$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(c)$. Concerning the SQGM property, the following result was proven in
[15].

######  Proposition .

For every graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
excl}(H)\in\mbox{\rm SQGM}(1)$.

A graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is an apex graph if it contains a vertex whose removal from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
results to a planar graph. For the SQGC property, the following counterpart of
Subsection 1.2 was proven in [21].

######  Proposition .

For every apex graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
excl}(H)\in\mbox{\rm SQGC}(1)$.

Notice that both above results concern graph classes that are defined by
excluding some graph as a minor. For such graphs, Subsection 1.2 is indeed
optimal. To see this, consider
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}K_{h}$-minor
free graphs where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}h\geq
6$ (these graphs are not apex graphs). Such classes do not satisfy the SQGC
property: take
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$,
add a new vertex, and make it adjacent, with all its vertices. The resulting
graph excludes
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$
as a contraction and has treewidth
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}>k$.

###  1.3 String graphs

An important step extending the applicability of bidimensionality theory
further than
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$-minor
free graphs, was done in [23] (see also [25]).

######  Definition  (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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
U}_{d}$ the set of unit disk graphs (resp. of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
M}_{d}$ map graphs) of maximum degree
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$.

The following was proved in [23, 25].

######  Proposition .

For every positive integer
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
U}_{d}\in\mbox{\rm SQGM}(1)$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
M}_{d}\in\mbox{\rm SQGM}(1)$.

Subsection 1.3 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 .

(String graphs) Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
L}=\\{L_{1},\ldots,L_{k}\\}$ be a collection of lines in the plane. We say
that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
L}$ is normal if there is no point belonging to more than two lines. The
intersection graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}$ of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
L}$, is the graph whose vertex set is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
L}$ and where, for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i,j$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
i<j\leq k$, the edge
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{L_{i},L_{j}\\}$
has multiplicity
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|L_{1}\cap
L_{2}|$. We denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}$ the set containing every graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{G}_{\cal
L}$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
L}$ is a normal collection of lines in the plane and where each vertex of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}$ has edge-degree at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$.
i.e., is incident to at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$
edges. We call
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}$ string graphs with edge-degree bounded by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$.

It is easy to observe that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
U}_{d}\cup{\cal M}_{d}\subseteq{\cal S}_{f(d)}$ for some quadratic function
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}f$.
Indeed, given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}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],
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}$ includes a much wider variety of classes of intersection graphs [32].
As an example, consider
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}_{d,\alpha}$ as the class of all graphs that are intersection graphs of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha$-convex
bodies111We call a set of points in the plane a body if it is homeomorphic to
the closed disk
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{(x,y)\mid
x^{2}+y^{2}\leq 1\\}$. A 2-dimensional body
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}B$
is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha$-convex
if every two of its points can be the extremes of a line
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}L$
consisting of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha$
straight lines and where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}L\subseteq
B$. Convex bodies are exactly the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1$-convex
bodies. in the plane and have edge-degree at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$.
In [32], it was proven that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}_{d,\alpha}\subseteq{\cal S}_{c}$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$
depends (polynomially) on
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha$.
Another interesting class from [32] is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
F}_{H,\alpha}$ containing all
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$-subgraph
free intersection graphs of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha$-fat222A
collection of convex bodies in the pane is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}a$.
families of convex bodies. Notice
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
U}_{d}$ can be seen as a special case of both
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}_{d,\alpha}$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
F}_{H,\alpha}$. (See [36] for other examples of classes included in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}$.)

Figure 3: A graphical representation of the definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}$.

###  1.4 Our contribution

#### Graph class extensions.

######  Definition
($\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(c_{1},c_{2})$-extension).

Given a class of graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}$
and two integers
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{2}$,
we define the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(c_{1},c_{2})$-extension
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$, denoted by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}$,
as the set containing every graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
such that there exist a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in\mathcal{G}$
and a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
that satisfy
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\leq^{(c_{1})}J\mbox{
and }H\leq^{c_{2}}J$ (see Figure 3 for a visualization of this construction).
Keep in mind that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{2},c_{1})}$
are two different graph classes. We also denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
P}$ the class of all planar graphs.

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

######  Proposition .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{1}\geq
1$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{2}\geq
0$ be two integers. If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}\in\mbox{\rm
SQGM}(c)$.

######  Proposition .

For every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d\in\mathbb{N}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}\subseteq{\cal P}^{(1,d)}$.

We visualise the idea of the proof of Subsection 1.4 by some example, depicted
in Figure 4. In Section 3 we use the same idea for a more general result.
Figure 4 motivates the definition of the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(c_{1},c_{2})$-extension
of a graph class. Intuitively, the fact that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\in{\cal
G}^{(c_{1},c_{2})}$ expresses the fact that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
can be seen as a “bounded” distortion of a graph in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ (after a fixed number of “de-contractions” and contractions).

Figure 4: An example of the proof of Subsection 1.4. In the leftmost figure we
we a collection of lines in the plane
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
L}=\\{L_{1},\ldots,L_{k}\\}$ whose intersection graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}$ is depicted in the rightmost figure and has maximum edge degree 9 because
of line
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$
that meets other lines in 9 points, therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}\in{\cal S}_{9}$. To see why
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}\in{\cal P}^{(1,9)}$, one may see the leftmost figure are a planar graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P\in{\cal
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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
in the middle, i.e.,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P\leq^{(1)}J$.
Finally, the intersection graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}$ can be seen as a result of the contraction in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
of each one of the paths, on at most 9 vertices, to a single vertex. Therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}\leq^{9}J$, hence
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal
L}$ belongs in the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(1,9)$-extension
of planar graphs.

Subsection 1.2, combined with Subsection 1.4, provided the wider, so far,
framework on the applicability of minor-bidimensionality:
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGM}(1)$ contains
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
excl}(H)^{(c_{1},c_{2})}$ for every apex graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
and positive integers
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{1},c_{2}$.
As, by Subsection 1.2,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
P}\in\mbox{\rm SQGC}(1)$, Subsection 1.4 and Subsection 1.4 directly
classifies in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGM}(1)$ the graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}$, and therefore a large family of bounded degree intersection graphs
(including
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
U}_{d}$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
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  (Intersection graphs).

Given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and a set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S\subseteq
V(G)$ we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
is a connected set of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[S]$
is a connected graph. We also define by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}(G)$ the set of all connected subsets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$.
Given a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}\subseteq{\cal C}(G)$, we define the intersection graph of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}$ in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
denoted by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}I_{G}({\cal
C})$, as the graph whose vertex set is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}$, where two vertices
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C_{2}$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}I_{G}({\cal
C})$ are connected by an edge if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C_{1}\cap
C_{2}\neq\emptyset$, and, moreover, the multiplicity of the edge
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{C_{1},C_{2}\\}$
is equal to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V(C_{1}\cap
C_{2})|$. Given a graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ we define the following class of graphs

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}({\cal G})=\bigcup_{G\in{\cal G}}\\{I_{G}({\cal C})\mid{\cal
C}\subseteq{\cal C}(G)\\}.$

In other words,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}({\cal G})$ contains all the intersection graphs of the connected vertex
subsets of each of the graphs in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$. Given a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d\in\mathbb{N}$,
we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal G})$ as the set of graphs in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}({\cal G})$ that have edge-degree at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$.

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

######  Lemma .

For every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d\in\mathbb{N}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}\subseteq{\sf inter}_{d}({\cal P})\subseteq{\cal S}_{d^{\prime}}$, for
some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d^{\prime}=O(d^{2})$.

###### Proof (sketch)..

We deal with the less trivial statement that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal P})\subseteq{\cal S}_{O(d^{2})}$. For this, let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\in{\sf
inter}_{d}({\cal P})$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H=I_{G}({\cal
C})$ for some collection
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}$ of connected subsets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$,
for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in{\cal
P}$. We choose the planar graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
so that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V(G)|+|E(G)|$
is minimized. This means that for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\in{\cal
C}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[C]$
is a tree on at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}2d$
vertices. If we now replace each tree
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[C]$
by a string “surrounding” it is easy to observe that two such string cannot
have more than
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}O(d^{2})$
points in common. ∎

Observe that Subsection 1.4 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 in [32] covered, for the case of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
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 Subsection 1.4. The main result of this paper is the following.

######  Theorem .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c_{2}$
be two positive integers. If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}\in\mbox{\rm
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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ is also a graph in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$. A powerful consequence of Subsection 1.4 is the following (the proof is
postponed in Section 3).

######  Theorem .

If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ is a monotone graph class, where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$, and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d\in\mathbb{N}$,
then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal G})\in\mbox{\rm SQGC}(c)$.

Figure 5: The hierarchy of graph classes where Subsection 1.4 applies.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
U}_{d}$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
M}_{d}$ are the bounded-degree unit-disk and map graphs respectively (where
the results of [23, 25] apply).
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}$ are the bounded-degree string graphs, while
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\sf excl}(H))$ are the bounded-degree intersection graphs of
connected sets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$-minor
free graphs, where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is an apex graph.

Combining Subsection 1.2 and Subsection 1.4 we obtain that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(1)$ contains
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\sf excl}(H))$ for every apex graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}_{d}\in\mbox{\rm SQGC}(1)$. Therefore, on
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
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 Subsection 1.4 in Section 3
while Section 4 is dedicated to the proof of Subsection 1.4. We should stress
that this proof is quite different than the one of Subsection 1.4 in [32].
Finally, Section 5 contains some discussion and open problems.

##  2 Definitions and preliminaries

We denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathbb{N}$
the set of all non-negative integers. Given
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}r,q\in\mathbb{N},$
we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}[r,q]=\\{r,\ldots,q\\}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}[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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
we denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$
its vertex set and by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}E(G)$
its edge set. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x$
be a vertex or an edge of a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and likewise for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}y$;
their distance in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
denoted by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
dist}_{G}(x,y)$, is the smallest number of vertices of a path in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
that contains them both. Moreover if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
is a graph and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x\in
V(G)$, we denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{G}^{c}(x)$,
for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c\in\mathbb{N}$,
the set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{y\mid
y\in V(G),\ {\bf dist}_{G}(x,y)\leq c+1\\}$. For any set of vertices
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S\subseteq
V(G)$, we denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[S]$
the subgraph of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
induced by the vertices from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$.
If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[S]$
is connected, then we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
is a _connected vertex set_ of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
We define the _diameter_ of a connected subset
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
as the maximum pairwise distance between any two vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$.
The edge-degree of a vertex
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}v\in
V(G)$ is the number of edges that are incident to it (multi-edges contribute
with their multiplicity to this number).

Figure 6: The graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{9}$.

######  Definition  (Grids).

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

######  Definition  (Treewidth).

A tree-decomposition of a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
is a pair
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(T,{\cal
X})$, where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T$
is a tree and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}=\\{X_{t}:\ t\in V(T)\\}$ is a family of subsets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$,
called bags, such that the following three properties are satisfied:

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bullet$
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bigcup_{t\in
V(T)}X_{t}=V(G)$,

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bullet$
for every edge
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e\in
E(G)$ there exists
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}t\in
V(T)$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e\subseteq
X_{t}$, and

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bullet$
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\forall
v\in V(G)$, the set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T_{v}=\\{t\in
V(T)\mid v\in X_{t}\\}$ is a connected vertex set of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T$.

The width of a tree-decomposition is the cardinality of the maximum size bag
minus 1 and the treewidth of a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
is the minimum width over all the tree-decompositions of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
We denote the treewidth of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(G)$.

######  Lemma .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
be a graph and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
be a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$-size
contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
Then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(G)\leq(c+1)\cdot({\sf tw}(H)+1)-1$.

###### Proof.

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

Consider now a tree decomposition
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(T,{\cal
X})$ of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$.
We claim that the pair
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(T,{\cal
X^{\prime}})$, where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X^{\prime}_{t}:=\bigcup_{x\in
X_{t}}V_{x}$ for
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}t\in
T$ is a tree decomposition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
Clearly all vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
are included in some bag, since all vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
did. Every edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e$
is an edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
with endpoints in different parts of the partition, say
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{x}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{y}$,
then this implies that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{x,y\\}\in
E(H)$. Thus, there is a node
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}t$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T$
for which
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x,y\in
X_{t}$ and therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e\subseteq
X_{t}^{\prime}$. Moreover, the continuity property remains unaffected, since
for any vertex
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x\in
V(H)$ each vertex in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{x}$
induces the same subtree in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T$
that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x$
did. ∎

In Table 1 we present all the notation that we use in this paper.

Symbol | Combinatorial object | Definition
---|---|---
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\boxplus_{k}$ |  $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(k\times k)$-grid | 2
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$ | uniformly triangulated grid | 2
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k}$ | extended uniformly triangulated grid | 2
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}I_{G}({\cal C})$ |  the intersection graph of a set $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal C}$ of connected subsets of the vertices of a graph $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$ | 1.4
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G_{\cal L}$ |  the intersection graph of a collection $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal L}=\\{L_{1},\ldots,L_{k}\\}$ of lines in the plane | 1.4
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal P}$ | planar graphs | 1.4
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal S}_{d}$ |  $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$-bounded degree string graphs | 1.3
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal M}_{d}$ |  $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$-bounded degree map graphs | 1.3
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal U}_{d}$ |  $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d$-bounded degree unit disk graphs | 1.3
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf excl}(H)$ |  the class of graphs excluding the graph $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$ as a minor | 1
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf diss}({\cal G})$ |  the graph class that is the dissolution closure of the graph class $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal G}$ | 3
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mathcal{G}^{(c_{1},c_{2})}$ |  the graph class that is the $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(c_{1},c_{2})$-extension of a graph class $\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal G}$ | 1.4
Table 1: Graphs, graph classes, and functions of the paper.

##  3 Proof of Subsection 1.4

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

######  Lemma .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q$
be a graph where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\delta(Q)\geq
3$ and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H,G$
be graphs where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a dissolution of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q\leq
G$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q\leq
H$.

###### Proof.

As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q\leq
G$ then there exist
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma:V(G)\to
V(Q)$ such that for all
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x\in
V(Q)$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[\sigma^{-1}(x)]$
is a non-empty graph and for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}x,y\in
V(Q),$
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{x,y\\}\in
E(Q)\iff G[\sigma^{-1}(x)\cup\sigma^{-1}(y)]$ is connected.

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

######  Definition  (The function bcg).

Given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(G)$ as the maximum
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k$
for which
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
can be contracted to the uniformly triangulated grid
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$.

Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}$ is a contraction-closed parameter, i.e., if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq
G$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(H)\leq{\bf bcg}(G)$.

######  Lemma .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
be two graphs. If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a dissolution of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(H)={\bf bcg}(G)$.

###### Proof.

The fact that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(H)\leq{\bf bcg}(G)$ follows from the fact that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is also a contraction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and taking into account the contraction-closedness of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}$. The fact that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(G)\leq{\bf bcg}(H)$ follows by taking into account that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\delta(\Gamma_{k})\geq
3$ and applying inductively Section 3 to the vertices of degee 2 in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
that need to be dissolved in order to transform
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$.
∎

######  Definition .

Given a graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$, we define the dissolution closure of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ as the graph class
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
diss}({\cal G})$ containing all the dissolutions of the graphs in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$.

We observe the following.

######  Lemma .

If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
diss}({\cal G})\in\mbox{\rm SQGC}(c)$.

###### Proof.

Suppose that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\in\mbox{\rm SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$, wich implies that

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\displaystyle\forall
G\in\mathcal{G}\ {\sf tw}(G)\leq\lambda\cdot({\bf bcg}(G))^{c}.$ (1)

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\in{\sf
diss}({\cal G})$ and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\in{\cal
G}$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a dissolution of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
By Section 3,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\bf
bcg}(H)={\bf bcg}(G)$ and from (1),
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(G)\leq\lambda({\bf bcg}(H))^{c}$. As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a minor of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
we have that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
tw}(H)\leq\lambda({\bf bcg}(H))^{c}$ and the lemma follows. ∎

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

######  Lemma .

If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ is a graph class that is topological minor closed, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal G})\subseteq{\cal G}^{(d+1,d-1)}$.

###### Proof.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
be a graph on
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}h$
vertices in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal G}),$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d\in\mathbb{N}$.
This means that there is a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ such that we can see the vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
as a set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}=\\{C_{1},\ldots,C_{h}\\}$ of connected subsets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and each multi-edge
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e=\\{C_{i},C_{j}\\}$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
corresponds to two mutually intersecting subsets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
C}$ and the multiplicity of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e$
is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|C_{i}\cap
C_{j}|$. For every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{i,j\\}\in{h\choose
2}$, we set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i,j}=C_{i}\cap
C_{j}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}m_{i,j}=|C_{i}\cap
C_{j}|$, and we assume that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e_{i,j}=\\{C_{i},C_{j}\\}$
is a multi-edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
of multiplicity
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}m_{i,j}$
(if this edge does not exists in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
then the multiplicity of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}e_{i,j}$
is 0).

We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i}=\bigcup_{j\in[h]}V_{i,j}$,
for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in[h]$
and also set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{V}=\bigcup_{i\in[h]}V_{i}$.
Notice that, for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in[h]$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V_{i}|$
is upper bounded by the edge-degree, in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
of the vertex
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C_{i}$,
therefore,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V_{i}|\leq
d$ for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in[h]$.
Also, a vertex in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{V}$
cannot belong in more that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d+1$
distinct
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C_{i}$’s
as, otherwise
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
would contain a clique with at least
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}d+2$
vertices. As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\in{\sf
inter}_{d}({\cal G})$, this is not possible.

Recall that, for each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in[h]$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i}$
is a subset of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C_{i}$
and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T_{i}$
be a minimum-size tree of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[C_{i}]$
containing the vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i}$.
We partition the set of vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T_{i}$
into three sets
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i},\overline{V}_{i},D_{i}$
where among the vertices in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(T_{i})\setminus
V_{i}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}D_{i}$
are the vertices of degree 2 and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\overline{V}_{i}$
are the rest. By minimality, the leaves of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T_{i}$
belong in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i}$.
Moreover, there is no vertex in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\overline{V}_{i}$
that belongs to some other
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\overline{V}_{i\textquoteright}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in[h]\setminus\\{i\\}$.
We denote by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{T}_{i}$
the tree obtained from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T_{i}$
if we dissolve in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}T_{i}$
all vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}D_{i}$.
That way we can still partition the vertices of each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{T}_{i}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in[h]$,
into
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V_{i}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\overline{V}_{i}$.
Also, it is easy to see that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{T}_{i}$
has diameter at most
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V_{i}|-1\leq
d-1$.

We define the graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G\textquoteright:=\bigcup_{i\in[h]}\hat{T}_{i}$.
Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
is obtained from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bigcup_{i\in[h]}T_{i}$
(that is a subgraph of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$)
after we dissolve all vertices in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bigcup_{i\in[h]}D_{i}$.
Therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
is a topological minor of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
thus
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}\in{\cal
G}$. We consider the collection
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
T}=\\{\hat{T}_{1},\ldots,\hat{T}_{h}\\}$ of connected subgraphs of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$.

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

Observe now that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}\leq^{(d+1)}J$,
as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}$
is obtained after contracting in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
the aforementioned pairwise disjoint cliques. Moreover,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{d-1}J$
as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is obtained after we contract in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}J$
each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{T}_{i}$
(of diameter
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\leq
d-1$) to a single vertex. As
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G^{\prime}\in{\cal
G}$, we conclude that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\in{\cal
G}^{(d+1,d-1)}$ as required. ∎

We are now ready to prove Subsection 1.4.

###### Proof of Subsection 1.4.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$ be a monotone graph class in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\mbox{\rm
SQGC}(c)$ for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}1\leq
c<2$ and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
D}={\sf diss}({\cal G})$. From Section 3,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
D}\in\mbox{\rm SQGC}(c)$ and by the monotonicity of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}$, we have that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
diss}({\cal G})$ is closed under taking of topological minors. Therefore, from
Section 3,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal D})\subseteq{\cal D}^{(d+1,d-1)}$ and from Subsection 1.4,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal D})\in\mbox{\rm SQGC}(c)$. The result follows because
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
G}\subseteq{\cal D}$, as this implies that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
inter}_{d}({\cal G})\subseteq{\sf inter}_{d}({\cal D})$. ∎

##  4 Proof of Subsection 1.4

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
be graphs and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$
be a non-negative integer. If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq_{\sigma}^{c}G$,
then we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma$-contraction
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
and denote this by
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq_{\sigma}G$.

Before we proceed the the proof of Subsection 1.4 we make first the following
three observations. (In all statements, we assume that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
are two graphs and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma:V(G)\to
V(H)$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma$-contraction
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.)

######  Observation .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
be a connected subset of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(H)$.
Then the set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\bigcup_{x\in
S}\sigma^{-1}(x)$ is connected in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.

######  Observation .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}\subseteq
S_{2}\subseteq V(H)$. Then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma^{-1}(S_{1})\subseteq\sigma^{-1}(S_{2})\subseteq
V(G)$.

######  Observation .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
be a connected subset of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$.
Then the diameter of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma(S)$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is at most the diameter of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.

Given a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1},S_{2}\subseteq
V(G)$ we say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{2}$
_touch_ if either
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}\cap
S_{2}\neq\emptyset$ or there is an edge of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
with one endpoint in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}$
and the other in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{2}$.

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

###  4.1
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configurations.

######  Definition .

($\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configurations) Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
be a graph. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda=({\cal
W},{\cal E})$ be a graph whose vertex set is a connected packing of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
i.e., its vertices are connected subsets of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$.
A
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of a graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
is a quadruple
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}=({\cal X},\alpha,{\cal R},\beta)$ where

  1. 1.

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}$ is a connected packing of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,

  2. 2.

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha$
is a bijection from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
W}$ to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}$ such that for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\subseteq\alpha(W)$,

  3. 3.

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}$ is a collection of internally disjoint paths of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
and

  4. 4.

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta$
is a bijection from
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
E}$ to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}$ such that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{W_{1},W_{2}\\}\in{\cal
E}$ then the endpoints of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta(\\{W_{1},W_{2}\\})$
are in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{1}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{2}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(\beta(\\{W_{1},W_{2}\\}))\subseteq\alpha(W_{1})\cup\alpha(W_{2})$.

######  Definition .

(States, freeways, clouds, and coverage) A
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}=({\cal X},\alpha,{\cal R},\beta)$ of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
is complete if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}$ is a partition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$.
We refer to the elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}$ as the states of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ and to the elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}$ as the freeways of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$. We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
indep}({\cal S})=V(G)\setminus\bigcup_{X\in\cal X}X.$ Note that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\cal
S$ is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\cal
S$ is complete if and only if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
indep}({\cal S})=\emptyset$.

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

  * (A)

If a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-cloud
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C$
intersects some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W\in{\cal
W}$, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}C\subseteq\alpha(W)$.

  * (B)

If a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-cloud over
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ intersects the vertex set of at least two freeways of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$, then it shadows at most one state of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$.

We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cost}_{\cal A}({\cal S})=\sum_{C\in{\sf front}_{\cal A}({\cal S})}{\sf
cov}_{\cal S}(C).$ Given
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}\subseteq
S_{2}\subseteq V(G)$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}$
is connected, we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\sf
cc}_{G}(S_{2},S_{1})$ as the (unique) connected component of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[S_{2}]$
that contains
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S_{1}$.

###  4.2 Triangulated grids inside triangulated grids

The next lemma is the main combinatorial engine of our results. We assume that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{c}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}\leq
G$. Here
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
should be seen as the result of a “shrink” of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
in the sense that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
can be contracted to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
so that each vertex of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
is created after a bounded number of contractions. The lemma states that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
can be contracted to a uniformly triangulated grid, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$,
as a “shrunk version” of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$,
can also be contracted to a uniformly triangulated grid that is no less than
linearly smaller.

The proof strategy views the graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
as being contracted into a uniformly triangulated grid
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\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
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
that, when contracted, give rise to a uniformly triangulated grid
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k^{\prime}}$,
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k^{\prime}=\Omega(k)$.

######  Lemma .

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H$
be graphs and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c,k$
be non-negative integers such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{c}G$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}\leq
G$. Then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k^{\prime}}\leq
H$ where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k^{\prime}=\lfloor\frac{k-1}{2c+1}\rfloor-1$.

###### Proof.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k^{*}=1+(2c+1)\cdot(k^{\prime}+1)$
and observe that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}k^{*}\leq
k$, therefore
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k^{*}}\leq\Gamma_{k}\leq
G$. For simplicity we use
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma=\Gamma_{k^{*}}$.
Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\phi:V(G)\rightarrow
V(H)$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}H\leq^{c}_{\phi}G$
and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma:V(G)\rightarrow
V(\Gamma)$ such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma\leq_{\sigma}G$.
We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}=\\{\phi^{-1}(a)\mid a\in V(H)\\}$. Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$ is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$-diameter
partition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.

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

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q,p$
be two different elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q$.
We say that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
are linked if they both belong in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
in}$ and their distance in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$
is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}2c+1$
or one of them is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}b_{\rm
out}$ and the other is
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}b_{i,j}$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in\\{1,k^{\prime}\\}$
or
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}j\in\\{1,k^{\prime}\\}$.

Figure 7: A visualization of the proof of Subsection 4.2. In this whole graph
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma_{k}$,
we initialize our reaserch of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$
such that every internal red hexagon will become a vertex of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$
and correspond to a state and the border, also circle by a red line will
become the vertex
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}b_{\rm
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.

For each
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q_{\rm in}$, we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}=\sigma^{-1}(q)$.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}$
is connected by the definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\sigma$.
In case
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q=b_{\rm
out}$ we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}=\bigcup_{q^{\prime}\in
Q_{\rm out}}\sigma^{-1}(q^{\prime})$. Note that as
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
out}$ is a connected set of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Gamma$,
then, by Observation 4,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{b_{\rm
out}}$ is connected in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
We also define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
W}=\\{W_{q}\mid q\in Q\\}$. Given some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q$ we call
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}$
the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$-capital
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
and a subset
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}S$
of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$
is a capital of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$
if it is the
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$-capital
for some
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q$. Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
W}$ is a connected packing of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(G)$.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q$. If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q_{\rm in}$ then we set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{q}=N^{c}_{{\Gamma}}(q)$.
If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q=b_{\rm
out}$, then we set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{q}=\bigcup_{q^{\prime}\in
Q_{\rm out}}N^{c}_{{\Gamma}}(q^{\prime})$. Note that for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}N_{q}\subseteq
V(\Gamma)$. For every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q$, we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{q}=\sigma^{-1}(N_{q})$.
Note that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{q}\subseteq
V(G)$. We also set
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
X}=\\{X_{q}\mid q\in Q\\}$. Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
we two linked elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q$.
If both
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
belong to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
in}$, and therefore are vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$,
then we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
as the unique shortest path between them in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$.
If
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p=b_{\rm
out}$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q_{\rm in}$, then we know that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q=b_{i,j}$
where
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i\in\\{1,k^{\prime}\\}$
or
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}j\in\\{1,k^{\prime}\\}$.
In this case we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
as any shortest path in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$
between
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}b_{i,j}$
and the vertices in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
out}$. In both cases, we define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p,q}$
by picking some path between
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{p}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}$
in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G[\sigma^{-1}(V(Z_{p,q}))]$
such that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V(P_{p,q})\cap
W_{q}|=1$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}|V(P_{p,q})\cap
W_{p}|=1$.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
E}=\\{\\{W_{p},W_{q}\\}\mid\mbox{\leavevmode\nobreak\
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
are linked}\\}$ and let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda=({\cal
W},{\cal E})$. Notice that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$
is isomorphic to
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$
and consider the isomorphism that correspond each vertex
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q=b_{i,j}$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}i,j\in\left\llbracket
1,k^{\prime}\right\rrbracket^{2}$ to the vertex with coordinates
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}(i,j)$.
Moreover
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}b_{\rm
out}$ corresponds to the apex vertex of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\hat{\Gamma}_{k^{\prime}}$.

Let
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha:{\cal
W}\rightarrow{\cal X}$ such that for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q\in
Q$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\alpha(W_{q})=X_{q}$.
Let also
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
R}=\\{P_{p,q}\mid p,q\in Q,\mbox{\leavevmode\nobreak\
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
are linked}\\}$. We define
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta:{\cal
E}\rightarrow{\cal R}$ such that if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
are linked, then
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta(W_{q},W_{p})=P_{p,q}$.
We use notation
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}=({\cal X},\alpha,{\cal R},\beta)$.

######  Claim .

$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
S}$ is an
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\cal
A}$-normal
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.

###### Proof of Claim 4.2..

We first see that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\cal
S$ is a
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\Lambda$-state
configuration of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}G$.
Condition 1 follows by the definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{q}$
and Observation 4. Condition 2 follows directly by the definitions of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}X_{q}$.
For Condition 3, we first observe that, by the construction of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$
and the definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$,
for any two pairs
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p,q$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p^{\prime},q^{\prime}$
of pairwise linked elements of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q$,
the paths
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p^{\prime},q^{\prime}}$
are internally vertex disjoined paths of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}{\Gamma}$.
It implies that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p,q}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p^{\prime},q^{\prime}}$
can intersect each other only on the vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{p}\cup
W_{q}\cup W_{p^{\prime}}\cup W_{q^{\prime}}$. But
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p,q}$
(resp.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p^{\prime},q^{\prime}}$),
by construction contains only two vertices of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{p}\cup
W_{q}\cup W_{p^{\prime}}\cup W_{q^{\prime}}$ that are the extremities of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p,q}$,
(resp.
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p^{\prime},q^{\prime}}$).
So
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p,q}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}P_{p^{\prime},q^{\prime}}$
are internally vertex disjoined, as required. For Condition 4, assume that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\\{W_{p},W_{q}\\}\in{\cal
E}$. The fact that the endpoints of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta(\\{W_{p},W_{q}\\})$
are in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{p}$
and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}W_{q}$
follows directly by the definition of
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}\beta(\\{W_{p},W_{q}\\})=P_{p,q}$.
It remains to prove that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(\beta(\\{W_{p},W_{q}\\}))\subseteq\alpha(W_{p})\cup\alpha(W_{q})$
or equivalently, that
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}V(P_{p,q})\subseteq
X_{p}\cup X_{q}$. Observe that, if both
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p,q\in
Q_{\rm in}$, then every vertex in the shortest path
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
should be within distance
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$
from either
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
or
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q$.
Similarly, if
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p\in
Q_{\rm in}$ and
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}q=b_{\rm
out}$, then every vertex in the shortest path
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}$
should be within distance
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}c$
from either
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p$
or some vertex in
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Q_{\rm
out}$. So for every
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p,q\in
Q$, with
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}p\not=q$,
$\color[rgb]{0.1,0.1,0.41}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,0.41}Z_{p,q}\subseteq
N_{p}\cup N_{q}$. By Observation 4, every vertex in