comparable-box-dimension.tex 44.1 KB
Newer Older
Zdenek Dvorak's avatar
Zdenek Dvorak committed
1
2
3
4
5
6
7
\documentclass[10pt]{article}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{colonequals}
\usepackage{epsfig}
Jane Tan's avatar
Jane Tan committed
8
\usepackage{tikz}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
9
10
\usepackage{url}
\newcommand{\GG}{{\cal G}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
11
\newcommand{\HH}{{\cal H}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
12
13
14
15
16
17
18
19
20
21
22
\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}}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
23
\newcommand{\ecbdim}{\brm{dim}^{ext}_{cb}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
24
25
\newcommand{\tw}{\brm{tw}}
\newcommand{\vol}{\brm{vol}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
26
27
%%%%%

Jane Tan's avatar
Jane Tan committed
28
\newcommand{\note}[1]{\textcolor{blue}{#1}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
29
30
31
32
33
34
35
36

\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}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
37
\newtheorem{definition}[theorem]{Definition}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
38
39
40
41

\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
Daniel Gonçalves's avatar
Daniel Gonçalves committed
42
  Daniel Gon\c{c}alves\thanks{LIRMM, Université de Montpellier, CNRS, Montpellier, France. E-mail: {\tt goncalves@lirmm.fr}. Supported by the ANR grant GATO ANR-16-CE40-0009.}\and 
Zdenek Dvorak's avatar
Zdenek Dvorak committed
43
Abhiruk Lahiri\thanks{...}\and
Jane Tan's avatar
Jane Tan committed
44
Jane Tan\thanks{Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK. E-mail: {\tt jane.tan@maths.ox.ac.uk}}\and
Zdenek Dvorak's avatar
Zdenek Dvorak committed
45
46
47
48
49
50
51
Torsten Ueckerdt\thanks{Karlsruhe Institute of Technology.  E-mail: {\tt torsten.ueckerdt@kit.edu}}}
\date{}

\begin{document}
\maketitle

\begin{abstract}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
52
53
54
55
56
57
Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset
of a translation of the other. 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.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
58
59
60
61
62
\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$}
63
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
64
65
66
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$.
Jane Tan's avatar
Jane Tan committed
67
This result motivated a number of strengthenings and variations (see \cite{graphsandgeom, sachs94} for some classical examples); most relevantly for us, every planar graph is a touching graph of cubes in $\mathbb{R}^3$~\cite{felsner2011contact}.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
68

Jane Tan's avatar
Jane Tan committed
69
70
71
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 theory~\cite{nesbook}).
This is in contrast to general intersection representations where the represented class always includes arbitrarily large cliques.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
72
Of course, whether the class of touching graph of objects from $\OO$ is sparse or not depends on the system $\OO$.
73
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
74
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$
Jane Tan's avatar
Jane Tan committed
75
boxes (a \emph{box} is the Cartesian product of intervals of non-zero length, in particular axis-aligned).
Zdenek Dvorak's avatar
Zdenek Dvorak committed
76
Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} noticed that this issue disappears if we forbid such a combination of
Jane Tan's avatar
Jane Tan committed
77
long and wide boxes: For two boxes $B_1$ and $B_2$, we write $B_1 \sqsubseteq B_2$ if $B_2$ contains a translate of $B_1$.
78
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
79
80
81
82
83
84
85
86
87
88
89
90
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
91
first natural graph class with polynomial strong coloring numbers and superpolynomial weak coloring numbers
Zdenek Dvorak's avatar
Zdenek Dvorak committed
92
93
94
95
96
97
98
99
100
101
102
(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.
103
This gives arbitrarily precise approximation algorithms for all monotone maximization problems that are
Zdenek Dvorak's avatar
Zdenek Dvorak committed
104
105
106
107
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}.


Daniel Gonçalves's avatar
Daniel Gonçalves committed
108
\section{Parameters}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
109

