# On Comparable Box Dimension

Zdenek Dvorák Supported by the ERC-CZ project LL2005 (Algorithms and
complexity within and beyond bounded expansion) of the Ministry of Education
of Czech Republic<EMAIL_ADDRESS>Charles University, Prague, Czech
Republic  Daniel Goncalves Supported by the ANR grant GATO ANR-16-CE40-0009.
<EMAIL_ADDRESS>LIRMM, Université de Montpellier, CNRS, Montpellier, France
Abhiruk Lahiri Supported by the ERC-CZ project LL2005 (Algorithms and
complexity within and beyond bounded expansion) of the Ministry of Education
of Czech Republic<EMAIL_ADDRESS>Charles University, Prague, Czech
Republic  Jane Tan<EMAIL_ADDRESS>Mathematical Institute, University
of Oxford, Oxford OX2 6GG, United Kingdom  Torsten Ueckerdt
<EMAIL_ADDRESS>Karlsruhe Institute of Technology, Karlsruhe, Germany

###### Abstract

Two boxes in $\mathbb{R}^{d}$ are _comparable_ if one of them is a subset of a
translation of the other one. The _comparable box dimension_ of a graph $G$ is
the minimum integer $d$ such that $G$ can be represented as a touching graph
of comparable axis-aligned boxes in $\mathbb{R}^{d}$. We show that proper
minor-closed classes have bounded comparable box dimension and explore further
properties of this notion.

##  1 Introduction

Given a system ${\cal O}$ of subsets of $\mathbb{R}^{d}$, we say that a graph
$G$ is a _touching graph of objects from ${\cal O}$_ if there exists a
function $f:V(G)\to{\cal O}$ (called a _touching representation by objects
from ${\cal O}$_) such that the interiors of $f(u)$ and $f(v)$ are disjoint
for all distinct $u,v\in V(G)$, and $f(u)\cap f(v)\neq\emptyset$ if and only
if $uv\in E(G)$. Famously, Koebe [13] proved that a graph is planar if and
only if it is a touching graph of balls in $\mathbb{R}^{2}$. This result has
motivated numerous strengthenings and variations (see [14, 19] for some
classical examples); most relevantly for us, Felsner and Francis [11] showed
that every planar graph is a touching graph of cubes in $\mathbb{R}^{3}$.

An attractive feature of touching representations is that it is possible to
represent graph classes that are sparse (e.g., planar graphs, or more
generally, graph classes with bounded expansion [15]). This is in contrast to
general intersection representations where the represented class always
includes arbitrarily large cliques. Of course, whether the class of touching
graphs of objects from ${\cal O}$ is sparse or not depends on the system
${\cal O}$. For example, all complete bipartite graphs $K_{n,m}$ are touching
graphs of boxes in $\mathbb{R}^{3}$, where the vertices in one part are
represented by $m\times 1\times 1$ boxes and the vertices of the other part
are represented by $1\times n\times 1$ boxes (throughout the paper, by a _box_
we mean an axis-aligned one, i.e., the Cartesian product of closed intervals
of non-zero length). Dvořák, McCarty and Norin [6] noticed that this issue
disappears if we forbid such a combination of long and wide boxes, a condition
which can be expressed as follows. For two boxes $B_{1}$ and $B_{2}$, we write
$B_{1}\sqsubseteq B_{2}$ if $B_{2}$ contains a translate of $B_{1}$. We say
that $B_{1}$ and $B_{2}$ are _comparable_ if $B_{1}\sqsubseteq B_{2}$ or
$B_{2}\sqsubseteq B_{1}$. A _touching representation by comparable boxes_ of a
graph $G$ is a touching representation $f$ by boxes such that for every
$u,v\in V(G)$, the boxes $f(u)$ and $f(v)$ are comparable. Let the _comparable
box dimension_ $\operatorname{dim}_{cb}(G)$ of a graph $G$ be the smallest
integer $d$ such that $G$ has a touching representation by comparable boxes in
$\mathbb{R}^{d}$. Let us remark that the comparable box dimension of every
graph $G$ is at most $|V(G)|$, see Section 3.1 for details. Then for a class
${\cal G}$ of graphs, let $\operatorname{dim}_{cb}({\cal
G})\colonequals\sup\\{\operatorname{dim}_{cb}(G):G\in{\cal G}\\}$. Note that
$\operatorname{dim}_{cb}({\cal G})=\infty$ if the comparable box dimension of
graphs in ${\cal G}$ is not bounded.

Dvořák, McCarty and Norin [6] proved some basic properties of this notion. In
particular, they showed that if a class ${\cal G}$ has finite comparable box
dimension, then it has polynomial strong coloring numbers, which implies that
${\cal G}$ has strongly sublinear separators. They also provided an example
showing that for many functions $h$, the class of graphs with strong coloring
numbers bounded by $h$ has infinite comparable box dimension111In their
construction $h(r)$ has to be at least 3, and has to tend to $+\infty$..
Dvořák et al. [9] proved that graphs of comparable box dimension $3$ have
exponential weak coloring numbers, giving the first natural graph class with
polynomial strong coloring numbers and superpolynomial weak coloring numbers
(the previous example is obtained by subdividing edges of every graph suitably
many times [12]).

We show that the comparable box dimension behaves well under the operations of
addition of apex vertices, clique-sums, and taking subgraphs. Together with
known results on product structure [4], this implies the main result of this
paper.

######  Theorem 1.

The comparable box dimension of every proper minor-closed class of graphs is
finite.

Additionally, we show that classes of graphs with finite comparable box
dimension are fractionally treewidth-fragile. This gives arbitrarily precise
approximation algorithms for all monotone maximization problems that are
expressible in terms of distances between the solution vertices and tractable
on graphs of bounded treewidth [8] or expressible in the first-order logic
[7].

##  2 Parameters

In this section we bound some basic graph parameters in terms of comparable
box dimension. The first result bounds the clique number $\omega(G)$ in terms
of $\operatorname{dim}_{cb}(G)$.

######  Lemma 1.

For any graph $G$, we have $\omega(G)\leq 2^{\operatorname{dim}_{cb}(G)}$.

###### Proof.

We may assume that $G$ has bounded comparable box dimension witnessed by a
representation $f$. To represent any clique $A=\\{a_{1},\ldots,a_{w}\\}$ in
$G$, the corresponding boxes $f(a_{1}),\ldots,f(a_{w})$ have pairwise non-
empty intersections. Since axis-aligned boxes have the Helly property, there
is a point $p\in\mathbb{R}^{d}$ contained in $f(a_{1})\cap\cdots\cap
f(a_{w})$. As each box is full-dimensional, its interior intersects at least
one of the $2^{d}$ orthants at $p$. At the same time, it follows from the
definition of a touching representation that $f(a_{1}),\ldots,f(a_{d})$ have
pairwise disjoint interiors, and hence $w\leq 2^{d}$. ∎

Note that a clique with $2^{d}$ vertices has a touching representation by
comparable boxes in $\mathbb{R}^{d}$, where each vertex is a hypercube defined
as the Cartesian product of intervals of form $[-1,0]$ or $[0,1]$. Together
with Lemma 1, it follows that $\operatorname{dim}_{cb}(K_{2^{d}})=d$.

In the following we consider the chromatic number $\chi(G)$, and two of its
variants. An _acyclic coloring_ (resp. _star coloring_) of a graph $G$ is a
proper coloring such that any two color classes induce a forest (resp. star
forest, i.e., a forest in which each component is a star). The _acyclic
chromatic number_ $\chi_{a}(G)$ (resp. _star chromatic number_ $\chi_{s}(G)$)
of $G$ is the minimum number of colors in an acyclic (resp. star) coloring of
$G$. We will need the fact that all the variants of the chromatic number are
at most exponential in the comparable box dimension; this follows from [6],
although we include an argument to make the dependence clear.

######  Lemma 2.

For any graph $G$ we have $\chi(G)\leq 3^{\operatorname{dim}_{cb}(G)}$,
$\chi_{a}(G)\leq 5^{\operatorname{dim}_{cb}(G)}$ and $\chi_{s}(G)\leq 2\cdot
9^{\operatorname{dim}_{cb}(G)}$.

###### Proof.

We focus on the star chromatic number and note that the chromatic number and
the acyclic chromatic number may be bounded similarly. Suppose that $G$ has
comparable box dimension $d$ witnessed by a representation $f$, and let
$v_{1},\ldots,v_{n}$ be the vertices of $G$ written so that
$\operatorname{vol}(f(v_{1}))\geq\ldots\geq\operatorname{vol}(f(v_{n}))$.
Equivalently, we have $f(v_{i})\sqsubseteq f(v_{j})$ whenever $i>j$. Now
define a greedy coloring $c$ so that $c(v_{i})$ is the smallest color such
that $c(v_{i})\neq c(v_{j})$ for any $j<i$ for which either $v_{j}v_{i}\in
E(G)$ or there exists $m>j$ such that $v_{j}v_{m},v_{m}v_{i}\in E(G)$. Note
that this gives a star coloring, since a path on four vertices always contains
a 3-vertex subpath of the form $v_{i_{1}}v_{i_{2}}v_{i_{3}}$ such that
$i_{1}<i_{2},i_{3}$ and our coloring procedure gives distinct colors to
vertices forming such a path.

It remains to bound the number of colors used. Suppose we are coloring
$v_{i}$. We shall bound the number of vertices $v_{j}$ such that $j<i$ and
such that there exists $m>i$ for which $v_{j}v_{m},v_{m}v_{i}\in E(G)$. Let
$B$ be the box obtained by scaling up $f(v_{i})$ by a factor of 5 while
keeping the same center. Since $f(v_{m})\sqsubseteq f(v_{i})\sqsubseteq
f(v_{j})$, there exists a translation $B_{j}$ of $f(v_{i})$ contained in
$f(v_{j})\cap B$ (see Figure 1). Two boxes $B_{j}$ and $B_{j^{\prime}}$ for
$j\neq j^{\prime}$ have disjoint interiors since their intersection is
contained in the intersection of the touching boxes $f(v_{j})$ and
$f(v_{j^{\prime}})$, and their interiors are also disjoint from
$f(v_{i})\subset B$. Thus the number of such indices $j$ is at most
$\operatorname{vol}(B)/\operatorname{vol}(f(v_{i}))-1=5^{d}-1$.

