comparable-box-dimension.tex 41.1 KB
Newer Older
Zdenek Dvorak's avatar
Zdenek Dvorak committed
1
2
3
4
5
6
7
8
9
\documentclass[10pt]{article}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{colonequals}
\usepackage{epsfig}
\usepackage{url}
\newcommand{\GG}{{\cal G}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
10
\newcommand{\HH}{{\cal H}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
11
12
13
14
15
16
17
18
19
20
21
\newcommand{\CC}{{\cal C}}
\newcommand{\OO}{{\cal O}}
\newcommand{\PP}{{\cal P}}
\newcommand{\RR}{{\cal R}}

\newcommand{\eps}{\varepsilon}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\bb}[1]{\mathbb{#1}}
\newcommand{\brm}[1]{\operatorname{#1}}
\newcommand{\cbdim}{\brm{dim}_{cb}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
22
23
\newcommand{\tw}{\brm{tw}}
\newcommand{\vol}{\brm{vol}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
24
25
26
27
28
29
30
31
32
33
34
35
36
37
%%%%%


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{question}[theorem]{Question}

\title{On comparable box dimension}
\author{Zden\v{e}k Dvo\v{r}\'ak\thanks{Computer Science Institute, Charles University, Prague, Czech Republic. E-mail: {\tt rakdver@iuuk.mff.cuni.cz}.
Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.}\and
38
Daniel Gon\c{c}alves\thanks{...}\and 
Zdenek Dvorak's avatar
Zdenek Dvorak committed
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
Abhiruk Lahiri\thanks{...}\and
Jane Tan\thanks{...}\and
Torsten Ueckerdt\thanks{Karlsruhe Institute of Technology.  E-mail: {\tt torsten.ueckerdt@kit.edu}}}
\date{}

\begin{document}
\maketitle

\begin{abstract}
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 boxes in $\mathbb{R}^d$ (two boxes are comparable if one of them is
a subset of a translation of the other one).  We show that proper minor-closed classes have bounded
comparable box dimension and explore further properties of this notion.
\end{abstract}

\section{Introduction}

For a system $\OO$ of subsets of $\mathbb{R}^d$, we say that a graph $G$ is a \emph{touching graph of objects from $\OO$}
57
if there exists a function $f:V(G)\to \OO$ (called a \emph{touching representation by objects from $\OO$})
Zdenek Dvorak's avatar
Zdenek Dvorak committed
58
59
60
such that for distinct $u,v\in V(G)$, the interiors of $f(u)$ and $f(v)$ are disjoint
and $f(u)\cap f(v)\neq\emptyset$ if and only if $uv\in E(G)$.
Famously, Koebe~\cite{koebe} proved that a graph is planar if and only if it is a touching graph of balls in $\mathbb{R}^2$.
61
This result motivated a number of strengthenings and variations~\cite{...}; most relevantly for us, every planar graph is
Zdenek Dvorak's avatar
Zdenek Dvorak committed
62
63
64
65
66
67
a touching graph of cubes in $\mathbb{R}^3$~\cite{felsner2011contact}.

An attractive feature of touching representation is that it makes it possible to represent graph classes that are sparse
(e.g., planar graphs, or more generally, graph classes with bounded expansion theory~\cite{nesbook}),
whereas in a general intersection representation, the represented class always includes arbitrarily large cliques.
Of course, whether the class of touching graph of objects from $\OO$ is sparse or not depends on the system $\OO$.
68
For example, all complete bipartite graphs $K_{n,m}$ are touching graphs of axis-aligned boxes in $\mathbb{R}^3$, where the vertices in
Zdenek Dvorak's avatar
Zdenek Dvorak committed
69
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$
70
boxes (a \emph{box} is the Cartesian product of intervals of non-zero length).
Zdenek Dvorak's avatar
Zdenek Dvorak committed
71
Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} noticed that this issue disappears if we forbid such a combination of
72
73
long and wide boxes: For two boxes $B_1$ and $B_2$, we write $B_1 \sqsubseteq B_2$ if a translation of $B_1$ is a subset of $B_2$.
We say that $B_1$ and $B_2$ are \emph{comparable} if $B_1\sqsubseteq B_2$ or $B_2\sqsubseteq B_1$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
74
75
76
77
78
79
80
81
82
83
84
85
A \emph{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.  For a graph $G$, let the \emph{comparable box dimension} $\cbdim(G)$
of $G$ be the smallest integer $d$ such that $G$ has a touching representation by comparable boxes in $\mathbb{R}^d$.
For a class $\GG$ of graphs, let $\cbdim(\GG)=\sup\{\cbdim(G):G\in\GG\}$; note that $\cbdim(\GG)=\infty$ if the
comparable box dimension of graphs in $\GG$ is not bounded.

Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} proved some basic properties of this notion.  In particular,
they proved that if a class $\GG$ has finite comparable box dimension, then it has polynomial strong coloring
numbers, which implies that $\GG$ has strongly sublinear separators.  They also provided an example showing
that for any function $h$, the class of graphs with strong coloring numbers bounded by $h$ has infinite
comparable box dimension.  Dvo\v{r}\'ak et al.~\cite{wcolig}
proved that graphs of comparable box dimension $3$ have exponential weak coloring number, giving the
86
first natural graph class with polynomial strong coloring numbers and superpolynomial weak coloring numbers
Zdenek Dvorak's avatar
Zdenek Dvorak committed
87
88
89
90
91
92
93
94
95
96
97
(the previous example is obtained by subdividing edges of every graph suitably many times~\cite{covcol}).

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~\cite{DJM+}, this implies
the main result of this paper.

\begin{theorem}\label{thm-minor}
The comparable box dimension of every proper minor-closed class of graphs is finite.
\end{theorem}

Additionally, we show that classes of graphs with finite comparable box dimension are fractionally treewidth-fragile.
98
This gives arbitrarily precise approximation algorithms for all monotone maximization problems that are
Zdenek Dvorak's avatar
Zdenek Dvorak committed
99
100
101
102
103
expressible in terms of distances between the solution vertices and tractable on graphs of bounded treewidth~\cite{distapx}
or expressible in the first-order logic~\cite{logapx}.

\section{Operations}

104
Let us start with a simple lemma saying that the addition of a vertex increases the comparable box dimension by at most one.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
105
In particular, this implies that $\cbdim(G)\le |V(G)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
106
107
108
109
\begin{lemma}\label{lemma-apex}
For any graph $G$ and $v\in V(G)$, we have $\cbdim(G)\le \cbdim(G-v)+1$.
\end{lemma}
\begin{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
110
Let $f$ be a touching representation of $G-v$ by comparable boxes in $\mathbb{R}^d$, where $d=\cbdim(G-v)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
111
112
113
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\}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
114
Then $h$ is a touching representation of $G$ by comparable boxes in $\mathbb{R}^{d+1}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
115
116
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
117
We need a bound on the clique number in terms of the comparable box dimension.
118
For a box $B=I_1\times \cdots \times I_d$ and $i\in\{1,\ldots,d\}$, let $B[i]=I_i$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
119
120
121
122
\begin{lemma}\label{lemma-cliq}
If $G$ has a touching representation $f$ by comparable boxes in $\mathbb{R}^d$, then $\omega(G)\le 2^d$.
\end{lemma}
\begin{proof}
123
124
125
126
 For any clique $A = \{a_1,\ldots,a_w\}$ in $G$, the corresponding boxes $f(a_1),\ldots,f(a_w)$ have pairwise non-empty intersection.
 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$.
 Since $f$ is a touching representation, $f(a_1),\ldots,f(a_d)$ have pairwise disjoint interiors and hence $w \leq 2^d$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
127
\end{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
128

Zdenek Dvorak's avatar
Zdenek Dvorak committed
129
130
A \emph{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 \emph{bag} to each of its nodes,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
131
132
such that
\begin{itemize}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
133
134
\item for each $uv\in E(G)$, there exists $x\in V(T)$ such that $u,v\in\beta(x)$, and
\item 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$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
135
\end{itemize}
136
For nodes $x,y\in V(T)$, we write $x\preceq y$ if $x=y$ or $x$ is a descendant of $y$ in $T$.
137
For each vertex $v\in V(G)$, let $p(v)$ be the node $x\in V(T)$ such that $v\in \beta(x)$ and $x$ is nearest to the root of $T$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
138
139
The \emph{adhesion} of the tree decomposition is the maximum of $|\beta(x)\cap\beta(y)|$ over distinct $x,y\in V(T)$,
and its \emph{width} is the maximum of the sizes of the bags minus $1$.  The \emph{treewidth} of a graph is the minimum
140
141
of the widths of its tree decompositions.  We will need to know that graphs of bounded treewidth have bounded comparable box dimension.
In fact, we will prove the following stronger fact (TODO: Was this published somewhere before? I am only aware of the upper bound of $t+2$ on the boxicity of $G$~\cite{box-treewidth}.)
Zdenek Dvorak's avatar
Zdenek Dvorak committed
142
143
144

\begin{lemma}\label{lemma-tw}
Let $(T,\beta)$ be a tree decomposition of a graph $G$ of width $t$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
145
146
Then $G$ has a touching representation $h$ by axis-aligned hypercubes in $R^{t+1}$ such that
for $u,v\in V(G)$, if $p(u)\prec p(v)$, then $h(u)\sqsubset h(v)$.
147
Moreover, the representation can be chosen so that no two hypercubes have the same size.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
148
149
\end{lemma}
\begin{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
Without loss of generality, we can assume that the root has a bag of size one
and that for each $x\in V(T)$ with parent $y$, we have $|\beta(x)\setminus\beta(y)|=1$
(if $\beta(x)\subseteq \beta(y)$, we can contract the edge $xy$; if $|\beta(x)\setminus\beta(y)|>1$,
we can subdivide the edge $xy$, introducing $|\beta(x)\setminus\beta(y)|-1$ new vertices,
and set their bags appropriately).  It is now natural to relabel the vertices of $G$
so that $V(G)=V(T)$, by giving the unique vertex in $\beta(x)\setminus\beta(y)$
the label $x$.  In particular, $p(x)=x$.  Furthermore, we can assume that $y\in\beta(x)$.
Otherwise, if $y$ is not the root of $T$, we can replace the edge $xy$ by the edge from $x$
to the parent of $y$.  If $y$ is the root of $T$, then the subtree rooted in $x$ induces a
union of connected components in $G$, and we can process this subtree separately from the
rest of the graph (being careful to only use hypercubes smaller than the one representing $y$
and of different sizes from those used on the rest of the graph).

Let us now greedily color $G$ by giving $x$ a color different from the colors of
all other vertices in $\beta(x)$; such a coloring $\varphi$ uses only colors
$\{1,\ldots,t+1\}$.

Let $D=4\Delta(T)+1$.  Let $V(G)=V(T)=\{x_1,x_2,\ldots, x_n\}$, where
for every $i<j$, $x_i$ and $x_j$ are either incomparable in $\prec$ or
$x_j\prec x_i)$; in particular, $x_1$ is the root of $T$.  Let $\varepsilon=D^{-n-1}$.
Let $s_i=D^{-i}$; we will represent $x_i$ by a hypercube $h(x_i)$ with edges of length $s_i$.
Additionally, we will need to consider larger hypercubes around $h(x_i)$; let $h'(x_i)$
be the hypercube with sides of length $2s_i$ and with $\min(h'(x_i)[j])=\min(h(x_i)[j])$
for $j\in\{1,\ldots, t+1\}$, and $h''(x_i)$ the hypercube with sides of length $2s_i+\epsilon$
and with $\min(h''(x_i)[j])=\min(h(x_i)[j])-\varepsilon$.  We will construct the representation $h$ so that the following
invariant is satisfied:
\begin{itemize}
\item[(a)] For each $x,z\in V(T)$ such that $x\prec z$, we have $h'(x)\subset h''(z)$.
\item[(b)] For each $y\in V(T)$ and distinct children $x$ and $z$ of $y$, we have $h''(x)\cap h''(z)=\emptyset$.
\end{itemize}
Note that this ensures that if $x$ and $z$ are vertices of $T$ and $h(x)\cap h(z)\neq\emptyset$, then $x\prec z$ or $z\prec x$.

We now construct the representation $h$.  For the root $x_1$ of $T$, $h(r)$ is an arbitrary hypercube with sides
of length $s_1$.  Assuming now we have already selected $h(y)$ for a vertex $y\in V(T)$, the hypercube $h(x_i)$ with sides of length $s_i$
for a child $x_i$ of $y$ is chosen as follows. For $j\in\{1,\ldots, t+1\}$,
\begin{itemize}
\item[(i)] if $j=\varphi(w)$ for $w\in\beta(x_i)\setminus\{x_i\}$, we choose $h(x_i)[j]$ so that
$\min(h(x_i)[j])=\max(h(w)[j])$ if $xw\in E(G)$ and so that $\min(h(x_i)[j])=\max(h(w)[j]) + \varepsilon$ otherwise.
\item[(ii)] if $j$ is different from the colors of all vertices in $\beta(x_i)\setminus\{x_i\}$,
then we choose $h(x_i)[j]$ so that $h''(x_i)[j]$ is a subset of the interior of $h(y)[j]$.  The interval $h''(x_i)[[j]$
is furthermore chosen to be disjoint from $h''(x_m)[j]$ for any other child $x_m$ of $y$;
this is always possible by the choice of $D$, $s_i$, and $s_m$.
\end{itemize}
Note that (ii) always applies for $j=\varphi(x_i)$ and this ensures that the invariant (b) holds.
For the invariant (a), note that in the case (ii), we ensure $h''(x_i)[[j]\subseteq h(y)[j]$ and
we have $h(y)[j]\subseteq h''(z)[j]$ by the invariant (a) for $y$ and $z$.  In the case (i),
if $z\prec w$, then we have $w\in\beta(z)\setminus\{z\}$ and
$\min(h(x_i)[j]),\min(h(z)[j])\in\{\max(h(w)[j]),\max(h(w)[j])+\varepsilon\}$.
If $w\preceq z$, then note we choose $h'(x_i)[j]\subseteq h'(w)[j]$ by (i) and that
we have $h'(w)[j]\subset h''(z)[j]$ by (a).  This verifies that the invariant (a)
also holds at $x_i$.

Consider now two adjacent vertices of $G$, say $x_i$ and $w$.  Note that any two
adjacent vertices are comparable in $\prec$, and thus we can assume $x_i\prec w$
and $w\in\beta(x_i)$.
By (i), for $j=\varphi(w)$, the intervals $h(x_i)[j]$ and $h(w)[j]$
intersect in a single point.  If $j\neq \varphi(w)$, then let $w_1$ be the child of $w$ on the path in $T$ from
$w$ to $x_i$.  If no vertex in $\beta(w_1)\setminus\{w_1\}$ has color $j$, then by (ii), we have $h''(w_1)[j]\subset h(w)[j]$,
Otherwise, $z\in \beta(w_1)\setminus\{w_1\}$ such that $\varphi(z)=j$; clearly, $w\prec z$ and $z\in\beta(w)\setminus\{w\}$.
We have $\min(h(w_1)[j]),\min(h(w)[j])\in\{\max(h(z)[j]),\max(h(z)[j])+\varepsilon\}$ by (i).
Hence, $\min(h(w)[j])-2\epsilon\le \min(h''(w_1)[j])\le \max(h''(w_1)[j])\le \max(h(w)[j])$.
Since $h(x_i)[j]\subseteq h''(w_1)[j]$ by (a) and the length of the interval $h(x_i)[j]$ is greater than $2\varepsilon$,
we conclude that $h(x_i)[j]\cap h(w)[j]\neq\emptyset$.  Therefore, the boxes $h(w)$ and $h(x_i)$ touch.

Consider now two non-adjacent vertices of $G$, say $x_i$ and $w$.  As we noted before, if $x_i$ and $w$ are
incomparable in $\prec$, then (a) and (b) implies that the boxes $h(x_i)$ and $h(w)$ are disjoint.
Suppose now that say $x_i\prec w$, and let $j=\varphi(w)$.  If $w\in\beta(x_i)$, then $h(x_i)[j]$ and $h(w)[j]$ are disjoint by (i).
Otherwise, let $y$ be the last vertex on the path from $w$ to $x_i$ in $T$ such that $w\in\beta(y)$ and let $z$ be the child of $y$
on this path.  As we argued in the first paragraph, $y\neq w$, and by (i), the interior of $h(y)[j]$ is disjoint from $h(w)[j]$.
By (ii), $h''(z)[j]$ is contained in the interior of $h(y)[j]$.  By (a), we conclude that $h(x_i)[j]\subseteq h''(z)[j]$,
implying that the boxes $h(x_i)$ and $h(w)$ are disjoint.  Therefore, $h$ is a touching representation of $G$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
221
222
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
223
224
225
Next, let us deal with clique-sums.  A \emph{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.  The main issue to overcome in obtaining a representation for a clique-sum
226
227
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
Zdenek Dvorak's avatar
Zdenek Dvorak committed
228
in a single corner.  This can be avoided by increasing the dimension, but we need to be careful so that the dimension stays bounded
229
even after an arbitrary number of clique-sums.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
230
231

It will be convenient to work in the setting of tree decompositions.
232
Consider a tree decomposition $(T,\beta)$ of a graph $G$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
233
234
235
236
237
238
239
240
241
For each $x\in V(T)$, the \emph{torso} $G_x$ of $x$ is the graph obtained from $G[\beta(x)]$ by adding a clique on $\beta(x)\cap\beta(y)$
for each $y\in V(T)$.  For a class of graphs $\GG$, we say that the tree decomposition is \emph{over $\GG$} if all the torsos belong to $\GG$.
We use the following well-known fact.
\begin{observation}
A graph $G$ is obtained from graphs in a class $\GG$ by repeated clique-sums if and only if $G$ has a tree decomposition over $\GG$.
\end{observation}
For each note $x\in V(T)$, let $\pi(x)=\{x\}\cup \{p(v):v\in\beta(x)\}$.  Let $T_\beta$ be the graph with vertex set $V(T)$ such that
$xy\in E(T_\beta)$ if and only if $x\in\pi(y)$ or $y\in\pi(x)$.
\begin{lemma}\label{lemma-legraf}
242
If $(T,\beta)$ is a tree decomposition of $G$ of adhesion $a$, then $(T,\pi)$ is a tree decomposition of $T_\beta$ of width at most $a$.
243
Moreover, $\pi(x)$ is a clique in $T_\beta$ and $p(x)=x$ for each $x\in V(T)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
244
245
\end{lemma}
\begin{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
246
247
248
249
250
251
252
253
254
255
256
For each edge $xy\in E(T_\beta)$, we have $x,y\in \pi(x)$ or $x,y\in \pi(y)$ by definition.
Moreover, for each $x\in V(T_\beta)$, we have
$$\{y:x\in\pi(y)\}=\{x\}\cup \bigcup_{v\in V(G):p(v)=x} \{y:v\in\beta(y)\},$$
and all the sets on the right-hand size induce connected subtrees containing $x$,
implying that $\{y:x\in\pi(y)\}$ also induces a connected subtree containing $x$.
Hence, $(T,\pi)$ is a tree decomposition of $T_\beta$.

Consider a node $x\in V(T)$.  Note that for each $v\in \beta(x)$, the vertex $p(v)$ is an ancestor of $x$ in $T$.
In particular, if $x$ is the root of $T$, then $\pi(x)=\{x\}$.  Otherwise, if $y$ is the parent of $x$ in $T$, then
$p(v)=x$ for every $v\in \beta(x)\setminus\beta(y)$, and thus $|\pi(x)|\le |\beta(x)\cap \beta(y)|+1\le a+1$.
Hence, the width of $(T,\pi)$ is at most $a$.
257
258
259
260
261
262
263

Suppose now that $y$ and $z$ are distinct vertices in $\pi(x)$.  Then both $y$ and $z$ are ancestors of $x$ in $T$,
and thus without loss of generality, we can assume that $y\preceq z$.  If $y=x$, then $yz\in E(T_\beta)$ by definition.
Otherwise, there exist vertices $u,v\in \beta(x)$ such that $p(u)=y$ and $p(v)=z$.  Since $v\in \beta(x)\cap\beta(z)$
and $y$ is on the path in $T$ from $x$ to $z$, we also have $v\in\beta(y)$.  This implies $z\in\pi(y)$ and $yz\in E(T_\beta)$.
Hence, $\pi(x)$ is a clique in $T_\beta$.  Moreover, note that $x\not\in \pi(w)$ for any ancestor $w\neq x$ of $x$ in $T$,
and thus $p(x)=x$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
264
265
266
267
\end{proof}

We are now ready to deal with the clique-sums.

Zdenek Dvorak's avatar
Zdenek Dvorak committed
268
\begin{theorem}\label{thm-cs}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
269
270
271
272
273
274
If $G$ is obtained from graphs in a class $\GG$ by clique-sums, then there exists a graph $G'$ such that
$G\subseteq G'$ and $\cbdim(G')\le (\cbdim(\GG)+1)(\omega(\GG)+1)$.
\end{theorem}
\begin{proof}
Let $(T,\beta)$ be a tree decomposition of $G$ over $\GG$; the adhesion $a$ of $(T,\beta)$ is at most $\omega(\GG)$.
By Lemma~\ref{lemma-legraf}, $(T,\pi)$ is a tree decomposition of $T_\beta$ of width at most $a$. By Lemma~\ref{lemma-tw},
Zdenek Dvorak's avatar
Zdenek Dvorak committed
275
$T_\beta$ has a touching representation $h$ by axis-aligned hypercubes in $\mathbb{R}^{a+1}$ such that
276
$h(x)\sqsubseteq h(y)$ whenever $x\preceq y$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
277
Since $T_\beta$ has treewidth at most $a$, it has a proper coloring $\varphi$ by colors $\{0,\ldots,a\}$.
278
279
For every $x\in V(T)$, let $f_x$ be a touching representation of the torso $G_x$ of $x$ by comparable boxes in $\mathbb{R}^d$,
where $d=\cbdim(\GG)$.  We scale and translate the representations so that for every $x\in V(T)$ and $i\in\{0,\ldots,a\}$,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
280
281
there exists a box $E_i(x)$ such that
\begin{itemize}
282
283
284
285
286
\item[(a)] for distinct $x,y\in V(T)$, if $h(x)\sqsubset h(y)$, then $E_i(x) \sqsubset E_i(y)$ and $E_i(x) \sqsubset f_y(v)$ for every $v\in \beta(y)$,
\item[(b)] if $x\prec y$, then $E_i(x)\subseteq E_i(y)$,
\item[(c)] if $i=\varphi(x)$, then $f_x(v)\subseteq E_i(x)$ for every $v\in\beta(x)$, and
\item[(d)] if $i\neq \varphi(x)$ and $K=\{v\in\beta(x):\varphi(p(v))=i\}$ is non-empty, then letting $y=p(v)$ for $v\in K$,
the box $E_i(x)$ contains a point belonging to $\bigcap_{v\in K} f_y(v)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
287
\end{itemize}
288
289
290
291
292
293
Some explanation is in order for the last point:  Firstly, since $\pi(x)$ is a clique in $T_\beta$, there
exists only one vertex $y\in \pi(x)$ of color $i$, and thus $y=p(v)$ for all $v\in K$.
Moreover, $K$ is a clique in $G_y$, and thus $\bigcap_{v\in K} f_y(v)$ is non-empty.  Lastly,
note that if $x\prec z\prec y$, then $K=\beta(x)\cap\beta(y)\subseteq \beta(z)\cap \beta(y)$,
and thus $E_i(z)$ was also chosen to contain a point of $\bigcap_{v\in K} f_y(v)$;
hence, a choice of $E_i(x)$ satisfying $E_i(x)\subseteq E_i(z)$ as required by (b) is possible.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
294
295
296
297
298

Let us now define $f(v)=h(p(v))\times E_0(v)\times \cdots\times E_a(v)$ for each $v\in V(G)$,
where $E_i(v)=f_{p(v)}(v)$ if $i=\varphi(p(v))$ and $E_i(v)=E_i(p(v))$ otherwise.  We claim this gives a touching representation
of a supergraph of $G$ by comparable boxes in $\mathbb{R}^{(d+1)(a+1)}$.  First, note that the boxes are indeed comparable;
if $p(u)=p(v)$, then this is the case since $f_{p(v)}$ is a representation by comparable boxes, and if say
299
$p(u)\prec p(v)$, then this is due to (a) and (c).  Next, let us argue $f(u)$ and $f(v)$ have disjoint
Zdenek Dvorak's avatar
Zdenek Dvorak committed
300
301
302
interiors.  If $p(u)=p(v)$, this is the case since $f_{p(v)}$ is a touching representation, and if $p(u)\neq p(v)$,
then this is the case because $h$ is a touching representation.  Finally, suppose that $uv\in E(G)$.  Let $x$
be the node of $T$ nearest to the root such that $u,v\in \beta(x)$.  Without loss of generality, $p(u)=x$.
303
Let $y=p(v)$.  If $x=y$, then $f(u)\cap f(v)\neq\emptyset$, since $f_x$ is a touching representation of $G_x$ and $uv\in E(G_x)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
304
If $x\neq y$, then $y\in\pi(x)$ and $xy\in E(T_\beta)$, implying that $h(x)\cap h(y)\neq\emptyset$.
305
306
307
Moreover, $x\prec y$, implying that $E_i(u)\cap E_i(v)\neq\emptyset$ for $i=0,\ldots,a$ by (b) if $\varphi(x)\neq i\neq \varphi(y)$,
(b) and (c) if $\varphi(x)=i\neq\varphi(y)$, and (d) if $\varphi(x)\neq i=\varphi(y)$ (we cannot have $\varphi(x)=i=\varphi(y)$, since
$xy\in E(T_\beta)$.  Hence, again we have $f(u)\cap f(v)\neq\emptyset$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
308
309
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
We can now combine Theorem~\ref{thm-cs} with Lemma~\ref{lemma-cliq}.
\begin{corollary}\label{cor-cs}
If $G$ is obtained from graphs in a class $\GG$ by clique-sums, then there exists a graph $G'$ such that
$G\subseteq G'$ and $\cbdim(G')\le (\cbdim(\GG)+1)\bigl(2^{\cbdim(\GG)}+1\bigr)\le 6^{\cbdim(\GG)}$.
\end{corollary}

Note that only bound the comparable box dimension of a supergraph
of $G$.  To deal with this issue, 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~\cite{subconvex}, but since the setting is somewhat
different and the construction of~\cite{subconvex} uses rotated boxes,
we provide details of the argument.

A \emph{star coloring} of a graph $G$ is a proper coloring such that any two color classes induce
a star forest (i.e., a graph not containing any 4-vertex path).  The \emph{star chromatic number} $\chi_s(G)$
of $G$ is the minimum number of colors in a star coloring of $G$.
We will need the fact that the star chromatic number is at most exponential in the comparable box dimension;
this follows from~\cite{subconvex} and we include the argument to make the dependence clear.
\begin{lemma}\label{lemma-chrom}
If $G$ has a comparable box representation $f$ in $\mathbb{R}^d$, then $G$ has star chromatic number at most $2\cdot 9^d$.
\end{lemma}
\begin{proof}
Let $v_1$, \ldots, $v_n$ be the vertices of $G$ ordered non-increasingly by the size of the boxes that represent them;
i.e., so that $f(v_i)\sqsubseteq f(v_j)$ whenever $i>j$.  We greedily color the vertices in order, giving $v_i$ the smallest
color different from the colors of all vertices $v_j$ such that $j<i$ and either $v_jv_i\in E(G)$, or there exists $m>j$
such that $v_jv_m,v_mv_i\in E(G)$.  Note this gives a star coloring: A path on four vertices always contains a 3-vertex subpath
$v_{i_1}v_{i_2}v_{i_3}$ such that $i_1<i_2,i_3$, and in such a path, the coloring procedure gives each vertex a distinct color.

Hence, it remains to bound the number of colors we used.  Let us fix some $i$, and let us first bound the number of vertices
$v_j$ such that $j<i$ and there exists $m>i$ such that $v_jv_m,v_mv_i\in E(G)$.  Let $B$ be the box that is five times larger than $f(v)$
and has the same center as $f(v)$.  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$.  The boxes $B_j$ for different $j$ have disjoint interiors and their interiors are also disjoint from
$f(v_i)\subset B$, and thus the number of such indices $j$ is at most $\vol(B_j)/\vol(f(v_i))-1=5^d-1$.
A similar argument shows that the number of indices $m$ such that $m<i$ and $v_mv_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_jv_m,v_mv_i\in E(G)$
is at most $(3^d-1)^2$.

Consequently, 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<5^d+9^d<2\cdot 9^d$$
vertices.
\end{proof}

Next, let us show a bound on the comparable box dimension of subgraphs.

\begin{lemma}\label{lemma-subg}
If $G$ is a subgraph of a graph $G'$, then $\cbdim(G)\le \cbdim(G')+\chi^2_s(G')$.
\end{lemma}
\begin{proof}
As we can remove the boxes that represent the vertices, we can assume $V(G')=V(G)$.
Let $f$ be a touching representation by comparable boxes in $\mathbb{R}^d$, where $d=\cbdim(G')$.  Let $\varphi$
be a star coloring of $G'$ using colors $\{1,\ldots,c\}$, where $c=\chi_s(G')$.

For any distinct colors $i,j\in\{1,\ldots,c\}$, let $A_{i,j}\subseteq V(G)$ consist of vertices $u$ of color $i$
such that there exists a vertex $v$ of color $j$ such that $uv\in E(G')$ and $uv\not\in E(G)$.
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}]=[1/3,4/3]$ for $v\in A_{i,j}$, $h(v)[d_{i,j}]=[-4/3,-1/3]$ for $v\in A_{j,i}$,
and $h(v)[d_{i,j}](v)=[-1/2,1/2]$ otherwise.  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$.  The boxes $f(u)$ and $f(v)$ touch.
We cannot have $u\in A_{i,j}$ and $v\in A_{j,u}$, as then $G'$ would contain a 4-vertex path in colors $i$ and $j$.
Hence, in any added dimension $d'$, at least one of $h(u)$ and $h(v)$ is represented by the interval $[-1/2,1/2]$,
and thus $h(u)[d']\cap h(v)[d']\neq\emptyset$.  Therefore, the boxes $h(u)$ and $h(v)$ touch.

Suppose now that $uv\not\in E(G)$.  If $uv\not\in E(G')$, 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')$, $\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}\le d+c^2$.
\end{proof}

Let us now combine Lemmas~\ref{lemma-chrom} and \ref{lemma-subg}.

\begin{corollary}\label{cor-subg}
If $G$ is a subgraph of a graph $G'$, then $\cbdim(G)\le \cbdim(G')+4\cdot 81^{\cbdim(G')}\le 5\cdot 81^{\cbdim(G')}$.
\end{corollary}

Let us remark that an exponential increase in the dimension is unavoidable: We have $\cbdim{K_{2^d}}=d$,
but the graph obtained from $K_{2^d}$ by deleting a perfect matching has comparable box dimension $2^{d-1}$.
Corollaries~\ref{cor-cs} and~\ref{cor-subg} now give the main result of this section.
391

Zdenek Dvorak's avatar
Zdenek Dvorak committed
392
393
394
395
\begin{corollary}\label{cor-comb}
If $G$ is obtained from graphs in a class $\GG$ by clique-sums, then 
$\cbdim(G)\le 5\cdot 81^{6^{\cbdim(\GG)}}$.
\end{corollary}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
396

Zdenek Dvorak's avatar
Zdenek Dvorak committed
397
\section{The product structure and minor-closed classes}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
398

Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
Let $G\boxtimes H$ denote the \emph{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
either $u_1=u_2$ or $u_1u_2\in E(G)$ and either $v_1=v_2$ or $v_1v_2\in E(G)$.
Dujmovi{\'c} et al.~\cite{DJM+} proved the following result.
\begin{theorem}\label{thm-prod}
Any graph $G$ is a subgraph of the strong product of a path, a graph of threewidth at most $t$, and $K_m$, where
\begin{itemize}
\item $t=3$ and $m=3$ if $G$ is planar, and
\item $t=4$ and $m=\max(2g,3)$ if $G$ has Euler genus at most $g$.
\end{itemize}
Moreover, for every $k$, there exists $t$ such that if $K_k\not\preceq_m G$, then $G$ is a subgraph of a clique-sum
for graphs that can be obtained from the strong product of a path and a graph of treewidth at most $t$ by adding
at most $t$ apex vertices.
\end{theorem}

The connection to the comparable box dimension comes from the following observation.
\begin{lemma}\label{lemma-ps}
The strong product of a path $P$, a graph $T$ of treewidth at most $t$, and $K_m$ has
comparable box dimension at most $t+2+\lceil \log_2 m\rceil$.
\end{lemma}
\begin{proof}
Without loss of generality, we can assume that $k=\log_2 m$ is an integer and the
vertices of $K_m$ are elements of $\{0,1\}^k$.  Moreover, we can assume that $V(P)=\{1,\ldots,n\}$
with $ij\in E(P)$ iff $|i-j|=1$.  Let $h$ be the touching representation of $T$ by
hypercubes in $\mathbb{R}^{t+1}$ obtained by Lemma~\ref{lemma-tw}.

The representation $f$ of $P\boxtimes T\boxtimes K_m$ in $\mathbb{R}^{t+2+k}$
is obtained as follows: For $p\in V(P)$, $v\in V(T)$, and $(x_1,\ldots, x_k)\in V(K_m)$,
we set
$$f(p,v,x_1, \ldots, x_k)[j]=\begin{cases}
f(v)[j]&\text{ for $j=1,\ldots, t+1$}\\
[p,p+1]&\text{ if $j=t+2$}\\
[x_{j-t-2},x_{j-t-2}+1]&\text{ if $j>t+2$.}
\end{cases}$$
Clearly, this is a touching representation by comparable boxes.
\end{proof}

Combining Theorem~\ref{thm-prod}, Lemma~\ref{lemma-ps}, and the results of the previous section,
we obtain the following corollary, which in particular implies Theorem~\ref{thm-minor}.

\begin{corollary}\label{cor-minor}
For every graph $G$ of Euler genus $g$, there exists a supergraph $G'$ of $G$ such that
$\cbdim(G')\le 6+\lceil \log_2 \max(2g,3)\rceil$.  Consequently,
$$\cbdim(G)\le 5\cdot 81^7 \cdot (2g+3)^{\log_2 81}.$$
Moreover, for every $k$ there exists $d$ such that if $K_k\not\preceq_m(G)$, then
$\cbdim(G)\le d$.
\end{corollary}
Note that the graph obtained from $K_{2n}$ by deleting a perfect matching has Euler genus $\Theta(n^2)$
and comparable box dimension $n$, showing that the dependence of the comparable box dimension cannot be
subpolynomial (though the degree $\log_2 81$ of the polynomial established in Corollary~\ref{cor-minor}
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~\ref{thm-prod} is based on the structure theorem of Robertson and Seymour~\cite{robertson2003graph}.
It would be interesting to prove this part of Corollary~\ref{cor-minor} without using the structure theorem.

Zdenek Dvorak's avatar
Zdenek Dvorak committed
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
\section{Fractional treewidth-fragility}

Suppose $G$ is a connected planar graph and $v$ is a vertex of $G$.  For an integer $k\ge 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~\cite{rs3}
on treewidth of planar graphs of bounded radius) is (in the modern terms) the basis of Baker's technique~\cite{baker1994approximation}
for design of approximation algorithms.  However, even quite simple graph classes (e.g., strong products of three paths~\cite{gridtw})
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~\cite{distapx}
and applies to much more general graph classes, including all graph classes with strongly sublinear separators and bounded maximum degree~\cite{twd}.

We say that a class of graphs $\GG$ is \emph{fractionally treewidth-fragile} if there exists a function $f$ such that
for every graph $G\in\GG$ and integer $k\ge 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 $\tw(G-X_i)\le f(k)$ for every $i$
(equivalently, there exists a probability distribution on the set $\{X\subseteq V(G):\tw(G-X)\le f(k)\}$
such that $\text{Pr}[v\in X]\le 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.

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~\cite{subconvex} 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.~\cite{erlebach2005polynomial}.

For a measurable set $A\subseteq \mathbb{R}^d$, let $\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'$ of $A$ such that $\vol(A'\cap B)\ge \tfrac{1}{s}\vol(A)$.
Note that for two boxes $A$ and $B$, we have $A\sqsubseteq_1 B$ if and only if $A\sqsubseteq B$.
An \emph{$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$, \ldots, $v_n$ of vertices of $G$,
\begin{itemize}
\item for each $i$, $\omega(v_i)$ is a box, $\iota(v_i)$ is a measurable set, and $\iota(v_i)\subseteq \omega(v_i)$,
\item if $i<j$, then $\omega(v_j)\sqsubseteq_s \iota(v_i)$, and
\item if $i<j$ and $v_iv_j\in E(G)$, then $\omega(v_j)\cap \iota(v_i)\neq\emptyset$.
\end{itemize}
We say that the representation has \emph{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:
\begin{itemize}
\item 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$.
\item 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$.
\end{itemize}

\begin{theorem}\label{thm-twfrag}
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.
\end{theorem}
\begin{proof}
For a positive integer $k$, let $f(k)=(2ksd+2)^dst$.
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$, \ldots, $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 follows.
\begin{itemize}
\item Let $\ell_{1,j}=ksd|\omega(v_1)[j]|$.
\item For $i=2,\ldots, n$, let $\ell_{i,j} = \ell_{i-1,j} / b_{i,j}$, where
$b_{i,j}=\max\bigl(1,\lfloor \tfrac{\ell_{i-1,j}}{ksd|\omega(v_i)[j]|} \bigr)$.
\end{itemize}
Let $x_j\in [0,\ell_{1,j}]$ be chosen uniformly at random, and let $\HH_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}$ and $i\in\{1,\ldots, n\}$.
For each hyperplane $H\in \HH_j$, let $i(H)$ denote the minimum integer $i$ such that $H$ can be expressed in this form.

Let $\HH=\bigcup_{j=1}^d \HH_j$.
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 \HH$
such that $i(H)\le a$.  First, let us argue that $\text{Pr}[v_a\in X]\le 1/k$.  Indeed, since $\ell{i,j}$ is an integer multiple
of $\ell_{a,j}$ for every $i<a$, we conclude that $v\in X$ if and only if for some $j\in\{1,\ldots,d\}$ and $m\in\mathbb{Z}$,
we have $x_j+m\ell_{a,j}\in \omega(v_a)[j]$.  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'\le a$ be the largest integer such that $b_{a',j}\neq 1$ if such an index exists,
and $a'=1$ otherwise; note that $\ell_{a,j}=\ell_{a',j}\ge ksd|\omega(v_{a'})[j]|$.  Moreover, since
$\omega(v_a)\sqsubseteq_s\iota(v_{a'})\subseteq \omega(v_{a'})$, we have $\omega(v_a)[j]\le s\omega(v_{a'})[j]$.
Combining these inequalities,
$$\frac{|\omega(v_a)[j]|}{\ell_{a,j}}\le \frac{s\omega(v_{a'})[j]}{ksd|\omega(v_{a'})[j]|}=\frac{1}{kd}.$$
By the union bound, we conclude that $\text{Pr}[v_a\in X]\le 1/k$.

Let us now bound the treewidth of $G-X$.  For $a\in\{1,\ldots,n\}$, the \emph{$a$-grid} is $F_a=\bigcup_{H\in \HH:i(h)\le a} H$, and we let
the $0$-grid $F_0=\emptyset$.  For $a\ge 0$, an \emph{$a$-cell} is a maximal connected subset of $\mathbb{R}^d\setminus F_a$.
A set $C\subseteq\mathbb{R}^d$ is a \emph{cell} if it is an $a$-cell for some $a\ge 0$.
A cell $C$ is \emph{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\ge 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_iv_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'$ for some $C'\in V(T)$.  Then $C'$ is an $a$-cell for some $a\ge j$, and since
$\iota(v_j)\cap C'\neq\emptyset$ and $\iota(v_j)\subset C$, we conclude that $C'\subseteq C$, and consequently $C'\preceq C$.
Moreover, any cell $C''$ such that $C'\preceq C''\preceq C$ (and thus $C'\subseteq C''\subseteq C$) is an $a'$-cell
for some $a'\ge j$ and $\iota(v_j)\cap C''\supseteq \iota(v_j)\cap C'\neq\emptyset$, implying $v_j\in\beta(C'')$.
It follows that $\{C':v_j\in\beta(C')\}$ 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}$, \ldots, $\ell_{a,d}$.  Consider $j\in\{1,\ldots,d\}$:
\begin{itemize}
\item If $a=1$, then $\ell_{a,j}=ksd |\omega(v_a)[j]|$.
\item If $a>1$ and $\ell_{a,j}=\ell_{a-1,j}$, then $b_{a,j}=1$, implying $\ell_{a,j}=\ell_{a-1,j}<2ksd|\omega(v_a)[j]|$.
\item If $a>1$ and $\ell_{a,j}>\ell_{a-1,j}$, then $\ell_{a-1,j}\ge 2ksd|\omega(v_a)[j]|$ and
$$\ell_{a,j}=\frac{\ell_{a-1,j}}{\lfloor \frac{\ell_{a-1,j}}{ksd|\omega(v_a)[j]|}\rfloor}<\tfrac{3}{2}ksd|\omega(v_a)[j]|.$$
\end{itemize}
Hence, $\ell_{a,j}<2ksd |\omega(v_a)[j]|$.  Let $C'$ be the box with the same center as $C$ and with $|C'[j]|=(2ksd+2)|\omega(v_a)[j]|$.
For any $v_i\in \beta(C)\setminus\{v_a\}$, we have $i\le 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\subseteq C'$ of $\omega(v_a)$ such that $\vol(B_i\cap\iota(v_i))\ge \tfrac{1}{s}\vol(\omega(v_a))$.
Since the representation has thickness at most $t$,
\begin{align*}
\vol(C')&\ge \vol\left(C'\cap \bigcup_{v_i\in \beta(C)\setminus\{v_a\}} \iota(v_i)\right)\\
&\ge \vol\left(\bigcup_{v_i\in \beta(C)\setminus\{v_a\}} B_i\cap\iota(v_i)\right)\\
&\ge \frac{1}{t}\sum_{v_i\in \beta(C)\setminus\{v_a\}} \vol(B_i\cap\iota(v_i))\\
&\ge \frac{\vol(\omega(v_a))(|\beta(C)|-1)}{st}.
\end{align*}
Since $\vol(C')=(2ksd+2)^d\vol(\omega(v_a))$, it follows that
$$|\beta(C)|-1\le (2ksd+2)^dst=f(k),$$
as required.
\end{proof}

573
574
575
576
577
578
579
580
581
582
583
584
585
586
The proof that (generalizations of) graphs with bounded comparable box dimensions have sublinear separators in~\cite{subconvex}
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~\cite{plotkin}.
The existence of sublinear separators is known to follow more directly from fractional treewidth-fragility.  Indeed, since $\text{Pr}[v\in X]\le 1/k$,
there exists $X\subseteq V(G)$ such that $\tw(G-X)\le f(k)$ and $|X|\le |V(G)|/k$. The graph $G-X$ has a balanced separator of size
at most $\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~\ref{thm-twfrag}.

\begin{corollary}
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).$
\end{corollary}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
587
588
589
\subsection*{Acknowledgments}
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.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
590

Zdenek Dvorak's avatar
Zdenek Dvorak committed
591
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
592
593
594
\bibliography{data}

\end{document}