Daniel Gonçalves's avatar
Daniel Gonçalves committed
110
111
Let us first bound the clique number $\omega(G)$ in terms of
$\cbdim(G)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
112
\begin{lemma}\label{lemma-cliq}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
113
For any graph $G$, then $\omega(G)\le 2^{\cbdim(G)}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
114
115
\end{lemma}
\begin{proof}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
116
117
118
119
120
121
122
123
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
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
124
125
\end{proof}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
126
127
128
129
130
131
132
133
134
In the following we consider the chromatic number $\chi(G)$, and one
of its variant.  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.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
135
\begin{lemma}\label{lemma-chrom}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
136
137
For any graph $G$, then $\chi(G)\le 3^{\cbdim(G)}$ and $\chi_s(G) \le 2\cdot
9^{\cbdim(G)}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
138
139
\end{lemma}
\begin{proof}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
140
  Let us focus on the star chromatic number.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
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$$
Daniel Gonçalves's avatar
Daniel Gonçalves committed
158
vertices. We proceed similarly to bound the chromatic number.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
159
160
\end{proof}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

\section{Operations}

It is clear that given a touching representation of a graph $G$, one
easily obtains a touching representation with 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.

\subsection{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 $\cbdim(G)\le |V(G)|$.
\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}
Let $f$ be a touching representation of $G-v$ by comparable boxes in $\mathbb{R}^d$, where $d=\cbdim(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}$.
\end{proof}


\subsection{Strong product}

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)$.  To obtain a touching representation of $G\boxtimes
H$ it suffice to take a product of representations of $G$ and $H$, but
the obtained representation may contain uncomparable boxes. Thus,
bounding $\cbdim(G\boxtimes H)$ in terms of $\cbdim(G)$ and
$\cbdim(H)$ seems to be a complicated task.  In the following lemma we
overcome this issue, by constraining one of the representations.

\begin{lemma}\label{lemma-sp}
  Consider a graph $H$ having a touching representation $h$ in
  $\mathbb{R}^{d_H}$ with hypercubes of unit size.  Then for any graph
  $G$, the strong product of these graphs is such that
  $\cbdim(G\boxtimes H) \le \cbdim(G) + d_H$.