A similar argument shows that the number of indices $m$ such that $m<i$ and
$v_{m}v_{i}\in E(G)$ is at most $3^{d}-1$. Consequently, the number of indices
$j<i$ for which there exists $m$ such that $j<m<i$ and
$v_{j}v_{m},v_{m}v_{i}\in E(G)$ is at most $(3^{d}-1)^{2}$. This means that
when choosing the color of $v_{i}$ greedily, we only need to avoid colors of
at most $(5^{d}-1)+(3^{d}-1)+(3^{d}-1)^{2}$ vertices, so $2\cdot 9^{d}$ colors
suffice. ∎

Figure 1: Nearby boxes obstructing colors at $v_{i}$.

##  3 Operations

It is clear that given a touching representation of a graph $G$, one can
easily obtains a touching representation by boxes of an induced subgraph $H$
of $G$ by simply deleting the boxes corresponding to the vertices in
$V(G)\setminus V(H)$. In this section we are going to consider other basic
operations on graphs. In the following, to describe the boxes, we are going to
use the Cartesian product $\times$ defined among boxes ($A\times B$ is the box
whose projection on the first dimensions gives the box $A$, while the
projection on the remaining dimensions gives the box $B$) or we are going to
provide its projections for every dimension ($A[i]$ is the interval obtained
from projecting $A$ on its $i^{\text{th}}$ dimension).

###  3.1 Vertex addition

Let us start with a simple lemma saying that the addition of a vertex
increases the comparable box dimension by at most one. In particular, this
implies that $\operatorname{dim}_{cb}(G)\leq|V(G)|$.

######  Lemma 3.

For any graph $G$ and $v\in V(G)$, we have
$\operatorname{dim}_{cb}(G)\leq\operatorname{dim}_{cb}(G-v)+1$.

###### Proof.

Let $f$ be a touching representation of $G-v$ by comparable boxes in
$\mathbb{R}^{d}$, where $d=\operatorname{dim}_{cb}(G-v)$. We define a
representation $h$ of $G$ as follows. For each $u\in V(G)\setminus\\{v\\}$,
let $h(u)=[0,1]\times f(u)$ if $uv\in E(G)$ and $h(u)=[1/2,3/2]\times f(u)$ if
$uv\not\in E(G)$. Let $h(v)=[-1,0]\times[-M,M]\times\cdots\times[-M,M]$, where
$M$ is chosen large enough so that
$f(u)\subseteq[-M,M]\times\cdots\times[-M,M]$ for every $u\in
V(G)\setminus\\{v\\}$. Then $h$ is a touching representation of $G$ by
comparable boxes in $\mathbb{R}^{d+1}$. ∎

###  3.2 Strong product

Let $G\boxtimes H$ denote the _strong product_ of the graphs $G$ and $H$,
i.e., the graph with vertex set $V(G)\times V(H)$ and with distinct vertices
$(u_{1},v_{1})$ and $(u_{2},v_{2})$ adjacent if and only if $u_{1}$ is equal
to or adjacent to $u_{2}$ in $G$ and $v_{1}$ is equal to or adjacent to
$v_{2}$ in $H$. To obtain a touching representation of $G\boxtimes H$ it
suffices to take a product of representations of $G$ and $H$, but the
resulting representation may contain incomparable boxes. Indeed,
$\operatorname{dim}_{cb}(G\boxtimes H)$ in general is not bounded by a
function of $\operatorname{dim}_{cb}(G)$ and $\operatorname{dim}_{cb}(H)$; for
example, every star has comparable box dimension at most two, but the strong
product of the star $K_{1,n}$ with itself contains $K_{n,n}$ as an induced
subgraph, and thus its comparable box dimension is at least $\Omega(\log n)$.
However, as shown in the following lemma, this issue does not arise if the
representation of $H$ consists of translates of a single box; by scaling, we
can without loss of generality assume this box is a unit hypercube.

######  Lemma 4.

Consider a graph $H$ having a touching representation $h$ in
$\mathbb{R}^{d_{H}}$ by axis-aligned hypercubes of unit size. Then for any
graph $G$, the strong product $G\boxtimes H$ of these graphs has comparable
box dimension at most $\operatorname{dim}_{cb}(G)+d_{H}$.

###### Proof.

The proof simply consists in taking a product of the two representations.
Indeed, consider a touching respresentation $g$ of $G$ by comparable boxes in
$\mathbb{R}^{d_{G}}$, with $d_{G}=\operatorname{dim}_{cb}(G)$, and the
representation $h$ of $H$. Let us define a representation $f$ of $G\boxtimes
H$ in $\mathbb{R}^{d_{G}+d_{H}}$ as follows.

$f((u,v))[i]=\begin{cases}g(u)[i]&\text{ if $i\leq d_{G}$}\\\
h(v)[i-d_{G}]&\text{ if $i>d_{G}$}\end{cases}$

Consider distinct vertices $(u,v)$ and $(u^{\prime},v^{\prime})$ of
$G\boxtimes H$. The boxes $g(u)$ and $g(u^{\prime})$ are comparable, say
$g(u)\sqsubseteq g(u^{\prime})$. Since $h(v^{\prime})$ is a translation of
$h(v)$, this implies that $f((u,v))\sqsubseteq f((u^{\prime},v^{\prime}))$.
Hence, the boxes of the representation $f$ are pairwise comparable.

The boxes of the representations $g$ and $h$ have pairwise disjoint interiors.
Hence, if $u\neq u^{\prime}$, then there exists $i\leq d_{G}$ such that the
interiors of the intervals $f((u,v))[i]=g(u)[i]$ and
$f((u^{\prime},v^{\prime}))[i]=g(u^{\prime})[i]$ are disjoint; and if $v\neq
v^{\prime}$, then there exists $i\leq d_{H}$ such that the interiors of the
intervals $f((u,v))[i+d_{G}]=h(v)[i]$ and
$f((u^{\prime},v^{\prime}))[i+d_{G}]=h(v^{\prime})[i]$ are disjoint.
Consequently, the interiors of boxes $f((u,v))$ and
$f((u^{\prime},v^{\prime}))$ are pairwise disjoint. Moreover, if $u\neq
u^{\prime}$ and $uu^{\prime}\not\in E(G)$, or if $v\neq v^{\prime}$ and
$vv^{\prime}\not\in E(G)$, then the intervals discussed above (not just their
interiors) are disjoint for some $i$; hence, if $(u,v)$ and
$(u^{\prime},v^{\prime})$ are not adjacent in $G\boxtimes H$, then
$f((u,v))\cap f((u^{\prime},v^{\prime}))=\emptyset$. Therefore, $f$ is a
touching representation of a subgraph of $G\boxtimes H$.

Finally, suppose that $(u,v)$ and $(u^{\prime},v^{\prime})$ are adjacent in
$G\boxtimes H$. Then there exists a point $p_{G}$ in the intersection of
$g(u)$ and $g(u^{\prime})$, since $u=u^{\prime}$ or $uu^{\prime}\in E(G)$ and
$g$ is a touching representation of $G$; and similarly, there exists a point
$p_{H}$ in the intersection of $h(v)$ and $h(v^{\prime})$. Then $p_{G}\times
p_{H}$ is a point in the intersection of $f((u,v))$ and
$f((u^{\prime},v^{\prime}))$. Hence, $f$ is indeed a touching representation
of $G\boxtimes H$. ∎

###  3.3 Taking a subgraph

The comparable box dimension of a subgraph of a graph $G$ may be larger than
$\operatorname{dim}_{cb}(G)$, see the end of this section for an example.
However, we show that the comparable box dimension of a subgraph is at most
exponential in the comparable box dimension of the whole graph. This is
essentially Corollary 25 in [6], but since the setting is somewhat different
and the construction of [6] uses rotated boxes, we provide details of the
argument.

######  Lemma 5.

If $G$ is a subgraph of a graph $G^{\prime}$, then
$\operatorname{dim}_{cb}(G)\leq\operatorname{dim}_{cb}(G^{\prime})+\frac{1}{2}\chi^{2}_{s}(G^{\prime})$.

###### Proof.

As we can remove the boxes that represent the vertices, we can assume
$V(G^{\prime})=V(G)$. Let $f$ be a touching representation of $G^{\prime}$ by
comparable boxes in $\mathbb{R}^{d}$, where
$d=\operatorname{dim}_{cb}(G^{\prime})$. Let $\varphi$ be a star coloring of
$G^{\prime}$ using colors $\\{1,\ldots,c\\}$, where $c=\chi_{s}(G^{\prime})$.

For any distinct colors $i,j\in\\{1,\ldots,c\\}$, let $A_{i,j}\subseteq V(G)$
be the set of vertices $u$ of color $i$ such that there exists a vertex $v$ of
color $j$ such that $uv\in E(G^{\prime})\setminus E(G)$. For each $u\in
A_{i,j}$, let $a_{j}(u)$ denote such a vertex $v$ chosen arbitrarily.

Let us define a representation $h$ by boxes in $\mathbb{R}^{d+\binom{c}{2}}$
by starting from the representation $f$ and, for each pair $i<j$ of colors,
adding a dimension $d_{i,j}$ and setting

$h(v)[d_{i,j}]=\begin{cases}[1/3,4/3]&\text{if $v\in A_{i,j}$}\\\
[-4/3,-1/3]&\text{if $v\in A_{j,i}$}\\\
[-1/2,1/2]&\text{otherwise.}\end{cases}$

Note that the boxes in this extended representation are comparable, as in the
added dimensions, all the boxes have size $1$.

Suppose $uv\in E(G)$, where $\varphi(u)=i$ and $\varphi(v)=j$ and say $i<j$.
We cannot have $u\in A_{i,j}$ and $v\in A_{j,i}$, as then $a_{j}(u)uva_{i}(v)$
would be a 4-vertex path in $G^{\prime}$ in colors $i$ and $j$. Hence, in any
added dimension $d^{\prime}$, we have $h(u)[d^{\prime}]=[-1/2,1/2]$ or
$h(v)[d^{\prime}]=[-1/2,1/2]$, and thus $h(u)[d^{\prime}]\cap
h(v)[d^{\prime}]\neq\emptyset$. Since the boxes $f(u)$ and $f(v)$ touch, it
follows that the boxes $h(u)$ and $h(v)$ touch as well.

Suppose now that $uv\not\in E(G)$. If $uv\not\in E(G^{\prime})$, then $f(u)$
is disjoint from $f(v)$, and thus $h(u)$ is disjoint from $h(v)$. Hence, we
can assume $uv\in E(G^{\prime})\setminus E(G)$, $\varphi(u)=i$, $\varphi(v)=j$
and $i<j$. Then $u\in A_{i,j}$, $v\in A_{j,i}$, $h(u)[d_{i,j}]=[1/3,4/3]$,
$h(v)[d_{j,i}]=[-4/3,-1/3]$, and $h(u)\cap h(v)=\emptyset$.

Consequently, $h$ is a touching representation of $G$ by comparable boxes in
dimension $d+\binom{c}{2}\leq d+c^{2}/2$. ∎

Let us now combine Lemmas 2 and 5.

######  Corollary 1.

If $G$ is a subgraph of a graph $G^{\prime}$, then
$\operatorname{dim}_{cb}(G)\leq\operatorname{dim}_{cb}(G^{\prime})+2\cdot
81^{\operatorname{dim}_{cb}(G^{\prime})}\leq 3\cdot
81^{\operatorname{dim}_{cb}(G^{\prime})}$.

Let us remark that an exponential increase in the dimension is unavoidable: We
have $\operatorname{dim}_{cb}(K_{2^{d}})=d$, but the graph obtained from
$K_{2^{d}}$ by deleting a perfect matching has comparable box dimension
$2^{d-1}$. Indeed, for every pair $u,v$ of non-adjacent vertices there is a
specific dimension $i$ such that their boxes span intervals $[a,b]$ and
$[c,d]$ with $b<c$, while for every other box in the representation their
$i^{\text{th}}$ interval contains $[b,c]$.

###  3.4 Clique-sums

A _clique-sum_ of two graphs $G_{1}$ and $G_{2}$ is obtained from their
disjoint union by identifying vertices of a clique in $G_{1}$ and a clique of
the same size in $G_{2}$ and possibly deleting some of the edges of the
resulting clique. A _full clique-sum_ is a clique-sum in which we keep all the
edges of the resulting clique. The main issue to overcome in obtaining a
representation for a (full) clique-sum is that the representations of $G_{1}$
and $G_{2}$ can be “degenerate”. Consider e.g. the case that $G_{1}$ is
represented by unit squares arranged in a grid; in this case, there is no
space to attach $G_{2}$ at the cliques formed by four squares intersecting in
a single corner. This can be avoided by increasing the dimension, but we need
to be careful so that the dimension stays bounded even after an arbitrary
number of clique-sums. We thus introduce the notion of _clique-sum extendable_
representations.

######  Definition 1.

Consider a graph $G$ with a distinguished clique $C^{\star}$, called the _root
clique_ of $G$. A touching representation $h$ of $G$ by (not necessarily
comparable) boxes in $\mathbb{R}^{d}$ is called _$C^{\star}$ -clique-sum
extendable_ if the following conditions hold for every sufficiently small
$\varepsilon>0$.

  * (vertices) For each $u\in V(C^{\star})$, there exists a dimension $d_{u}$, such that:

_(v0)_ $d_{u}\neq d_{u^{\prime}}$ for distinct $u,u^{\prime}\in V(C^{\star})$,

_(v1)_ each vertex $u\in V(C^{\star})$ satisfies $h(u)[d_{u}]=[-1,0]$ and
$h(u)[i]=[0,1]$ for any dimension $i\neq d_{u}$, and

_(v2)_ each vertex $v\notin V(C^{\star})$ satisfies $h(v)\subset[0,1)^{d}$.

  * (cliques) For every clique $C$ of $G$, there exists a point $p(C)\in[0,1)^{d}\cap\left(\bigcap_{v\in V(C)}h(v)\right)$ such that, defining the _clique box_ $h^{\varepsilon}(C)$ by setting $h^{\varepsilon}(C)[i]=[p(C)[i],p(C)[i]+\varepsilon]$ for every dimension $i$, the following conditions are satisfied:

_(c1)_ For any two cliques $C_{1}\neq C_{2}$, $h^{\varepsilon}(C_{1})\cap
h^{\varepsilon}(C_{2})=\emptyset$ (equivalently, $p(C_{1})\neq p(C_{2})$).

_(c2)_ A box $h(v)$ intersects $h^{\varepsilon}(C)$ if and only if $v\in
V(C)$, and in that case their intersection is a facet of $h^{\varepsilon}(C)$
incident to $p(C)$. That is, there exists a dimension $i_{C,v}$ such that for
each dimension $j$,

$h(v)[j]\cap h^{\varepsilon}(C)[j]=\begin{cases}\\{p(C)[i_{C,v}]\\}&\text{if
$j=i_{C,v}$}\\\ [p(C)[j],p(C)[j]+\varepsilon]&\text{otherwise.}\end{cases}$

Note that the root clique can be empty, that is the empty subgraph with no
vertices. In that case the clique is denoted $\emptyset$. Let
$\operatorname{dim}^{ext}_{cb}(G)$ be the minimum dimension such that $G$ has
an $\emptyset$-clique-sum extendable touching representation by comparable
boxes.

Let us remark that a clique-sum extendable representation in dimension $d$
implies such a representation in higher dimensions as well.

######  Lemma 6.

Let $G$ be a graph with a root clique $C^{\star}$ and let $h$ be a
$C^{\star}$-clique-sum extendable touching representation of $G$ by comparable
boxes in $\mathbb{R}^{d}$. Then $G$ has such a representation in
$\mathbb{R}^{d^{\prime}}$ for every $d^{\prime}\geq d$.

###### Proof.

It clearly suffices to consider the case that $d^{\prime}=d+1$. Note that the
(vertices) conditions imply that $h(v^{\prime})\sqsubseteq h(v)$ for every
$v^{\prime}\in V(G)\setminus V(C^{\star})$ and $v\in V(C^{\star})$. We extend
the representation $h$ by setting $h(v)[d+1]=[0,1]$ for $v\in V(C^{\star})$
and $h(v)[d+1]=[0,\frac{1}{2}]$ for $v\in V(G)\setminus V(C^{\star})$. The
clique point $p(C)$ of each clique $C$ is extended by setting
$p(C)[d+1]=\frac{1}{4}$. It is easy to verify that the resulting
representation is $C^{\star}$-clique-sum extendable. ∎

The following lemma ensures that clique-sum extendable representations behave
well with respect to full clique-sums.

######  Lemma 7.

Consider two graphs $G_{1}$ and $G_{2}$, given with a $C^{\star}_{1}$\- and a
$C^{\star}_{2}$-clique-sum extendable representations $h_{1}$ and $h_{2}$ by
comparable boxes in $\mathbb{R}^{d_{1}}$ and $\mathbb{R}^{d_{2}}$,
respectively. Let $G$ be the graph obtained by performing a full clique-sum of
these two graphs on any clique $C_{1}$ of $G_{1}$, and on the root clique
$C^{\star}_{2}$ of $G_{2}$. Then $G$ admits a $C^{\star}_{1}$-clique sum
extendable representation $h$ by comparable boxes in
$\mathbb{R}^{\max(d_{1},d_{2})}$.

###### Proof.

By Lemma 6, we can assume that $d_{1}=d_{2}$; let $d=d_{1}$. The idea is to
translate (allowing also exchanges of dimensions) and scale $h_{2}$ to fit in
$h_{1}^{\varepsilon}(C_{1})$. Consider an $\varepsilon>0$ sufficiently small
so that $h_{1}^{\varepsilon}(C_{1})$ satisfies all the (cliques) conditions,
and such that $h_{1}^{\varepsilon}(C_{1})\sqsubseteq h_{1}(v)$ for any vertex
$v\in V(G_{1})$. Let $V(C_{1})=\\{v_{1},\ldots,v_{k}\\}$; without loss of
generality, we can assume $i_{C_{1},v_{i}}=i$ for $i\in\\{1,\ldots,k\\}$, and
thus

$h_{1}(v_{i})[j]\cap
h_{1}^{\varepsilon}(C_{1})[j]=\begin{cases}\\{p_{1}(C_{1})[i]\\}&\text{ if
$j=i$}\\\ [p_{1}(C_{1})[j],p_{1}(C_{1})[j]+\varepsilon]&\text{
otherwise.}\end{cases}$

Now let us consider $G_{2}$ and its representation $h_{2}$. Here the vertices
of $C^{\star}_{2}$ are also denoted $v_{1},\ldots,v_{k}$, and without loss of
generality, the (vertices) conditions are satisfied by setting $d_{v_{i}}=i$
for $i\in\\{1,\ldots,k\\}$

We are now ready to define $h$. For $v\in V(G_{1})$, we set $h(v)=h_{1}(v)$.
We now scale and translate $h_{2}$ to fit inside $h_{1}^{\varepsilon}(C_{1})$.
That is, we fix $\varepsilon>0$ small enough so that

  * •

the conditions (cliques) hold for $h_{1}$,

  * •

$h_{1}^{\varepsilon}(C_{1})\subset[0,1)^{d}$, and

  * •

$h_{1}^{\varepsilon}(C_{1})\sqsubseteq h_{1}(u)$ for every $u\in V(G_{1})$,

and for each $v\in V(G_{2})\setminus V(C^{\star}_{2})$, we set
$h(v)[i]=p_{1}(C_{1})[i]+\varepsilon h_{2}(v)[i]$ for $i\in\\{1,\ldots,d\\}$.
Note that the condition (v2) for $h_{2}$ implies $h(v)\subset
h_{1}^{\varepsilon}(C_{1})$. Each clique $C$ of $H$ is a clique of $G_{1}$ or
$G_{2}$. If $C$ is a clique of $G_{2}$, we set $p(C)=p_{1}(C_{1})+\varepsilon
p_{2}(C)$, otherwise we set $p(C)=p_{1}(C)$. In particular, for subcliques of
$C_{1}=C^{\star}_{2}$, we use the former choice.

Let us now check that $h$ is a $C^{\star}_{1}$-clique sum extendable
representation by comparable boxes. The fact that the boxes are comparable
follows from the fact that those of $h_{1}$ and $h_{2}$ are comparable and
from the scaling of $h_{2}$: By construction both $h_{1}(v)\sqsubseteq
h_{1}(u)$ and $h_{2}(v)\sqsubseteq h_{2}(u)$ imply $h(v)\sqsubseteq h(u)$, and
for any vertex $u\in V(G_{1})$ and any vertex $v\in V(G_{2})\setminus
V(C^{\star}_{2})$, we have $h(v)\subset h_{1}^{\varepsilon}(C_{1})\sqsubseteq
h(u)$.