\end{lemma}
\begin{proof}
  The proof simply consists in taking a product of the two
  representations.  Indeed, consider a touching respresentation with
  comparable boxes $g$ of $G$ in $\mathbb{R}^{d_G}$, with
  $d_G=\cbdim(G)$, and the depresentation $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\le d_G$}\\
  h(u)[i-d_G]&\text{ if $i > d_G$}
  \end{cases}$$
  Notice first that the boxes of $f$ are comparable as $f((u,v))
  \sqsubset f((u',v'))$ if and only if $g(u) \sqsubset g(u')$.

  Now let us observe that for any two vertices $u, u'$ of $G$, there
  is an hyperplane separating the interiors of $g(u)$ and $g(u')$, and
  similarly for $h$ and $H$. This implies that the boxes in $f$ are
  interior disjoint. Indeed, the same hyperplane that separates $g(u)$
  and $g(u')$, when extended to $\mathbb{R}^{d_G+d_H}$, now separates
  any two boxes $f((u,v))$ and $f((u',v'))$. This implies that $f$ is
  a touching representation of a subgraph of $G\boxtimes H$.

  Similarly, one can also observe that there is a point $p$ in the
  intersection of $f((u,v))$ and $f((u',v'))$, if and only if there is
  a point $p_G$ in the intersection of $g(u)$ and $g(u')$, and a point
  $p_H$ in the intersection of $h(v)$ and $h(v')$. Indeed, one can
  obtain $p_G$ and $p_H$ by projecting $p$ in $\mathbb{R}^{d_G}$ or in
  $\mathbb{R}^{d_G}$ respectively, and conversely $p$ can be obtained
  by taking the product of $p_G$ and $p_H$. Thus $f$ is indeed a
  touching representation of $G\boxtimes H$.
\end{proof}


\subsection{Subgraph}

Examples show that the comparable box dimension of a graph $G$ may be
larger than the one a subgraph $H$ of $G$. 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~\cite{subconvex}, but since the setting is somewhat
different and the construction of~\cite{subconvex} uses rotated boxes,
we provide details of the argument.



Zdenek Dvorak's avatar
Zdenek Dvorak committed
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
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}$.
290

Zdenek Dvorak's avatar
Zdenek Dvorak committed
291

Daniel Gonçalves's avatar
Daniel Gonçalves committed
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
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
391
392
393
394
395
396
397
398
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
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
\subsection{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.  A \emph{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
\emph{clique-sum extendable} representations.

\begin{definition}
Consider a graph $G$ with a distinguished clique $C^*$, called the
\emph{root clique} of $G$. A touching representation (with comparable
boxes or not) $h$ of $G$ in $\mathbb{R}^d$ is called
\emph{$C^*$-clique-sum extendable} if the following conditions hold.
\begin{itemize}
\item[{\bf(vertices)}] There are $|V(C^*)|$ dimensions, denoted $d_u$ for each
  vertex $u\in V(C^*)$, such that:
  \begin{itemize}
  \item[(v1)] for each vertex $u\in V(C^*)$, $h(u)[d_u] = [-1 ,0]$ and
    $h(u)[i] = [0,1]$, for any dimension $i\neq d_u$, and
  \item[(v2)] for any vertex $v\notin V(C^*)$, $h(v) \subset [0,1)^d$.
  \end{itemize}
\item[{\bf(cliques)}] For every clique $C$ of $G$ we define a point
  $p(C)\in I_C \cap [0,1)^d$, where $I_C =\cap_{v\in V(C)} h(v)$, and
  we define the box $h^\epsilon(C)$, for any $\epsilon > 0$, by
  $h^\epsilon(C)[i] = [p(C)[i],p(C)[i]+\epsilon]$, for every dimension
  $i$. Furthermore, for a sufficiently small $\epsilon > 0$ these
  \emph{clique boxes} verify the following conditions.
  \begin{itemize}
  \item[(c1)] For any two cliques $C_1\neq C_2$, $h^\epsilon(C_1) \cap
    h^\epsilon(C_2) = \emptyset$ (i.e. $p(C_1) \neq p(C_2)$).
  \item[(c2)] A box $h(v)$ intersects $h^\epsilon(C)$ if and only if
    $v\in V(C)$, and in that case their intersection is a facet of
    $h^\epsilon(C)$ incident to $p(C)$ (i.e. if we denote this
    intersection $I$, then $I[i] = \{p(C)[i] \}$ for some dimension
    $i$, and $I[j] = [p(C)[j],p(C)[j]+\epsilon]$ for the other
    dimensions $j\neq i$).
  \end{itemize}
\end{itemize}
\end{definition}
Note that we may consider that the root clique is empty, that is the
empty subgraph with no vertices.  In that case the clique is denoted
$\emptyset$.  Let $\ecbdim(G)$ be the minimum dimension such that $G$
has a $\emptyset$-clique-sum extendable touching representation with
comparable boxes.  The following lemma ensures that clique-sum
extendable representations behave well with respect to full
clique-sums.

\begin{lemma}\label{lem-cs}
  Consider two graphs $G_1$ and $G_2$, given with a $C^*_1$- and a
  $C^*_2$-clique-sum extendable representations with comparable boxes
  $h_1$ and $h_2$, in $\mathbb{R}^{d_1}$ and $\mathbb{R}^{d_2}$
  respectively. Let $G$ be the graph obtained after performing a full
  clique-sum of these two graphs on any clique $C_1$ of $G_1$, and on
  the root clique $C^*_2$ of $G_2$.  Then $G$ admits a $C^*_1$-clique
  sum extendable representation with comparable boxes $h$ in
  $\mathbb{R}^{\max(d_1,d_2)}$. Furthermore, we have that the aspect
  ratio of $h(v)$ is the same as the one of $h_1(v)$, if $v\in
  V(G_1)$, or the same as $h_2(v)$ if $v\in V(G_2)\setminus V(C^*_2)$.
  \note{ shall we remove the aspect ratio thing ? only needed for the
    hypercubes of the k-trees, but those are not really needed...}
\end{lemma}
\begin{proof}
  The idea is to translate (allowing also exchanges of dimensions) and
  scale $h_2$ to fit in $h_1^\epsilon(C_1)$. Consider an $\epsilon >0$
  sufficiently small so that, $h_1^\epsilon(C_1)$ verifies all the
  (cliques) conditions, and such that $h_1^\epsilon(C_1) \sqsubseteq
  h_1(v)$ for any vertex $v\in V(G_1)$.  Without loss of generality,
  let us assume that $V(C_1)=\{v_1,\ldots,v_k\}$, and we also assume
  that $h_1(v_i)$ and $h_1^\epsilon(C_1)$ touch in dimension $i$ (i.e.
  $h_1(v_i)[i] \cap h_1^\epsilon(C_1)[i] = \{p(C_1)[i]\}$, and
  $h_1(v_i)[j] \cap h_1^\epsilon(C_1)[j] =
  [p(C_1)[j],p(C_1)[j]+\epsilon] $ for $j\neq i$.

  Now let us consider $G_2$ and its representation $h_2$. Here the
  vertices of $C^*_2$ are also denoted $v_1,\ldots,v_k$, and let us
  denote $d_{v_i}$ the dimension in $h_2$ that fulfills condition (v1)
  with respect to $v_i$.

  Let $d=\max(d_1,d_2)$. We are now ready for defining $h$.  For the
  vertices of $G_1$ it is almost the same representation as $h_1$, as
  we set $h(v)[i] = h_1(v)[i]$ for any dimension $i\le d_1$. If $d=d_2
  > d_1$, then for any dimension $i>d_1$ we set $h(v)[i] = [0,1]$ if
  $v\in V(C^*_1)$, and $h(v)[i] = [0,\frac12]$ if $v\in
  V(G_1)\setminus V(C^*_1)$. Similarly the clique points $p_1(C)$
  become $p(C)$ by setting $p(C)[i] = p_1(C)[i]$ for $i\le d_1$, and 
  $p(C)[i] = \frac14$ for $i> d_1$.

  For $h_2$ and the vertices in $V(G_2) \setminus \{v_1,\ldots,v_k\}$
  we have to consider a mapping $\sigma$ from $\{1,\ldots,d_2\}$ to
  $\{1,\ldots,d\}$ such that $\sigma(d_{v_i}) = i$. This mapping
  describes the changes of dimension we have to perform.  We also have
  to perform a scaling in order to make $h_2$ fit inside
  $h_1^\epsilon(C_1)$. This is ensured by multiplying the coordinates
  by $\epsilon$. More formally, for any vertex $v\in V(G_2) \setminus
  \{v_1,\ldots,v_k\}$, we set $h(v)[\sigma(i)] = p(C_1)[\sigma(i)] +
  \epsilon h_2(v)[i]$ for $i\in \{1 ,\ldots,d_2\}$, and $h(v)[j] =
  p(C_1)[j] + [0, \epsilon/2]$, otherwise (for any $j$ not in the
  image of $\sigma$). Note that if we apply the same mapping from
  $h_2$ to $h$, to the vertices of $\{v_1,\ldots,v_k\}$, then the
  image of $h_2(v_i)$ fit inside the (previously defined) box
  $h(v_i)$.  Similarly the clique points $p_2(C)$ become $p(C)$ by
  setting $p(C)[\sigma(i)] = p(C_1)[\sigma(i)] + \epsilon p_2(C)[i]$
  for $i\in \{1 ,\ldots,d_2\}$, and $p(C)[j] = p(C_1)[j] + [0,
    \frac14]$, otherwise.

  Note that we have defined (differently) both $h^\epsilon(C_1)$
  (resp. $p(C_1)$) and $h^\epsilon(C^*_2)$ (resp. $p(C^*_2)$), despite
  the fact that those cliques were merged. In the following we use
  $h^\epsilon(C_1)$ and $p(C_1)$ only for the purpose of the
  proof. The point and the box corresponding to these clique in $h$ is
  $p(C^*_2)$ and $h^\epsilon(C^*_2)$.
  
  Let us now check that $h$ is a $C^*_1$-clique sum extendable
  representation with comparable boxes. The fact that the boxes are
  comparable follows from the fact that those of $V(G_1)$
  (resp. $V(G_1)$) are comparable in $h_1$ (resp. $h_2$) with the
  boxes of $V(C^*_1)$ (resp. $V(C^*_2)$) being hypercubes of side one,
  and the other boxes being smaller. Clearly, by construction both
  $h_1(u) \sqsubseteq h_1(v)$ or $h_2(u) \sqsubseteq h_2(v)$, imply
  $h(u) \sqsubseteq h(v)$, and for any vertex $u\in V(G_1)$ and any
  vertex $v\in V(G_2) \setminus \{v_1,\ldots,v_k\}$, we have $h(v)
  \sqsubseteq h^\epsilon(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_1,\ldots,v_k\}$) it
  is clear that $h(u)$ and $h(v)$ are interior disjoint, 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_1,\ldots,v_k\}$. As
  $h(v)$ fits inside $h^\epsilon(C_1)$, we have that $h(u)$ and $h(v)$
  are interior disjoint. Furthermore, if they intersect then $u\in
  V(C_1)$, say $u=v_1$, and $h(v)[1] = [p(C_1)[1], p(C_1)[1]+\alpha]$
  for some $\alpha>0$.  By construction, this implies that $h_2(v_1)$
  and $h_2(v)$ intersect.

  Finally for the $C^*_1$-clique-sum extendability, one can easily
  check that the (vertex) conditions hold, such as the (clique)
  conditions.  
\end{proof}

The following lemma shows that any graphs has a $C^*$-clique-sum
extendable representation in $\mathbb{R}^d$, for $d= \omega(G) +
\ecbdim(G)$ and for any clique $C^*$.
\begin{lemma}\label{lem-apex-cs}
  For any graph $G$ and any clique $C^*$, we have that $G$ admits a
  $C^*$-clique-sum extendable touching representation with comparabe
  boxes in $\mathbb{R}^d$, for $d = |V(C^*)| + \ecbdim(G\setminus
  V(C^*))$.
\end{lemma}
\begin{proof}
  The proof is essentially the same as the one of
  Lemma~\ref{lemma-apex}.  Consider a $\emptyset$-clique-sum
  extendable touching representation $h'$ of $G\setminus V(C^*)$ by
  comparable boxes in $\mathbb{R}^{d'}$, with $d' = \cbdim(G\setminus
  V(C^*))$, and let $V(C^*) = \{v_1,\ldots,v_k\}$. We now construct
  the desired representation $h$ of $G$ as follows. For each vertex
  $v_i\in V(C^*)$ let $h(v_i)$ be the box fulfilling (v1) with
  $d_{v_i} = i$. For each vertex $u\in V(G)\setminus V(C^*)$, if $i\le
  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] =
  h'(u)[i-k]$. We proceed similarly for the clique points. For any
  clique $C$ of $G$, if $i\le 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 have
  to refer to the clique point $p'(C')$ of $C'=C\setminus
  \{v_1,\ldots,v_k\}$, as we set $p(C)[i] = p'(C')[i-k]$. One can
  easily check that $h$ is as desired.
\end{proof}

The following lemma provides an upper bound on $\ecbdim(G)$ in terms
of $\cbdim(G)$ and $\chi(G)$.
\begin{lemma}\label{lem-ecbdim-cbdim}
  For any graph $G$, $\ecbdim(G) \le \cbdim(G) + \chi(G)$.
\end{lemma}
\begin{proof}
  Let $h$ be a touching representation with comparable boxes of $G$ in
  $\mathbb{R}^d$, with $d=\cbdim(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-\epsilon,b+\epsilon]$ for each vertex $v$ and dimension
  $i$. Furthermore $\alpha$ is chosen sufficiently small, so that no
  new intersection was created. The obtained representation $h_1$ is
  thus an intersection representation of the same graph $G$ such that,
  for every clique $C$ of $G$, the intersection $I_C= \cap_{v\in V(C)
    h_1(v)}$ is $d$-dimensional. For any maximal clique $C$ of $G$, let
  $p_1(C)$ be a point in the interior of $I_C$.

  Now we add $\chi(G)$ dimensions to make the representation touching
  again, and to ensure some space for the clique boxes
  $h^\epsilon(C)$. Formally we define $h_2$ as follows.
  $$h_2(u)[i]=\begin{cases}
  h_1(u)[i]&\text{ if $i\le d$}\\
  [1/5,3/5]&\text{ if $c(u) < i-d$}\\
  [0,2/5]&\text{ if $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 us denote $c(C)$, the set
  $\{c(u)\ |\ u\in V(C')\}$, and let $C$ be one of the maximal cliques
  containing $C'$.We now set
  $$p_2(C')[i]=\begin{cases}
  p_1(C) &\text{ if $i\le d$}\\
  2/5 &\text{ if $i-d \in c(C')$}\\%\text{if $\exists u\in V(C)$ with $c(u) = i-d$}\\
  1/2 &\text{ otherwise}
  \end{cases}
  $$ One can now check that this is a $\emptyset$-clique-sum
  extendable touching representation with comparable boxes. In particular,
  one should notice that for a vertex $u$ of a clique $C'$ we have that
  $h_2^{\epsilon}(C')[i] \subset h_2(u)[i]$ for every dimension $i$,
  except if $c(u)=i-d$. If $c(u)=i-d$, then $h_2(u)[i] \cap
  h_2^{\epsilon}(C')[i] = \{2/5\}$.
\end{proof}





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

Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
520
521
Dujmovi{\'c} et al.~\cite{DJM+} proved the following result.
\begin{theorem}\label{thm-prod}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
522
Any graph $G$ is a subgraph of the strong product of a $k$-tree, a path, and $K_m$, where
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
523
\begin{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
524
525
\item $k=3$ and $m=3$ if $G$ is planar, and
\item $k=4$ and $m=\max(2g,3)$ if $G$ has Euler genus at most $g$.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
526
\end{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
527
528
529
530
Moreover, for every $t$, there exists a $k$ such that any
$K_t$-minor-free graph $G$ is a subgraph of a graph obtained from
successive clique-sums of graphs, that are obtained from the strong
product of a path and a $k$-tree, by adding at most $k$ apex vertices.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
531
532
\end{theorem}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
533
534
535
536
537
538
539
540
541
542
Let us first bound the comparable box dimension of a graph in terms of
its Euler genus.  As paths and $m$-clique admit touching
representations with hypercubes of unit size in $\mathbb{R}^{1}$ and
in $\mathbb{R}^{\lceil \log_2 m \rceil}$ respectively, by
  Lemma~\ref{lemma-sp} it suffice to bound the comparable box
  dimension of $k$-trees.

\begin{theorem}\label{thm-ktree}
  For any $k$-tree $G$,  $\cbdim(G) \le \ecbdim(G) \le k+1$.
\end{theorem}
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
543
\begin{proof}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
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
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
  Note that there exists a $k$-tree $G'$ having a $k$-clique $C^*$
  such that $G'\setminus V(C^*)$ corresponds to $G$.  Let us construct
  a $C^*$-clique-sum extendable representation of $G'$ and note that
  it induces a $\emptyset$-clique-sum extendable representation of
  $G$.

Note that $G'$ can be obtained by starting with a $(k+1)$-clique
containing $C^*$, and by performing successive full clique-sums of
$K_{k+1}$ on a $K_k$ subclique.  By Lemma~\ref{lem-cs}, it suffice to
show that $K_{k+1}$, the $(k+1)$-clique with vertex set $\{v_1,
\ldots, v_{k+1}\}$, has a $(K_{k+1} -\{v_{k+1}\})$-clique-sum
extendable touching representation with hypercubes. Let us define such
touching representation $h$ as follows:
\begin{itemize}
  \item $h(v_i)[i] = [-1,0] $ if $i\le k$
  \item $h(v_i)[j] = [0,1] $ if $i\le k$ and $i\neq j$
  \item $h(v_{k+1})[j] = [0,\frac12]$ for any $j$
\end{itemize}
One can easily check that the (vertices)
conditions are fulfilled. For the (cliques) conditions let us set
the point $p(C)$ for every clique $C$ as follows:
\begin{itemize}
  \item $p(C)[i] = 0 $ for every $i\le k$ and if $v_i\in C$
  \item $p(C)[i] = \frac14 $ for every $i\le k$ and if $v_i\notin C$
  \item $p(C)[k+1] = \frac12 $ if $v_{k+1}\in C$
  \item $p(C)[k+1] = \frac34 $ if $v_{k+1}\notin C$
\end{itemize}
By construction, it is clear that $p(C) \in h(v_i)$ if and only if
$v_i\in V(C)$. Let us check the other (cliques) conditions.

For any two distinct cliques $C_1$ and $C_2$ the points $p(C_1)$ and
$p(C_2)$ are distinct.  Indeed, if $|V(C_1)|\ge |V(C_2)|$ there is a
vertex $v_i\in V(C_1)\setminus V(C_2)$, and this implies that
$p(C_1)[i] < p(C_2)[i]$.

For a vertex $v_i$ and a clique $C$, the boxes $h(v_i)$ and
$h^\epsilon(C)$ intersect if and only if $v_i\in V(C)$. Indeed, if
$v_i\in V(C)$ then $p(C)\in h(v_i)$ and $p(C)\in h^\epsilon(C)$, and
if $v_i\notin V(C)$ then $h(v_i)[i] = [-1,0]$ if $i\le k$
(resp. $h(v_i)[i] = [0 \frac12]$ if $i= k+1$) and $h^\epsilon(C)[i] =
[\frac14,\frac14+\epsilon]$ (resp. $h^\epsilon(C)[i] =
[\frac34,\frac34+\epsilon]$). Finally, if $v_i\in V(C)$ we have that
$h(v_i)[i] \cap h^\epsilon(C)[i] = \{p(C)[i]\}$ and that $h(v_i)[j]
\cap h^\epsilon(C)[j] = [p(C)[j],p(C)[j]+\epsilon]$ for any $j\neq i$
and any $\epsilon <\frac14$.  This concludes the proof of the theorem.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
589
590
\end{proof}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
591
592
593
594
595
596
597
598
599
600
601
602
As every planar graph $G$ has a touching representation with cubes in
$\mathbb{R}^3$~\cite{felsner2011contact}, we have that $\cbdim(G)\le
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~\ref{thm-ktree},
Lemma~\ref{lemma-sp}, and Corollary~\ref{cor-subg} we obtain:

\begin{corollary}\label{cor-genus}
For every graph $G$ of Euler genus $g$, there exists a supergraph $G'$
of $G$ such that $\cbdim(G')\le 5+1+\lceil \log_2 \max(2g,3)\rceil$.
Consequently, $$\cbdim(G)\le 5\cdot 81^7 \cdot \max(2g,3)^{\log_2
  81}.$$
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
603
\end{corollary}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621


Let us now finally prove Theorem~\ref{thm-minor}, using the structure
provided by Theorem~\ref{thm-prod}.  We have seen that the strong
product of a path and a $k$-tree has bounded comparable boxes
dimension, and by Lemma~\ref{lemma-apex} adding at most $k$ apex
vertices keeps the dimension bounded. Then by Lemma~\ref{lemma-chrom}
and Lemma~\ref{lem-ecbdim-cbdim}, these graphs admit a
$\emptyset$-clique-sum extendable representations in bounded
dimensions. As the obtained graphs have bounded dimension, by
Lemma~\ref{lemma-cliq} and Lemma~\ref{lem-apex-cs}, for any choice of
a root clique $C^*$, they have a $C^*$-clique-sum extendable
representation in bounded dimension. Thus by Lemma~\ref{lem-cs} any
sequence of clique sum from these graphs leads to a graph with bounded
dimension. Finally, we have seen that taking a subgraph does not lead
to undounded dimension, and we obtain Theorem~\ref{thm-minor}.


Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
622
Note that the graph obtained from $K_{2n}$ by deleting a perfect matching has Euler genus $\Theta(n^2)$
Jane Tan's avatar
Jane Tan committed
623
and comparable box dimension $n$. It follows that the dependence of the comparable box dimension cannot be
Daniel Gonçalves's avatar
Daniel Gonçalves committed
624
subpolynomial (though the degree $\log_2 81$ of the polynomial established in Corollary~\ref{cor-genus}
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
625
626
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}.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
627
It would be interesting to prove Theorem~\ref{thm-minor} without using the structure theorem.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
628

Zdenek Dvorak's avatar
Zdenek Dvorak committed
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
\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}

749
750
751
752
753
754
755
756
757
758
759
760
761
762
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
763
764
765
\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
766

Zdenek Dvorak's avatar
Zdenek Dvorak committed
767
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
768
769
770
\bibliography{data}

\end{document}