We now check that $h$ is a contact representation of $G$. For $u,v\in
V(G_{1})$ (resp. $u,v\in V(G_{2})\setminus V(C^{\star}_{2})$) it is clear that
$h(u)$ and $h(v)$ have disjoint interiors, and that they intersect if and only
if $h_{1}(u)$ and $h_{1}(v)$ intersect (resp. if $h_{2}(u)$ and $h_{2}(v)$
intersect). Consider now a vertex $u\in V(G_{1})$ and a vertex $v\in
V(G_{2})\setminus V(C^{\star}_{2})$. As $h(v)\subset h^{\varepsilon}(C_{1})$,
the condition (v2) for $h_{1}$ implies that $h(u)$ and $h(v)$ have disjoint
interiors.

Furthermore, if $uv\in E(G)$, then $u\in V(C_{1})=V(C^{\star}_{2})$, say
$u=v_{1}$. Since $uv\in E(G_{2})$, the intervals $h_{2}(u)[1]$ and
$h_{2}(v)[1]$ intersect, and by (v1) and (v2) for $h_{2}$, we conclude that
$h_{2}(v)[1]=[0,\alpha]$ for some positive $\alpha<1$. Therefore,
$p_{1}(C_{1})[1]\in h(v)[1]$. Since $p_{1}(C_{1})\in\bigcap_{x\in
V(C_{1})}h_{1}(x)$, we have $p_{1}(C_{1})\in h(u)$, and thus
$p_{1}(C_{1})[1]\in h(u)[1]\cap h(v)[1]$. For $i\in\\{2,\ldots,d\\}$, note
that $i\neq 1=i_{C_{1},u}$, and thus by (c2) for $h_{1}$, we have
$h_{1}^{\varepsilon}(C_{1})[i]\subseteq h_{1}(u)[i]=h(u)[i]$. Since
$h(v)[i]\subseteq h_{1}^{\varepsilon}(C_{1})[i]$, it follows that $h(u)$
intersects $h(v)$.

Finally, let us consider the $C^{\star}_{1}$-clique-sum extendability. The
(vertices) conditions hold, since (v0) and (v1) are inherited from $h_{1}$,
and (v2) is inherited from $h_{1}$ for $v\in V(G_{1})\setminus
V(C^{\star}_{1})$ and follows from the fact that $h(v)\subseteq
h_{1}^{\varepsilon}(C_{1})\subset[0,1)^{d}$ for $v\in V(G_{2})\setminus
V(C^{\star}_{2})$. For the (cliques) condition (c1), the mapping $p$ inherits
injectivity when restricted to cliques of $G_{2}$, or to cliques of $G_{1}$
not contained in $C_{1}$. For any clique $C$ of $G_{2}$, the point $p(C)$ is
contained in $h_{1}^{\varepsilon}(C_{1})$, since $p_{2}(C)\in[0,1)^{d}$. On
the other hand, if $C^{\prime}$ is a clique of $G_{1}$ not contained in
$C_{1}$, then there exists $v\in V(C^{\prime})\setminus V(C_{1})$, we have
$p(C^{\prime})=p_{1}(C^{\prime})\in h_{1}(v)$, and $h_{1}(v)\cap
h_{1}^{\varepsilon}(C_{1})=\emptyset$ by (c2) for $h_{1}$. Therefore, the
mapping $p$ is injective, and thus for sufficiently small
$\varepsilon^{\prime}>0$, we have $h^{\varepsilon^{\prime}}(C)\cap
h^{\varepsilon^{\prime}}(C^{\prime})=\emptyset$ for any distinct cliques $C$
and $C^{\prime}$ of $G$.

The condition (c2) of $h$ is (for sufficiently small $\varepsilon^{\prime}>0$)
inherited from the property (c2) of $h_{1}$ and $h_{2}$ when $C$ is a clique
of $G_{2}$ and $v\in V(G_{2})\setminus V(C^{\star}_{2})$, or when $C$ is a
clique of $G_{1}$ not contained in $C_{1}$ and $v\in V(G_{1})$. If $C$ is a
clique of $G_{1}$ not contained in $C_{1}$ and $v\in V(G_{2})\setminus
V(C^{\star}_{2})$, then by (c1) for $h_{1}$ we have
$h_{1}^{\varepsilon}(C)\cap h_{1}^{\varepsilon}(C_{1})=\emptyset$, and since
$h^{\varepsilon^{\prime}}(C)\subseteq h_{1}^{\varepsilon}(C)$ and
$h(v)\subseteq h_{1}^{\varepsilon}(C_{1})$, we conclude that $h(v)\cap
h^{\varepsilon^{\prime}}(C)=\emptyset$. It remains to consider the case that
$C$ is a clique of $G_{2}$ and $v\in V(G_{1})$. Note that
$h^{\varepsilon^{\prime}}(C)\subseteq h_{1}^{\varepsilon}(C_{1})$.

  * •

If $v\not\in V(C_{1})$, then by the property (c2) of $h_{1}$, the box
$h(v)=h_{1}(v)$ is disjoint from $h_{1}^{\varepsilon}(C_{1})$, and thus
$h(v)\cap h^{\varepsilon^{\prime}}(C)=\emptyset$.

  * •

Otherwise $v\in V(C_{1})=V(C^{\star}_{2})$, say $v=v_{1}$. Note that by (v1),
we have $h_{2}(v)=[-1,0]\times[0,1]^{d-1}$.

    * –

If $v\not\in V(C)$, then by the property (c2) of $h_{2}$, the box $h_{2}(v)$
is disjoint from $h_{2}^{\varepsilon}(C)$. Since
$h_{2}^{\varepsilon}(C)[i]\subseteq[0,1]=h_{2}(v)[i]$ for
$i\in\\{2,\ldots,d\\}$, it follows that
$h_{2}^{\varepsilon}(C)[1]\subseteq(0,1)$, and thus
$h^{\varepsilon^{\prime}}(C)[1]\subseteq
h_{1}^{\varepsilon}(C_{1})[1]\setminus\\{p(C_{1})[1]\\}$. By (c2) for $h_{1}$,
we have $h(v)[1]\cap h_{1}^{\varepsilon}(C_{1})[1]=h_{1}(v)[1]\cap
h_{1}^{\varepsilon}(C_{1})[1]=p(C_{1})[1]$, and thus $h(v)\cap
h^{\varepsilon^{\prime}}(C)=\emptyset$.

    * –

If $v\in V(C)$, then by the property (c2) of $h_{2}$, the intersection of
$h_{2}(v)[1]=[-1,0]$ and $h_{2}^{\varepsilon}(C)[1]\subseteq[0,1)$ is the
single point $p_{2}(C)[1]=0$, and thus $p(C)[1]=p_{1}(C_{1})[1]$ and
$h^{\varepsilon^{\prime}}(C)[1]=[p_{1}(C_{1})[1],p_{1}(C_{1})[1]+\varepsilon^{\prime}]$.
Recall that the property (c2) of $h_{1}$ implies $h(v)[1]\cap
h_{1}^{\varepsilon}(C_{1})[1]=\\{p(C_{1})[1]\\}$, and thus $h(v)[1]\cap
h^{\varepsilon^{\prime}}(C)[1]=\\{p(C)[1]\\}$. For $i\in\\{2,\ldots,d\\}$, the
property (c2) of $h_{1}$ implies $h_{1}^{\varepsilon}(C_{1})[i]\subseteq
h_{1}(v)[i]=h(v)[i]$, and since $h^{\varepsilon^{\prime}}(C)[i]\subseteq
h_{1}^{\varepsilon}(C_{1})[i]$, it follows that
$h^{\varepsilon^{\prime}}(C)[i]\subseteq h(v)[i]$.

∎

The following lemma enables us to pick the root clique at the expense of
increasing the dimension by $\omega(G)$.

######  Lemma 8.

For any graph $G$ and any clique $C^{\star}$, the graph $G$ admits a
$C^{\star}$-clique-sum extendable touching representation by comparable boxes
in $\mathbb{R}^{d}$, for
$d=|V(C^{\star})|+\operatorname{dim}^{ext}_{cb}(G\setminus V(C^{\star}))$.

###### Proof.

The proof is essentially the same as the one of Lemma 3. Consider a
$\emptyset$-clique-sum extendable touching representation $h^{\prime}$ of
$G\setminus V(C^{\star})$ by comparable boxes in $\mathbb{R}^{d^{\prime}}$,
with $d^{\prime}=\operatorname{dim}_{cb}(G\setminus V(C^{\star}))$, and let
$V(C^{\star})=\\{v_{1},\ldots,v_{k}\\}$. We now construct the desired
representation $h$ of $G$ as follows. For each vertex $v_{i}\in V(C^{\star})$,
let $h(v_{i})$ be the box in $\mathbb{R}^{d}$ uniquely determined by the
condition (v1) with $d_{v_{i}}=i$. For each vertex $u\in V(G)\setminus
V(C^{\star})$, if $i\leq k$ then let $h(u)[i]=[0,1/2]$ if $uv_{i}\in E(G)$,
and $h(u)[i]=[1/4,3/4]$ if $uv_{i}\notin E(G)$. For $i>k$ we have
$h(u)[i]=\alpha h^{\prime}(u)[i-k]$, for some $\alpha>0$. The value $\alpha>0$
is chosen sufficiently small so that $h(u)[i]\subset[0,1)$ whenever $u\notin
V(C^{\star})$. We proceed similarly for the clique points. For any clique $C$
of $G$, if $i\leq k$ then let $p(C)[i]=0$ if $v_{i}\in V(C)$, and
$p(C)[i]=1/4$ if $v_{i}\notin V(C)$. For $i>k$ we refer to the clique point
$p^{\prime}(C^{\prime})$ of $C^{\prime}=C\setminus\\{v_{1},\ldots,v_{k}\\}$,
and we set $p(C)[i]=\alpha p^{\prime}(C^{\prime})[i-k]$.

By the construction, it is clear that $h$ is a touching representation of $G$.
As $h^{\prime}(u)\sqsubset h^{\prime}(v)$ implies that $h(u)\sqsubset h(v)$,
and as $h(u)\sqsubset h(v_{i})$ for every $u\in V(G)\setminus V(C^{\star})$
and every $v_{i}\in V(C^{\star})$, we have that $h$ is a representation by
comparable boxes.

For the $C^{\star}$-clique-sum extendability, the (vertices) conditions hold
by the construction. For the (cliques) condition (c1), let us consider
distinct cliques $C_{1}$ and $C_{2}$ of $G$ such that
$|V(C_{1})|\geq|V(C_{2})|$, and let $C^{\prime}_{i}=C_{i}\setminus
V(C^{\star})$. If $C^{\prime}_{1}=C^{\prime}_{2}$, there is a vertex $v_{i}\in
V(C_{1})\setminus V(C_{2})$, and $p(C_{1})[i]=0\neq 1/4=p(C_{2})[i]$.
Otherwise, if $C^{\prime}_{1}\neq C^{\prime}_{2}$, then
$p^{\prime}(C^{\prime}_{1})\neq p^{\prime}(C^{\prime}_{2})$, which implies
$p(C_{1})\neq p(C_{2})$ by construction.

For the (cliques) condition (c2), let us first consider a vertex $v\in
V(G)\setminus V(C^{\star})$ and a clique $C$ of $G$ containing $v$. In the
dimensions $i\in\\{1,\ldots,k\\}$, we always have
$h^{\varepsilon}(C)[i]\subseteq h(v)[i]$. Indeed, if $v_{i}\in V(C)$, then
$h^{\varepsilon}(C)[i]\subseteq[0,1/2]=h(v)[i]$, as in this case $v$ and
$v_{i}$ are adjacent; and if $v_{i}\notin V(C)$, then
$h^{\varepsilon}(C)[i]\subseteq[1/4,1/2]\subseteq h(v)[i]$. By the property
(c2) of $h^{\prime}$, we have $h^{\varepsilon}(C)[i]\subseteq h(v)[i]$ for
every $i>k$, except one, for which $h^{\varepsilon}(C)[i]\cap
h(v)[i]=\\{p(C)[i]\\}$.

Next, let us consider a vertex $v\in V(G)\setminus V(C^{\star})$ and a clique
$C$ of $G$ not containing $v$. As $v\notin V(C^{\prime})$, the condition (c2)
for $h^{\prime}$ implies that $p^{\prime}(C^{\prime})$ is disjoint from
$h^{\prime}(v)$, and thus $p(C)$ is disjoint from $h(v)$.

Finally, we consider a vertex $v_{i}\in V(C^{\star})$. Note that for any
clique $C$ containing $v_{i}$, we have that $h^{\varepsilon}(C)[i]\cap
h(v_{i})[i]=[0,\varepsilon]\cap[-1,0]=\\{0\\}$, and
$h^{\varepsilon}(C)[j]\subseteq[0,1]=h(v_{i})[j]$ for any $j\neq i$. For a
clique $C$ that does not contain $v_{i}$ we have that
$h^{\varepsilon}(C)[i]\cap h(v_{i})[i]\subset(0,1)\cap[-1,0]=\emptyset$.
Condition (c2) is thus fulfilled and this completes the proof of the lemma. ∎

The following lemma provides an upper bound on
$\operatorname{dim}^{ext}_{cb}(G)$ in terms of $\operatorname{dim}_{cb}(G)$
and $\chi(G)$.

######  Lemma 9.

For any graph $G$,
$\operatorname{dim}^{ext}_{cb}(G)\leq\operatorname{dim}_{cb}(G)+\chi(G)$.

###### Proof.

Let $h$ be a touching representation of $G$ by comparable boxes in
$\mathbb{R}^{d}$, with $d=\operatorname{dim}_{cb}(G)$, and let $c$ be a
$\chi(G)$-coloring of $G$. We start with a slightly modified version of $h$.
We first scale $h$ to fit in $(0,1)^{d}$, and for a sufficiently small real
$\alpha>0$ we increase each box in $h$ by $2\alpha$ in every dimension, that
is we replace $h(v)[i]=[a,b]$ by $[a-\alpha,b+\alpha]$ for each vertex $v$ and
dimension $i$. We choose $\alpha$ sufficiently small so that the boxes
representing non-adjacent vertices remain disjoint, and thus the resulting
representation $h_{1}$ is an intersection representation of the same graph
$G$. Moreover, observe that for every clique $C$ of $G$, the intersection
$I_{C}=\bigcap_{v\in V(C)}h_{1}(v)$ is a box with non-zero edge lengths. For
any clique $C$ of $G$, let $p_{1}(C)$ be a point in the interior of $I_{C}$
different from the points chosen for all other cliques.

Now we add $\chi(G)$ dimensions to make the representation touching again, and
to ensure some space for the clique boxes $h^{\varepsilon}(C)$. Formally we
define $h_{2}$ as follows.

$h_{2}(u)[i]=\begin{cases}h_{1}(u)[i]&\text{ if $i\leq d$}\\\ [1/5,3/5]&\text{
if $i>d$ and $c(u)<i-d$}\\\ [0,2/5]&\text{ if $i>d$ and $c(u)=i-d$}\\\
[2/5,4/5]&\text{ otherwise (if $c(u)>i-d>0$)}\end{cases}$

For any clique $C$ of $G$, let $c(C)$ denote the color set $\\{c(u)\ |\ u\in
V(C)\\}$. We now set

$p_{2}(C)[i]=\begin{cases}p_{1}(C)[i]&\text{ if $i\leq d$}\\\ 2/5&\text{ if
$i>d$ and $i-d\in c(C)$}\\\ 1/2&\text{ otherwise}\end{cases}$

As $h_{2}$ is an extension of $h_{1}$, and as in each dimension $j>d$,
$h_{2}(v)[j]$ is an interval of length $2/5$ containing the point $2/5$ for
every vertex $v$, we have that $h_{2}$ is an intersection representation of
$G$ by comparable boxes. To prove that it is touching consider two adjacent
vertices $u$ and $v$ such that $c(u)<c(v)$, and let us note that
$h_{2}(u)[d+c(u)]=[0,2/5]$ and $h_{2}(v)[d+c(u)]=[2/5,4/5]$.

For the $\emptyset$-clique-sum extendability, the (vertices) conditions are
void. For the (cliques) conditions, since $p_{1}$ is chosen to be injective,
the mapping $p_{2}$ is injective as well, implying that (c1) holds.

Consider now a clique $C$ in $G$ and a vertex $v\in V(G)$. If $c(v)\not\in
c(C)$, then $h_{2}(v)[c(v)+d]=[0,2/5]$ and $p_{2}(C)[c(v)+d]=1/2$, implying
that $h_{2}^{\varepsilon}(C)\cap h_{2}(v)=\emptyset$. If $c(v)\in c(C)$ but
$v\not\in V(C)$, then letting $v^{\prime}\in V(C)$ be the vertex of color
$c(v)$, we have $vv^{\prime}\not\in E(G)$, and thus $h_{1}(v)$ is disjoint
from $h_{1}(v^{\prime})$. Since $p_{1}(C)$ is contained in the interior of
$h_{1}(v^{\prime})$, it follows that $h_{2}^{\varepsilon}(C)\cap
h_{2}(v)=\emptyset$. Finally, suppose that $v\in C$. Since $p_{1}(C)$ is
contained in the interior of $h_{1}(v)$, we have
$h_{2}^{\varepsilon}(C)[i]\subset h_{2}(v)[i]$ for every $i\leq d$. For $i>d$
distinct from $d+c(v)$, we have $p_{2}^{\varepsilon}(C)[i]\in\\{2/5,1/2\\}$
and $[2/5,3/5]\subseteq h_{2}(v)[i]$, and thus
$h_{2}^{\varepsilon}(C)[i]\subset h_{2}(v)[i]$. For $i=d+c(v)$, we have
$p_{2}^{\varepsilon}(C)[i]=2/5$ and $h_{2}(v)[i]=[0,2/5]$, and thus
$h_{2}^{\varepsilon}(C)[i]\cap h_{2}(v)[i]=\\{p_{2}^{\varepsilon}(C)[i]\\}$.
Therefore, (c2) holds. ∎

A touching representation of axis-aligned boxes in $\mathbb{R}^{d}$ is said
_fully touching_ if any two intersecting boxes intersect on a
$(d-1)$-dimensional box. Note that the construction above is fully touching.
Indeed, two intersecting boxes corresponding to vertices $u,v$ of colors
$c(u)<c(v)$, only touch at coordinate $2/5$ in the $(d+c(u))^{\text{th}}$
dimension, while they fully intersect in every other dimension. This
observation with Lemma 2 lead to the following.

######  Corollary 2.

Any graph $G$ has a fully touching representation of comparable axis-aligned
boxes in $\mathbb{R}^{d}$, where
$d=\operatorname{dim}_{cb}(G)+3^{\operatorname{dim}_{cb}(G)}$.

Together, the lemmas from this section show that comparable box dimension is
almost preserved by full clique-sums.

######  Corollary 3.

Let ${\cal G}$ be a class of graphs of chromatic number at most $k$. If ${\cal
G}^{\prime}$ is the class of graphs obtained from ${\cal G}$ by repeatedly
performing full clique-sums, then

$\operatorname{dim}_{cb}({\cal G}^{\prime})\leq\operatorname{dim}_{cb}({\cal
G})+2k.$

###### Proof.

Suppose a graph $G$ is obtained from $G_{1},\ldots,G_{m}\in{\cal G}$ by
performing full clique-sums. Without loss of generality, the labelling of the
graphs is chosen so that we first perform the full clique-sum on $G_{1}$ and
$G_{2}$, then on the resulting graph and $G_{3}$, and so on. Let
$C^{\star}_{1}=\emptyset$ and for $i=2,\ldots,m$, let $C^{\star}_{i}$ be the
root clique of $G_{i}$ on which it is glued in the full clique-sum operation.
By Lemmas 9 and 8, $G_{i}$ has a $C_{i}^{\star}$-clique-sum extendable
touching representation by comparable boxes in $\mathbb{R}^{d}$, where
$d=\operatorname{dim}_{cb}({\cal G})+2k$. Repeatedly applying Lemma 7, we
conclude that $\operatorname{dim}_{cb}(G)\leq d$. ∎

By Lemmas 2 and 5, this gives the following bounds.

######  Corollary 4.

Let ${\cal G}$ be a class of graphs of comparable box dimension at most $d$.

  * •

The class ${\cal G}^{\prime}$ of graphs obtained from ${\cal G}$ by repeatedly
performing full clique-sums has comparable box dimension at most $d+2\cdot
3^{d}$.

  * •

The closure of ${\cal G}^{\prime}$ by taking subgraphs has comparable box
dimension at most $1250^{d}$.

###### Proof.

The former bound directly follows from Corollary 3 and the bound on the
chromatic number from Lemma 2. For the latter one, we need to bound the star
chromatic number of ${\cal G}^{\prime}$. Suppose a graph $G$ is obtained from
$G_{1},\ldots,G_{m}\in{\cal G}$ by performing full clique-sums. For
$i=1,\ldots,m$, suppose $G_{i}$ has an acyclic coloring $\varphi_{i}$ by at
most $k$ colors. Note that the vertices of any clique get pairwise different
colors, and thus by permuting the colors, we can ensure that when we perform
the full clique-sum, the vertices that are identified have the same color.
Hence, we can define a coloring $\varphi$ of $G$ such that for each $i$, the
restriction of $\varphi$ to $V(G_{i})$ is equal to $\varphi_{i}$. Let $C$ be
the union of any two color classes of $\varphi$. Then for each $i$,
$G_{i}[C\cap V(G_{i})]$ is a forest, and since $G[C]$ is obtained from these
graphs by full clique-sums, $G[C]$ is also a forest. Hence, $\varphi$ is an
acyclic coloring of $G$ by at most $k$ colors. By [1], $G$ has a star coloring
by at most $2k^{2}-k$ colors. Hence, Lemma 2 implies that ${\cal G}^{\prime}$
has star chromatic number at most $2\cdot 25^{d}-5^{d}$. The bound on the
comparable box dimension of subgraphs of graphs from ${\cal G}^{\prime}$ then
follows from Lemma 5. ∎

##  4 The strong product structure and minor-closed classes

A _$k$ -tree_ is any graph obtained by repeated full clique-sums on cliques of
size $k$ from cliques of size at most $k+1$. A _$k$ -tree-grid_ is a strong
product of a $k$-tree and a path. An _extended $k$-tree-grid_ is a graph
obtained from a $k$-tree-grid by adding at most $k$ apex vertices. Dujmović et
al. [4] proved the following result.

######  Theorem 2.

Any graph $G$ is a subgraph of the strong product of a $k$-tree-grid and
$K_{m}$, where

  * •

$k=3$ and $m=3$ if $G$ is planar, and

  * •

$k=4$ and $m=\max(2g,3)$ if $G$ has Euler genus at most $g$.

Moreover, for every $t$, there exists an integer $k$ such that any
$K_{t}$-minor-free graph $G$ is a subgraph of a graph obtained by repeated
clique-sums from extended $k$-tree-grids.

Let us first bound the comparable box dimension of a graph in terms of its
Euler genus. As paths and $m$-cliques admit touching representations with
hypercubes of unit size in $\mathbb{R}^{1}$ and in
$\mathbb{R}^{\lceil\log_{2}m\rceil}$ respectively, by Lemma 4 it suffices to
bound the comparable box dimension of $k$-trees.

######  Theorem 3.

For any $k$-tree $G$,
$\operatorname{dim}_{cb}(G)\leq\operatorname{dim}^{ext}_{cb}(G)\leq k+1$.

###### Proof.

Let $H$ be a complete graph with $k+1$ vertices and let $C^{\star}$ be a
clique of size $k$ in $H$. By Lemma 7, it suffices to show that $H$ has a
$C^{\star}$-clique-sum extendable touching representation by hypercubes in
$\mathbb{R}^{k+1}$. Let $V(C^{\star})=\\{v_{1},\ldots,v_{k}\\}$. We construct
the representation $h$ so that (v1) holds with $d_{v_{i}}=i$ for each $i$;
this uniquely determines the hypercubes $h(v_{1})$, …, $h(v_{k})$. For the
vertex $v_{k+1}\in V(H)\setminus V(C^{\star})$, we set
$h(v_{k+1})=[0,1/2]^{k+1}$. This ensures that the (vertices) conditions holds.

For the (cliques) conditions, let us set the point $p(C)$ for every clique $C$
as follows:

  * •

$p(C)[i]=0$ for every $i\leq k$ such that $v_{i}\in C$

  * •

$p(C)[i]=\frac{1}{4}$ for every $i\leq k$ such that $v_{i}\notin C$

  * •

$p(C)[k+1]=\frac{1}{2}$ if $v_{k+1}\in C$

  * •

$p(C)[k+1]=\frac{3}{4}$ if $v_{k+1}\notin C$

By construction, it is clear that for each vertex $v\in V(H)$, $p(C)\in h(v)$
if and only if $v\in V(C)$.

For any two distinct cliques $C_{1}$ and $C_{2}$, the points $p(C_{1})$ and
$p(C_{2})$ are distinct. Indeed, by symmetry we can assume that for some $i$
we have $v_{i}\in V(C_{1})\setminus V(C_{2})$, and this implies that
$p(C_{1})[i]<p(C_{2})[i]$. Hence, the condition (c1) holds.

Consider now a vertex $v_{i}$ and a clique $C$. As we observed before, if
$v_{i}\not\in V(C)$, then $p(C)\not\in h(v_{i})$, and thus
$h^{\varepsilon}(C)$ and $h(v_{i})$ are disjoint (for sufficiently small
$\varepsilon>0$). If $v_{i}\in C$, then the definitions ensure that $p(C)[i]$
is equal to the maximum of $h(v_{i})[i]$, and that for $j\neq i$, $p(C)[j]$ is
in the interior of $h(v_{i})[j]$, implying $h(v_{i})[j]\cap
h^{\varepsilon}(C)[j]=[p(C)[j],p(C)[j]+\varepsilon]$ for sufficiently small
$\varepsilon>0$. ∎

The _treewidth_ $\operatorname{tw}(G)$ of a graph $G$ is the minimum $k$ such
that $G$ is a subgraph of a $k$-tree. Note that actually the bound on the
comparable box dimension of Theorem 3 extends to graphs of treewidth at most
$k$.

######  Corollary 5.

Every graph $G$ satisfies
$\operatorname{dim}_{cb}(G)\leq\operatorname{tw}(G)+1$.

###### Proof.

Let $k=\operatorname{tw}(G)$. Observe that there exists a $k$-tree $T$ with
the root clique $C^{\star}$ such that $G\subseteq T-V(C^{\star})$. Inspection
of the proof of Theorem 3 (and Lemma 7) shows that we obtain a representation
$h$ of $T-V(C^{\star})$ in $\mathbb{R}^{k+1}$ such that

  * •

the vertices are represented by hypercubes of pairwise different sizes,

  * •

if $uv\in E(T-V(C^{\star}))$ and $h(u)\sqsubseteq h(v)$, then $h(u)\cap h(v)$
is a facet of $h(u)$ incident with its point with minimum coordinates, and

If for some $u,v\in V(G)$, we have $uv\in E(T)\setminus E(G)$, where without
loss of generality $h(u)\sqsubseteq h(v)$, we now alter the representation by
shrinking $h(u)$ slightly away from $h(v)$ (so that all other touchings are
preserved). Since the hypercubes of $h$ have pairwise different sizes, the
resulting touching representation of $G$ is by comparable boxes. ∎

As every planar graph $G$ has a touching representation by cubes in
$\mathbb{R}^{3}$ [11], we have that $\operatorname{dim}_{cb}(G)\leq 3$. For
the graphs with higher Euler genus we can also derive upper bounds. Indeed,
combining the previous observation on the representations of paths and
$K_{m}$, with Theorem 3, Lemma 4, and Corollary 1 we obtain:

######  Corollary 6.

For every graph $G$ of Euler genus $g$, there exists a supergraph $G^{\prime}$
of $G$ such that $\operatorname{dim}_{cb}(G^{\prime})\leq
6+\lceil\log_{2}\max(2g,3)\rceil$. Consequently,

$\operatorname{dim}_{cb}(G)\leq 3\cdot 81^{7}\cdot\max(2g,3)^{\log_{2}81}.$

Similarly, we can deal with proper minor-closed classes.

###### Proof of Theorem 1.

Let ${\cal G}$ be a proper minor-closed class. Since ${\cal G}$ is proper,
there exists $t$ such that $K_{t}\not\in{\cal G}$. By Theorem 2, there exists
$k$ such that every graph in ${\cal G}$ is a subgraph of a graph obtained by
repeated clique-sums from extended $k$-tree-grids. As we have seen, $k$-tree-
grids have comparable box dimension at most $k+2$, and by Lemma 3, extended
$k$-tree-grids have comparable box dimension at most $2k+2$. By Corollary 4,
it follows that $\operatorname{dim}_{cb}({\cal G})\leq 1250^{2k+2}$. ∎

Note that the graph obtained from $K_{2n}$ by deleting a perfect matching has
Euler genus $\Theta(n^{2})$ and comparable box dimension $n$. It follows that
the dependence of the comparable box dimension on the Euler genus cannot be
subpolynomial (though the degree $\log_{2}81$ of the polynomial established in
Corollary 6 certainly can be improved). The dependence of the comparable box
dimension on the size of the forbidden minor that we established is not
explicit, as Theorem 2 is based on the structure theorem of Robertson and
Seymour [17]. It would be interesting to prove Theorem 1 without using the
structure theorem.

##  5 Fractional treewidth-fragility

Suppose $G$ is a connected planar graph and $v$ is a vertex of $G$. For an
integer $k\geq 2$, give each vertex at distance $d$ from $v$ the color $d\bmod
k$. Then deleting the vertices of any of the $k$ colors results in a graph of
treewidth at most $3k$. This fact (which follows from the result of Robertson
and Seymour [18] on treewidth of planar graphs of bounded radius) is (in the
modern terms) the basis of Baker’s technique [2] for design of approximation
algorithms. However, even quite simple graph classes (e.g., strong products of
three paths [3]) do not admit such a coloring (where the removal of any color
class results in a graph of bounded treewidth). However, a fractional version
of this coloring concept is still very useful in the design of approximation
algorithms [8] and applies to much more general graph classes, including all
graph classes with strongly sublinear separators and bounded maximum degree
[5].

We say that a class of graphs ${\cal G}$ is _fractionally treewidth-fragile_
if there exists a function $f$ such that for every graph $G\in{\cal G}$ and
integer $k\geq 2$, there exist sets $X_{1},\ldots,X_{m}\subseteq V(G)$ such
that each vertex belongs to at most $m/k$ of them and
$\operatorname{tw}(G-X_{i})\leq f(k)$ for every $i$ (equivalently, there
exists a probability distribution on the set $\\{X\subseteq
V(G):\operatorname{tw}(G-X)\leq f(k)\\}$ such that $\text{Pr}[v\in X]\leq 1/k$
for each $v\in V(G)$). For example, the class of planar graphs is
(fractionally) treewidth-fragile, since we can let $X_{i}$ consist of the
vertices of color $i-1$ in the coloring described at the beginning of the
section.

Before going further, let us recall some notions about treewidth. A _tree
decomposition_ of a graph $G$ is a pair $(T,\beta)$, where $T$ is a rooted
tree and $\beta:V(T)\to 2^{V(G)}$ assigns a _bag_ to each of its nodes, such
that

  * •

for each $uv\in E(G)$, there exists $x\in V(T)$ such that $u,v\in\beta(x)$,
and

  * •

for each $v\in V(G)$, the set $\\{x\in V(T):v\in\beta(x)\\}$ is non-empty and
induces a connected subtree of $T$.

For nodes $x,y\in V(T)$, we write $x\preceq y$ if $x=y$ or $x$ is a descendant
of $y$ in $T$. The _width_ of the tree decomposition is the maximum of the
sizes of the bags minus $1$. The _treewidth_ of a graph is the minimum of the
widths of its tree decompositions. Let us remark that the value of treewidth
obtained via this definition coincides with the one via $k$-trees which we
used in the previous section.

Our main result is that all graph classes of bounded comparable box dimension
are fractionally treewidth-fragile. We will show the result in a more general
setting, motivated by concepts from [6] and by applications to related
representations. The argument is motivated by the idea used in the
approximation algorithms for disk graphs by Erlebach et al. [10]. Before
introducing this more general setting, and as a warm-up, let us outline how to
prove that disk graphs of thickness $t$ are fractionally treewidth-fragile.
Consider first unit disk graphs. By partitionning the plane with a random grid
${\cal H}$, having squared cells of side-length $2k$, any unit disk has
probability $1/2k$ to intersect a vertical (resp. horizontal) line of the
grid. By union bound, any disk has probability at most $1/k$ to intersect the
grid. Considering this probability distribution, let us now show that removing
the disks intersected by the grid leads to a unit disk graph of bounded
treewidth. Indeed, in such a graph any connected component corresponds to unit
disks contained in the same cell of the grid. Such cell having area bounded by
$4k^{2}$, there are at most $16tk^{2}/\pi$ disks contained in a cell. The size
of the connected components being bounded, so is the treewidth. Note that this
distribution also works if we are given disks whose diameter lie in a certain
range. If any diameter $\delta$ is such that $1/c\leq\delta\leq 1$, then the
same process with a random grid of $2k\times 2k$ cells, ensures that any disk
is deleted with probability at most $1/k$, while now the connected components
have size at most $4tc^{2}k^{2}/\pi$. Dealing with arbitrary disk graphs (with
any diameter $\delta$ being in the range $0<\delta\leq 1$) requires to delete
more disks. This is why each $(2k\times 2k)$-cell is now partitionned in a
quadtree-like manner. Now a disk with diameter between $\ell/2$ and $\ell$
(with $\ell=1/2^{i}$ for some integer $i\geq 0$) is deleted if it is not
contained in a $(2k\ell\times 2k\ell)$-cell of a quadtree. It is not hard to
see that a disk is deleted with probability at most $1/k$. To prove that the
remaining graph has bounded treewidth one should consider the following tree
decomposition $(T,\beta)$. The tree $T$ is obtained by linking the roots of
the quadtrees we used (as trees) to a new common root. Then for a
$(2k\ell\times 2k\ell)$-cell $C$, $\beta(C)$ contains all the disks of
diameter at least $\ell/2$ intersecting $C$. To see that such bag is bounded
consider the $((2k+1)\ell\times(2k+1)\ell)$ square $C^{\prime}$ centered on
$C$, and note that any disk in $\beta(C)$ intersects $C^{\prime}$ on an area
at least $\pi\ell^{2}/16$. This implies that $|\beta(C)|\leq
16t(2k+1)^{2}/\pi$.

Let us now give a detailed proof in a more general setting. For a measurable
set $A\subseteq\mathbb{R}^{d}$, let $\operatorname{vol}(A)$ denote the
Lebesgue measure of $A$. For two measurable subsets $A$ and $B$ of
$\mathbb{R}^{d}$ and a positive integer $s$, we write $A\sqsubseteq_{s}B$ if
for every $x\in B$, there exists a translation $A^{\prime}$ of $A$ such that
$x\in A^{\prime}$ and $\operatorname{vol}(A^{\prime}\cap
B)\geq\tfrac{1}{s}\operatorname{vol}(A)$. Note that for two boxes $A$ and $B$,
we have $A\sqsubseteq_{1}B$ if and only if $A\sqsubseteq B$. An _$s$
-comparable envelope representation_ $(\iota,\omega)$ of a graph $G$ in
$\mathbb{R}^{d}$ consists of two functions $\iota,\omega:V(G)\to
2^{\mathbb{R}^{d}}$ such that for some ordering $v_{1}$, …, $v_{n}$ of
vertices of $G$,

  * •

for each $i$, $\omega(v_{i})$ is a box, $\iota(v_{i})$ is a measurable set,
and $\iota(v_{i})\subseteq\omega(v_{i})$,

  * •

if $i<j$, then $\omega(v_{j})\sqsubseteq_{s}\iota(v_{i})$, and

  * •

if $i<j$ and $v_{i}v_{j}\in E(G)$, then
$\omega(v_{j})\cap\iota(v_{i})\neq\emptyset$.

We say that the representation has _thickness at most $t$_ if for every point
$x\in\mathbb{R}^{d}$, there exist at most $t$ vertices $v\in V(G)$ such that
$x\in\iota(v)$.

For example:

  * •

If $f$ is a touching representation of $G$ by comparable boxes in
$\mathbb{R}^{d}$, then $(f,f)$ is a $1$-comparable envelope representation of
$G$ in $\mathbb{R}^{d}$ of thickness at most $2^{d}$.

  * •

If $f$ is a touching representation of $G$ by balls in $\mathbb{R}^{d}$ and
letting $\omega(v)$ be the smallest axis-aligned hypercube containing $f(v)$,
then there exists a positive integer $s_{d}$ depending only on $d$ such that
$(f,\omega)$ is an $s_{d}$-comparable envelope representation of $G$ in
$\mathbb{R}^{d}$ of thickness at most $2$.

######  Theorem 4.

For positive integers $t$, $s$, and $d$, the class of graphs with an
$s$-comparable envelope representation in $\mathbb{R}^{d}$ of thickness at
most $t$ is fractionally treewidth-fragile, with a function
$f(k)=O_{t,s,d}\bigl{(}k^{d}\bigr{)}$.

###### Proof.

For a positive integer $k$, let $f(k)=(2ksd+2)^{d}st$. Let $(\iota,\omega)$ be
an $s$-comparable envelope representation of a graph $G$ in $\mathbb{R}^{d}$
of thickness at most $t$, and let $v_{1}$, …, $v_{n}$ be the corresponding
ordering of the vertices of $G$. Let us define $\ell_{i,j}\in\mathbb{R}^{+}$
for $i=1,\ldots,n$ and $j\in\\{1,\ldots,d\\}$ as an approximation of
$ksd|\omega(v_{i})[j]|$ such that $\ell_{i-1,j}/\ell_{i,j}$ is a positive
integer. Formally it is defined as follows.

  * •

Let $\ell_{1,j}=ksd|\omega(v_{1})[j]|$.

  * •

For $i=2,\ldots,n$, let $\ell_{i,j}=\ell_{i-1,j}$, if
$\ell_{i-1,j}<ksd|\omega(v_{i})[j]|$, and otherwise let $\ell_{i,j}$ be lowest
fraction of $\ell_{i-1,j}$ that is greater than $ksd|\omega(v_{i})[j]|$,
formally $\ell_{i,j}=\min\\{\ell_{i-1,j}/b\ |\ b\in\mathbb{N}^{+}\text{ and
}\ell_{i-1,j}/b\geq ksd|\omega(v_{i})[j]|\\}$.

Let the real $x_{j}\in[0,\ell_{1,j}]$ be chosen uniformly at random, and let
${\cal H}^{i}_{j}$ be the set of hyperplanes in $\mathbb{R}^{d}$ consisting of
the points whose $j$-th coordinate is equal to $x_{j}+m\ell_{i,j}$ for some
$m\in\mathbb{Z}$. As $\ell_{i,j}$ is a multiple of $\ell_{i^{\prime},j}$
whenever $i\leq i^{\prime}$, we have that ${\cal H}^{i}_{j}\subseteq{\cal
H}^{i^{\prime}}_{j}$ whenever $i\leq i^{\prime}$. For $i\in\\{1,\ldots,n\\}$,
the _$i$ -grid_ is ${\cal H}^{i}=\bigcup_{j=1}^{d}{\cal H}^{i}_{j}$, and we
let the $0$-grid ${\cal H}^{0}=\emptyset$. Similarly as above we have that
${\cal H}^{i}\subseteq{\cal H}^{i^{\prime}}$ whenever $i\leq i^{\prime}$.

We let $X\subseteq V(G)$ consist of the vertices $v_{a}\in V(G)$ such that the
box $\omega(v_{a})$ intersects some hyperplane $H\in{\cal H}^{a}$, that is
such that $x_{j}+m\ell_{a,j}\in\omega(v_{a})[j]$, for some
$j\in\\{1,\ldots,d\\}$ and some $m\in\mathbb{Z}$. First, let us argue that
$\text{Pr}[v_{a}\in X]\leq 1/k$. Indeed, the set
$[0,\ell_{1,j}]\cap\bigcup_{m\in\mathbb{Z}}(\omega(v_{a})[j]-m\ell_{a,j})$ has
measure $\tfrac{\ell_{1,j}}{\ell_{a,j}}\cdot|\omega(v_{a})[j]|$, implying that
for fixed $j$, this happens with probability $|\omega(v_{a})[j]|/\ell_{a,j}$.
Let $a^{\prime}$ be the largest integer such that $a^{\prime}\leq a$ and
$\ell_{a^{\prime},j}<\ell_{a^{\prime}-1,j}$ if such an index exists, and
$a^{\prime}=1$ otherwise; note that $\ell_{a,j}=\ell_{a^{\prime},j}\geq
ksd|\omega(v_{a^{\prime}})[j]|$. Moreover, since
$\omega(v_{a})\sqsubseteq_{s}\iota(v_{a^{\prime}})\subseteq\omega(v_{a^{\prime}})$,
we have $\omega(v_{a})[j]\leq s\omega(v_{a^{\prime}})[j]$. Combining these
inequalities,

$\frac{|\omega(v_{a})[j]|}{\ell_{a,j}}\leq\frac{s\omega(v_{a^{\prime}})[j]}{ksd|\omega(v_{a^{\prime}})[j]|}=\frac{1}{kd}.$

By the union bound, we conclude that $\text{Pr}[v_{a}\in X]\leq 1/k$.

Let us now bound the treewidth of $G-X$. For $a\geq 0$, an _$a$ -cell_ is a
maximal connected subset of $\mathbb{R}^{d}\setminus\bigl{(}\bigcup_{H\in{\cal
H}^{a}}H\bigr{)}$. A set $C\subseteq\mathbb{R}^{d}$ is a _cell_ if it is an
$a$-cell for some $a\geq 0$. A cell $C$ is _non-empty_ if there exists $v\in
V(G-X)$ such that $\iota(v)\subseteq C$. Note that there exists a rooted tree
$T$ whose vertices are the non-empty cells and such that for $x,y\in V(T)$, we
have $x\preceq y$ if and only if $x\subseteq y$. For each non-empty cell $C$,
let us define $\beta(C)$ as the set of vertices $v_{i}\in V(G-X)$ such that
$\iota(v)\cap C\neq\emptyset$ and $C$ is an $a$-cell for some $a\geq i$.

Let us show that $(T,\beta)$ is a tree decomposition of $G-X$. For each
$v_{j}\in V(G-X)$, the $j$-grid is disjoint from $\omega(v_{j})$, and thus
$\iota(v_{j})\subseteq\omega(v_{j})\subset C$ for some $j$-cell $C\in V(T)$
and $v_{j}\in\beta(C)$. Consider now an edge $v_{i}v_{j}\in E(G-X)$, where
$i<j$. We have $\omega(v_{j})\cap\iota(v_{i})\neq\emptyset$, and thus
$\iota(v_{i})\cap C\neq\emptyset$ and $v_{i}\in\beta(C)$. Finally, suppose
that $v_{j}\in C^{\prime}$ for some $C^{\prime}\in V(T)$. Then $C^{\prime}$ is
an $a$-cell for some $a\geq j$, and since $\iota(v_{j})\cap
C^{\prime}\neq\emptyset$ and $\iota(v_{j})\subset C$, we conclude that
$C^{\prime}\subseteq C$, and consequently $C^{\prime}\preceq C$. Moreover, any
cell $C^{\prime\prime}$ such that $C^{\prime}\preceq C^{\prime\prime}\preceq
C$ (and thus $C^{\prime}\subseteq C^{\prime\prime}\subseteq C$) is an
$a^{\prime}$-cell for some $a^{\prime}\geq j$ and $\iota(v_{j})\cap
C^{\prime\prime}\supseteq\iota(v_{j})\cap C^{\prime}\neq\emptyset$, implying
$v_{j}\in\beta(C^{\prime\prime})$. It follows that
$\\{C^{\prime}:v_{j}\in\beta(C^{\prime})\\}$ induces a connected subtree of
$T$.

Finally, let us bound the width of the decomposition $(T,\beta)$. Let $C$ be a
non-empty cell and let $a$ be maximum such that $C$ is an $a$-cell. Then $C$
is an open box with sides of lengths $\ell_{a,1}$, …, $\ell_{a,d}$. Consider
$j\in\\{1,\ldots,d\\}$:

  * •

If $a=1$, then $\ell_{a,j}=ksd|\omega(v_{a})[j]|$.

  * •

If $a>1$ and $\ell_{a,j}=\ell_{a-1,j}$, then
$\ell_{a,j}=\ell_{a-1,j}<2ksd|\omega(v_{a})[j]|$ (otherwise
$\ell_{a,j}=\ell_{a-1,j}/b$ for some integer $b\geq 2$).

  * •

If $a>1$ and $\ell_{a,j}<\ell_{a-1,j}$, then $\ell_{a-1,j}\geq b\times
ksd|\omega(v_{a})[j]|$ for some integer $b\geq 2$. Now let $b$ be the greatest
such integer (that is such that $\ell_{a-1,j}<(b+1)\times
ksd|\omega(v_{a})[j]|$) and note that

$\ell_{a,j}=\frac{\ell_{a-1,j}}{b}<\tfrac{b+1}{b}ksd|\omega(v_{a})[j]|<\tfrac{3}{2}ksd|\omega(v_{a})[j]|.$

Hence, $\ell_{a,j}<2ksd|\omega(v_{a})[j]|$. Let $C^{\prime}$ be the box with
the same center as $C$ and with $|C^{\prime}[j]|=(2ksd+2)|\omega(v_{a})[j]|$.
For any $v_{i}\in\beta(C)\setminus\\{v_{a}\\}$, we have $i\leq a$ and
$\iota(v_{i})\cap C\neq\emptyset$, and since
$\omega(v_{a})\sqsubseteq_{s}\iota(v_{i})$, there exists a translation $B_{i}$
of $\omega(v_{a})$ that intersects $C\cap\iota(v_{i})$ and such that
$\operatorname{vol}(B_{i}\cap\iota(v_{i}))\geq\tfrac{1}{s}\operatorname{vol}(\omega(v_{a}))$.
Note that as $B_{i}$ intersects $C$, we have that $B_{i}\subseteq C^{\prime}$.
Since the representation has thickness at most $t$,

$\displaystyle\operatorname{vol}(C^{\prime})$
$\displaystyle\geq\operatorname{vol}\left(C^{\prime}\cap\bigcup_{v_{i}\in\beta(C)\setminus\\{v_{a}\\}}\iota(v_{i})\right)$
$\displaystyle\geq\operatorname{vol}\left(\bigcup_{v_{i}\in\beta(C)\setminus\\{v_{a}\\}}B_{i}\cap\iota(v_{i})\right)$
$\displaystyle\geq\frac{1}{t}\sum_{v_{i}\in\beta(C)\setminus\\{v_{a}\\}}\operatorname{vol}(B_{i}\cap\iota(v_{i}))$
$\displaystyle\geq\frac{\operatorname{vol}(\omega(v_{a}))(|\beta(C)|-1)}{st}.$

Since
$\operatorname{vol}(C^{\prime})=(2ksd+2)^{d}\operatorname{vol}(\omega(v_{a}))$,
it follows that

$|\beta(C)|-1\leq(2ksd+2)^{d}st=f(k),$

as required. ∎

The proof that (generalizations of) graphs with bounded comparable box
dimensions have sublinear separators in [6] is indirect; it is established
that these graphs have polynomial coloring numbers, which in turn implies they
have polynomial expansion, which then gives sublinear separators using the
algorithm of Plotkin, Rao, and Smith [16]. The existence of sublinear
separators is known to follow more directly from fractional treewidth-
fragility. Indeed, since $\text{Pr}[v\in X]\leq 1/k$, there exists $X\subseteq
V(G)$ such that $\operatorname{tw}(G-X)\leq f(k)$ and $|X|\leq|V(G)|/k$. The
graph $G-X$ has a balanced separator of size at most
$\operatorname{tw}(G-X)+1$, which combines with $X$ to a balanced separator of
size at most $V(G)|/k+f(k)+1$ in $G$. Optimizing the value of $k$ (choosing it
so that $V(G)|/k=f(k)$), we obtain the following corollary of Theorem 4.

######  Corollary 7.

For positive integers $t$, $s$, and $d$, every graph $G$ with an
$s$-comparable envelope representation in $\mathbb{R}^{d}$ of thickness at
most $t$ has a sublinear separator of size
$O_{t,s,d}\bigl{(}|V(G)|^{\tfrac{d}{d+1}}\bigr{)}.$

##  6 Acknowledgement

This research was carried out at the workshop on Geometric Graphs and
Hypergraphs organized by Yelena Yuditsky and Torsten Ueckerdt in September
2021. We would like to thank the organizers and all participants for creating
a friendly and productive environment.

## References

  * [1] Michael O Albertson, Glenn G Chappell, Hal A Kierstead, André Kündgen, and Radhika Ramamurthi.  Coloring with no $2$-colored $p\\_4$’s.  the electronic journal of combinatorics, pages R26–R26, 2004.
  * [2] B.S. Baker.  Approximation algorithms for NP-complete problems on planar graphs.  Journal of the ACM (JACM), 41(1):153–180, 1994.
  * [3] E. Berger, Z. Dvorák, and S. Norin.  Treewidth of grid subsets.  Combinatorica, 2017.
  * [4] V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood.  Planar graphs have bounded queue-number.  Journal of the ACM, 67:22, 2020.
  * [5] Z. Dvorák.  Sublinear separators, fragility and subexponential expansion.  European Journal of Combinatorics, 52:103–119, 2016.
  * [6] Z. Dvorák, R. McCarty, and S. Norin.  Sublinear separators in intersection graphs of convex shapes.  arXiv, 2001.01552, 2020.
  * [7] Zdenek Dvorák.  Approximation metatheorem for fractionally treewidth-fragile graphs.  arXiv, 2103.08698, 2021.
  * [8] Zdenek Dvorák and Abhiruk Lahiri.  Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs.  In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 40:1–40:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [9] Zdenek Dvorák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky.  Weak coloring numbers of intersection graphs.  arXiv, 2103.17094, 2021.
  * [10] Thomas Erlebach, Klaus Jansen, and Eike Seidel.  Polynomial-time approximation schemes for geometric intersection graphs.  SIAM Journal on Computing, 34:1302–1323, 2005.
  * [11] Stefan Felsner and Mathew C Francis.  Contact representations of planar graphs with cubes.  In Proceedings of the twenty-seventh annual symposium on Computational geometry, pages 315–320, 2011.
  * [12] Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos.  Coloring and covering nowhere dense graphs.  SIAM Journal on Discrete Mathematics, 32:2467–2481, 2018.
  * [13] P. Koebe.  Kontaktprobleme der Konformen Abbildung.  Math.-Phys. Kl., 88:141–164, 1936.
  * [14] L. Lovász.  Graphs and Geometry.  American Mathematical Society, Providence, 2019.
  * [15] J. Nesetril and P. Ossona de Mendez.  Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics.  Springer, 2012.
  * [16] Serge Plotkin, Satish Rao, and Warren D Smith.  Shallow excluded minors and improved graph decompositions.  In Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, pages 462–470. Society for Industrial and Applied Mathematics, 1994.
  * [17] N. Robertson and P. D. Seymour.  Graph Minors. XVI. Excluding a non-planar graph.  J. Combin. Theory, Ser. B, 89(1):43–76, 2003.
  * [18] Neil Robertson and Paul D. Seymour.  Graph Minors. III. Planar tree-width.  Journal of Combinatorial Theory, Series B, 36:49–64, 1984.
  * [19] Horst Sachs.  Coin graphs, polyhedra, and conformal mapping.  Discrete Mathematics, 134:133–138, 1994.