comparable-box-dimension.tex 57.4 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}
52
53
Two boxes in $\mathbb{R}^d$ are \emph{comparable} if one of them is a subset
of a translation of the other one. The \emph{comparable box dimension} of a graph
Daniel Gonçalves's avatar
Daniel Gonçalves committed
54
55
56
57
$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
\end{abstract}

\section{Introduction}

62
Given 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$})
64
such that the interiors of $f(u)$ and $f(v)$ are disjoint for all distinct $u,v\in V(G)$, and $f(u)\cap f(v)\neq\emptyset$ if and only if $uv\in E(G)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
65
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$.
66
This result has motivated numerous strengthenings and variations (see \cite{graphsandgeom, sachs94} for some classical examples); most relevantly for us, Felsner and Francis~\cite{felsner2011contact} showed that every planar graph is a touching graph of cubes in $\mathbb{R}^3$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
67

Jane Tan's avatar
Jane Tan committed
68
69
70
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.
71
72
Of course, whether the class of touching graphs of objects from $\OO$ is sparse or not depends on the system $\OO$.
For example, all complete bipartite graphs $K_{n,m}$ are touching graphs of boxes in $\mathbb{R}^3$, where the vertices in
Zdenek Dvorak's avatar
Zdenek Dvorak committed
73
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$
74
boxes (throughout the paper, by a \emph{box} we mean an axis-aligned one, i.e., the Cartesian product of closed intervals of non-zero length).
Zdenek Dvorak's avatar
Zdenek Dvorak committed
75
Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} noticed that this issue disappears if we forbid such a combination of
76
long and wide boxes, a condition which can be expressed as follows. For two boxes $B_1$ and $B_2$, we write $B_1 \sqsubseteq B_2$ if $B_2$ contains a translate of $B_1$.
77
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
78
A \emph{touching representation by comparable boxes} of a graph $G$ is a touching representation $f$ by boxes
79
80
such that for every $u,v\in V(G)$, the boxes $f(u)$ and $f(v)$ are comparable. 
Let the \emph{comparable box dimension} $\cbdim(G)$ of a graph $G$ be the smallest integer $d$ such that $G$ has a touching representation by comparable boxes in $\mathbb{R}^d$.
81
Let us remark that the comparable box dimension of every graph $G$ is at most $|V(G)|$, see Section~\ref{sec-vertad} for details.
82
Then for a class $\GG$ of graphs, let $\cbdim(\GG):=\sup\{\cbdim(G):G\in\GG\}$. Note that $\cbdim(\GG)=\infty$ if the
Zdenek Dvorak's avatar
Zdenek Dvorak committed
83
84
85
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,
86
they showed that if a class $\GG$ has finite comparable box dimension, then it has polynomial strong coloring
Zdenek Dvorak's avatar
Zdenek Dvorak committed
87
88
89
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}
90
proved that graphs of comparable box dimension $3$ have exponential weak coloring numbers, 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
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
107
\section{Parameters}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
108

109
110
In this section we bound some basic graph parameters in terms of comparable box dimension.
The first result bounds the clique number $\omega(G)$ in terms of $\cbdim(G)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
111
\begin{lemma}\label{lemma-cliq}
112
For any graph $G$, we have $\omega(G)\le 2^{\cbdim(G)}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
113
114
\end{lemma}
\begin{proof}
115
116
We may assume that $G$ has bounded comparable box dimension
witnessed by a representation $f$. To represent any clique $A = \{a_1,\ldots,a_w\}$ in $G$, the
Daniel Gonçalves's avatar
Daniel Gonçalves committed
117
118
119
120
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
121
122
123
least one of the $2^d$ orthants at $p$. At the same time, it follows from the definition
of a touching representation that $f(a_1),\ldots,f(a_d)$ have pairwise disjoint
interiors, and hence $w \leq 2^d$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
124
\end{proof}
125
126
127
Note that a clique with $2^d$ vertices has a touching representation by comparable boxes in $\mathbb{R}^d$,
where each vertex is a hypercube defined as the Cartesian product of intervals of form $[-1,0]$ or $[0,1]$.
Together with Lemma~\ref{lemma-cliq}, it follows that $\cbdim(K_{2^d})=d$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
128

Daniel Gonçalves's avatar
Daniel Gonçalves committed
129
In the following we consider the chromatic number $\chi(G)$, and one
130
of its variants.  A \emph{star coloring} of a graph $G$ is a proper
Daniel Gonçalves's avatar
Daniel Gonçalves committed
131
132
133
134
135
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
136
from~\cite{subconvex}, although we include an argument to make the
Daniel Gonçalves's avatar
Daniel Gonçalves committed
137
dependence clear.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
138
\begin{lemma}\label{lemma-chrom}
139
For any graph $G$ we have $\chi(G)\le 3^{\cbdim(G)}$ and $\chi_s(G) \le 2\cdot
Daniel Gonçalves's avatar
Daniel Gonçalves committed
140
9^{\cbdim(G)}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
141
142
\end{lemma}
\begin{proof}
143
144
145
We focus on the star chromatic number and note that the chromatic number may be bounded similarly. Suppose that $G$ has comparable box dimension $d$ witnessed by a representation $f$, and let $v_1, \ldots, v_n$ be the vertices of $G$ written so that $\vol(f(v_1)) \geq \ldots \geq \vol(f(v_n))$. Equivalently, we have $f(v_i)\sqsubseteq f(v_j)$ whenever $i>j$. Now define a greedy colouring $c$ so that $c(i)$ is the smallest color such that $c(i)\neq c(j)$ for any $j<i$ for which either $v_jv_i\in E(G)$ or there exists $m>j$ such that $v_jv_m,v_mv_i\in E(G)$. Note that this gives a star coloring, since a path on four vertices always contains a 3-vertex subpath of the form $v_{i_1}v_{i_2}v_{i_3}$ such that $i_1<i_2,i_3$ and our coloring procedure gives distinct colors to vertices forming such a path.

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
149
150
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)$
151
is at most $(3^d-1)^2$. This means that when choosing the color of $v_i$ greedily, we only need to avoid colors of at most
Zdenek Dvorak's avatar
Zdenek Dvorak committed
152
$$(5^d-1) + (3^d-1) + (3^d-1)^2<5^d+9^d<2\cdot 9^d$$
153
vertices. 
Zdenek Dvorak's avatar
Zdenek Dvorak committed
154
155
\end{proof}

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
\begin{figure}
\centering
    \begin{tikzpicture}[xscale=1, yscale=0.6]
    \footnotesize
    	\draw[dashed] (0,0) rectangle (5,5);
	\filldraw[red!20!white] (2,2) rectangle (3,3);
	\draw (1,0) rectangle (3,2);
	\node [fill=none, color=red] at (2.5, 2.5) {$f(v_i)$};
	\draw (3,3) rectangle (6,6);
	\draw (1.4,2.6) rectangle (2,3.2);
	\draw (-0.8,2.2) rectangle (1.4,4.4);
	\filldraw[blue!20!white] (1.5,0.5) rectangle (2.5,1.5);
	\filldraw[blue!20!white] (3.5,3.5) rectangle (4.5,4.5);
	\filldraw[blue!20!white] (0.2,2.8) rectangle (1.2,3.8);
	\node [fill=white] at (5, 1) {$B$};
	\node [fill=white] at (6, 4.5) {$f(v_1)$};
	\node [fill=none, color=blue] at (4, 4) {$B_1$};
	\node [fill=white] at (-0.8, 3) {$f(v_2)$};
	\node [fill=none, color=blue] at (0.7, 3.3) {$B_2$};
	\node [fill=white] at (3.4, 1) {$f(v_3)$};
	\node [fill=none, color=blue] at (2, 1) {$B_3$};
    \end{tikzpicture}
    \caption{Nearby boxes obstructing colors at $v_i$.}
    \label{fig:lowercolcount}
\end{figure}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
182
183
184
185

\section{Operations}

It is clear that given a touching representation of a graph $G$, one
186
easily obtains a touching representation by boxes of an induced
Daniel Gonçalves's avatar
Daniel Gonçalves committed
187
188
189
190
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.

191
\subsection{Vertex addition}\label{sec-vertad}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

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
213
214
215
216
217
218
219
220
221
222
223
224
distinct vertices $(u_1,v_1)$ and $(u_2,v_2)$ adjacent if and only if
$u_1$ is equal to or adjacent to $u_2$ in $G$
and $v_1$ is equal to or adjacent to $v_2$ in $H$.
To obtain a touching representation of $G\boxtimes
H$ it suffices to take a product of representations of $G$ and $H$, but
the resulting representation may contain incomparable boxes. 
Indeed, $\cbdim(G\boxtimes H)$ in general is not bounded by a function
of $\cbdim(G)$ and $\cbdim(H)$; for example, every star has comparable box dimension
at most two, but the strong product of the star $K_{1,n}$ with itself contains
$K_{n,n}$ as an induced subgraph, and thus its comparable box dimension is at least $\Omega(\log n)$.
However, as shown in the following lemma, this issue does not arise if the representation of $H$ consists of translates
of a single box; by scaling, we can without loss of generality assume this box is a unit hypercube.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
225
226
227

\begin{lemma}\label{lemma-sp}
  Consider a graph $H$ having a touching representation $h$ in
228
229
230
  $\mathbb{R}^{d_H}$ by axis-aligned hypercubes of unit size.  Then for any graph
  $G$, the strong product $G\boxtimes H$ of these graphs has comparable box dimension at most
  $\cbdim(G) + d_H$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
231
232
233
\end{lemma}
\begin{proof}
  The proof simply consists in taking a product of the two
234
235
  representations.  Indeed, consider a touching respresentation $g$ of $G$ by 
  comparable boxes in $\mathbb{R}^{d_G}$, with
236
  $d_G=\cbdim(G)$, and the representation $h$ of $H$.  Let us define a
Daniel Gonçalves's avatar
Daniel Gonçalves committed
237
238
239
240
  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$}\\
241
  h(v)[i-d_G]&\text{ if $i > d_G$}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
242
  \end{cases}$$
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
  Consider distinct vertices $(u,v)$ and $(u',v')$ of $G\boxtimes H$.
  The boxes $g(u)$ and $g(u')$ are comparable, say $g(u)\sqsubseteq g(u')$.  Since $h(v')$
  is a translation of $h(v)$, this implies that $f((u,v))\sqsubseteq f((u',v'))$. Hence, the boxes
  of the representation $f$ are pairwise comparable.

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

  Finally, suppose that $(u,v)$ and $(u',v')$ are adjacent in $G\boxtimes H$.
  Then there exists a point $p_G$ in the intersection of $g(u)$ and $g(u')$,
  since $u=u'$ or $uu'\in E(G)$ and $g$ is a touching representation of $G$;
  and similarly, there exists a point $p_H$ in the intersection of $h(v)$ and $h(v')$.
  Then $p_G\times p_H$ is a point in the intersection of $f((u,v))$ and $f((u',v'))$.
  Hence, $f$ is indeed a touching representation of $G\boxtimes H$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
265
266
267
\end{proof}


268
\subsection{Taking a subgraph}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
269

270
271
The comparable box dimension of a subgraph of a graph $G$ may be larger than $\cbdim(G)$, see the end of this
section for an example. However, we show that the
Daniel Gonçalves's avatar
Daniel Gonçalves committed
272
273
274
275
276
277
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
278
279
280
281
282
\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)$.
283
Let $f$ be a touching representation of $G'$ by comparable boxes in $\mathbb{R}^d$, where $d=\cbdim(G')$.  Let $\varphi$
Zdenek Dvorak's avatar
Zdenek Dvorak committed
284
285
be a star coloring of $G'$ using colors $\{1,\ldots,c\}$, where $c=\chi_s(G')$.

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
290
291
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
292
293
294
295
296
297
$$h(v)[d_{i,j}]=\begin{cases}
[1/3,4/3]&\text{if $v\in A_{i,j}$}\\
[-4/3,-1/3]&\text{if $v\in A_{j,i}$}\\
[-1/2,1/2]&\text{otherwise.}
\end{cases}$$
Note that the boxes in this extended representation are comparable,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
298
299
as in the added dimensions, all the boxes have size $1$.

300
301
302
303
304
Suppose $uv\in E(G)$, where $\varphi(u)=i$ and $\varphi(v)=j$ and say $i<j$.
We cannot have $u\in A_{i,j}$ and $v\in A_{j,i}$, as then $a_j(u)uva_i(v)$ would be a 4-vertex path in $G'$ in colors $i$ and $j$.
Hence, in any added dimension $d'$, we have $h(u)[d']=[-1/2,1/2]$ or $h(v)[d']=[-1/2,1/2]$,
and thus $h(u)[d']\cap h(v)[d']\neq\emptyset$.  
Since the boxes $f(u)$ and $f(v)$ touch, it follows that the boxes $h(u)$ and $h(v)$ touch as well.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
305
306

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
307
$h(v)$.  Hence, we can assume $uv\in E(G')\setminus E(G)$, $\varphi(u)=i$, $\varphi(v)=j$ and $i<j$.  Then $u\in A_{i,j}$, $v\in A_{j,i}$,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
308
309
310
311
312
313
314
315
316
317
318
$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}

319
Let us remark that an exponential increase in the dimension is unavoidable: We have $\cbdim(K_{2^d})=d$,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
320
but the graph obtained from $K_{2^d}$ by deleting a perfect matching has comparable box dimension $2^{d-1}$.
321

Zdenek Dvorak's avatar
Zdenek Dvorak committed
322

Daniel Gonçalves's avatar
Daniel Gonçalves committed
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
\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}
341
342
343
344
Consider a graph $G$ with a distinguished clique $C^\star$, called the
\emph{root clique} of $G$. A touching representation $h$ of $G$
by (not necessarily comparable) boxes in $\mathbb{R}^d$ is called
\emph{$C^\star$-clique-sum extendable} if the following conditions hold for every sufficiently small $\varepsilon>0$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
345
\begin{itemize}
346
347
\item[{\bf(vertices)}] For each $u\in V(C^\star)$, there exists a dimension $d_u$,
  such that:
Daniel Gonçalves's avatar
Daniel Gonçalves committed
348
  \begin{itemize}
349
350
351
352
  \item[(v0)] $d_u\neq d_{u'}$ for distinct $u,u'\in V(C^\star)$,
  \item[(v1)] each vertex $u\in V(C^\star)$ satisfies $h(u)[d_u] = [-1,0]$ and
    $h(u)[i] = [0,1]$ for any dimension $i\neq d_u$, and
  \item[(v2)] each vertex $v\notin V(C^\star)$ satisfies $h(v) \subset [0,1)^d$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
353
  \end{itemize}
354
355
356
357
358
359
\item[{\bf(cliques)}] For every clique $C$ of $G$, there exists
  a point $$p(C)\in [0,1)^d\cap \bigcap_{v\in V(C)} h(v)$$
  such that, defining the \emph{clique box} $h^\varepsilon(C)$
  by setting
  $$h^\varepsilon(C)[i] = [p(C)[i],p(C)[i]+\varepsilon]$$ for every dimension
  $i$, the following conditions are satisfied:
Daniel Gonçalves's avatar
Daniel Gonçalves committed
360
  \begin{itemize}
361
362
363
  \item[(c1)] For any two cliques $C_1\neq C_2$, $h^\varepsilon(C_1) \cap
    h^\varepsilon(C_2) = \emptyset$ (equivalently, $p(C_1) \neq p(C_2)$).
  \item[(c2)] A box $h(v)$ intersects $h^\varepsilon(C)$ if and only if
Daniel Gonçalves's avatar
Daniel Gonçalves committed
364
    $v\in V(C)$, and in that case their intersection is a facet of
365
366
367
368
369
370
    $h^\varepsilon(C)$ incident to $p(C)$.  That is, there exists a dimension $i_{C,v}$
    such that for each dimension $j$,
    $$h(v)[j]\cap h^\varepsilon(C)[j] = \begin{cases}
    \{p(C)[i_{C,v}] \}&\text{if $j=i_{C,v}$}\\
    [p(C)[j],p(C)[j]+\varepsilon]&\text{otherwise.}
    \end{cases}$$
Daniel Gonçalves's avatar
Daniel Gonçalves committed
371
372
373
  \end{itemize}
\end{itemize}
\end{definition}
374
Note that the root clique can be empty, that is the
Daniel Gonçalves's avatar
Daniel Gonçalves committed
375
376
empty subgraph with no vertices.  In that case the clique is denoted
$\emptyset$.  Let $\ecbdim(G)$ be the minimum dimension such that $G$
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
has an $\emptyset$-clique-sum extendable touching representation by
comparable boxes.

Let us remark that a clique-sum extendable representation in dimension $d$ implies
such a representation in higher dimensions as well.
\begin{lemma}\label{lemma-add}
Let $G$ be a graph with a root clique $C^\star$ and let $h$ be
a $C^\star$-clique-sum extendable touching representation of $G$ by comparable boxes in $\mathbb{R}^d$.
Then $G$ has such a representation in $\mathbb{R}^{d'}$ for every $d'\ge d$.
\end{lemma}
\begin{proof}
It clearly suffices to consider the case that $d'=d+1$.
Note that the \textbf{(vertices)} conditions imply that $h(v')\sqsubseteq h(v)$ for every $v'\in V(G)\setminus V(C^\star)$
and $v\in V(C^\star)$.  We extend the representation $h$
by setting $h(v)[d+1] = [0,1]$ for $v\in V(C^\star)$ and $h(v)[d+1] = [0,\frac12]$ for $v\in V(G)\setminus V(C^\star)$.
The clique point $p(C)$ of each clique $C$ is extended by setting $p(C)[d+1] = \frac14$.
It is easy to verify that the resulting representation is $C^\star$-clique-sum extendable.
\end{proof}

The following lemma ensures that clique-sum
Daniel Gonçalves's avatar
Daniel Gonçalves committed
397
398
399
400
extendable representations behave well with respect to full
clique-sums.

\begin{lemma}\label{lem-cs}
401
402
403
404
  Consider two graphs $G_1$ and $G_2$, given with a $C^\star_1$- and a
  $C^\star_2$-clique-sum extendable representations $h_1$ and $h_2$ by comparable boxes
  in $\mathbb{R}^{d_1}$ and $\mathbb{R}^{d_2}$,
  respectively. Let $G$ be the graph obtained by performing a full
Daniel Gonçalves's avatar
Daniel Gonçalves committed
405
  clique-sum of these two graphs on any clique $C_1$ of $G_1$, and on
406
407
  the root clique $C^\star_2$ of $G_2$.  Then $G$ admits a $C^\star_1$-clique
  sum extendable representation $h$ by comparable boxes in
408
  $\mathbb{R}^{\max(d_1,d_2)}$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
409
410
\end{lemma}
\begin{proof}
411
  By Lemma~\ref{lemma-add}, we can assume that $d_1=d_2$; let $d=d_1$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
412
  The idea is to translate (allowing also exchanges of dimensions) and
413
414
415
416
417
418
419
420
421
422
  scale $h_2$ to fit in $h_1^\varepsilon(C_1)$. Consider an $\varepsilon >0$
  sufficiently small so that $h_1^\varepsilon(C_1)$ satisfies all the
  \textbf{(cliques)} conditions, and such that $h_1^\varepsilon(C_1) \sqsubseteq
  h_1(v)$ for any vertex $v\in V(G_1)$.  Let $V(C_1)=\{v_1,\ldots,v_k\}$;
  without loss of generality, we can assume $i_{C_1,v_i}=i$ for $i\in\{1,\ldots,k\}$,
  and thus
  $$h_1(v_i)[j] \cap h_1^\varepsilon(C_1)[j] = \begin{cases}
  \{p_1(C_1)[i]\}&\text{ if $j=i$}\\
  [p_1(C_1)[j],p_1(C_1)[j]+\varepsilon]&\text{ otherwise.}
  \end{cases}$$
Daniel Gonçalves's avatar
Daniel Gonçalves committed
423
424

  Now let us consider $G_2$ and its representation $h_2$. Here the
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
  vertices of $C^\star_2$ are also denoted $v_1,\ldots,v_k$, and
  without loss of generality, the \textbf{(vertices)} conditions are
  satisfied by setting $d_{v_i}=i$ for $i\in\{1,\ldots,k\}$

  We are now ready to define $h$.  For $v\in V(G_1)$, we set $h(v)=h_1(v)$.
  We now scale and translate $h_2$ to fit inside $h_1^\varepsilon(C_1)$.
  That is, we fix $\varepsilon>0$ small enough so that
  \begin{itemize}
  \item the conditions \textbf{(cliques)} hold for $h_1$,
  \item $h_1^\varepsilon(C_1)\subset [0,1)^d$, and
  \item $h_1^\varepsilon(C_1)\sqsubseteq h_1(u)$ for every $u\in V(G_1)$,
  \end{itemize}
  and for each $v\in V(G_2) \setminus V(C^\star_2)$,
  we set $h(v)[i]=p_1(C_1)[i] + \varepsilon h_2(v)[i]$ for $i\in\{1,\ldots,d\}$.
  Note that the condition (v2) for $h_2$ implies $h(v)\subset h_1^\varepsilon(C_1)$.
  Each clique $C$ of $H$ is a clique of $G_1$ or $G_2$.
  If $C$ is a clique of $G_2$, we set $p(C)=p_1(C_1)+\varepsilon p_2(C)$,
  otherwise we set $p(C)=p_1(C)$. In particular, for subcliques of $C_1=C^\star_2$,
  we use the former choice.

  Let us now check that $h$ is a $C^\star_1$-clique sum extendable
446
  representation by comparable boxes. The fact that the boxes are
447
448
449
450
451
  comparable follows from the fact that those of $h_1$ and $h_2$
  are comparable and from the scaling of $h_2$:  By construction both
  $h_1(v) \sqsubseteq h_1(u)$ and $h_2(v) \sqsubseteq h_2(u)$ imply
  $h(v) \sqsubseteq h(u)$, and for any vertex $u\in V(G_1)$ and any
  vertex $v\in V(G_2) \setminus V(C^\star_2)$, we have $h(v) \subset h_1^\varepsilon(C_1) \sqsubseteq h(u)$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
452
453

  We now check that $h$ is a contact representation of $G$. For $u,v
454
  \in V(G_1)$ (resp. $u,v \in V(G_2) \setminus V(C^\star_2)$) it
455
  is clear that $h(u)$ and $h(v)$ have disjoint interiors, and that they
Daniel Gonçalves's avatar
Daniel Gonçalves committed
456
457
  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
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
  V(G_1)$ and a vertex $v \in V(G_2) \setminus V(C^\star_2)$. As
  $h(v)\subset h^\varepsilon(C_1)$, the condition (v2) for $h_1$ implies
  that $h(u)$ and $h(v)$ have disjoint interiors.
  
  Furthermore, if $uv\in E(G)$, then $u\in V(C_1)=V(C^\star_2)$, say $u=v_1$.
  Since $uv\in E(G_2)$, the intervals $h_2(u)[1]$ and $h_2(v)[1]$ intersect,
  and by (v1) and (v2) for $h_2$, we conclude that $h_2(v)[1]=[0,\alpha]$ for some positive $\alpha<1$.
  Therefore, $p_1(C_1)[1]\in h(v)[1]$.  Since $p_1(C_1)\in \bigcap_{x\in V(C_1)} h_1(x)$,
  we have $p_1(C_1)\in h(u)$, and thus $p_1(C_1)[1]\in h(u)[1]\cap h(v)[1]$.
  For $i\in \{2,\ldots,d\}$, note that $i\neq 1=i_{C_1,u}$, and thus
  by (c2) for $h_1$, we have $h_1^\varepsilon(C_1)[i]\subseteq h_1(u)[i]=h(u)[i]$.
  Since $h(v)[i]\subseteq h_1^\varepsilon(C_1)[i]$, it follows that $h(u)$ intersects $h(v)$.

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

  The condition (c2) of $h$ is (for sufficiently small $\varepsilon'>0$)
  inherited from the property (c2) of $h_1$ and $h_2$
  when $C$ is a clique of $G_2$ and $v\in V(G_2)\setminus V(C^\star_2)$, or
  when $C$ is a clique of $G_1$ not contained in $C_1$ and $v\in V(G_1)$.
  If $C$ is a clique of $G_1$ not contained in $C_1$ and $v\in V(G_2)\setminus V(C^\star_2)$,
  then by (c1) for $h_1$ we have $h_1^\varepsilon(C)\cap h_1^\varepsilon(C_1)=\emptyset$,
  and since $h^{\varepsilon'}(C)\subseteq h_1^\varepsilon(C)$ and $h(v)\subseteq h_1^\varepsilon(C_1)$,
  we conclude that $h(v)\cap h^{\varepsilon'}(C)=\emptyset$.
  It remains to consider the case that $C$ is a clique of $G_2$ and $v\in V(G_1)$.
  Note that $h^{\varepsilon'}(C)\subseteq h_1^\varepsilon(C_1)$.
  \begin{itemize}
  \item If $v\not\in V(C_1)$, then by the property (c2) of $h_1$, the box $h(v)=h_1(v)$ is disjoint from $h_1^\varepsilon(C_1)$,
  and thus $h(v)\cap h^{\varepsilon'}(C)=\emptyset$.
  \item Otherwise $v\in V(C_1)=V(C^\star_2)$, say $v=v_1$.
  Note that by (v1), we have $h_2(v)=[-1,0]\times [0,1]^{d-1}$.
  \begin{itemize}
  \item If $v\not\in V(C)$, then by the property (c2) of $h_2$, the box $h_2(v)$ is disjoint from $h_2^\varepsilon(C)$.
  Since $h_2^\varepsilon(C)[i]\subseteq[0,1]=h_2(v)[i]$ for $i\in\{2,\ldots,d\}$,
  it follows that $h_2^\varepsilon(C)[1]\subseteq (0,1)$, and thus $h^{\varepsilon'}(C)[1]\subseteq h_1^\varepsilon(C_1)[1]\setminus\{p(C_1)[1]\}$.
  By (c2) for $h_1$, we have $h(v)[1]\cap h_1^\varepsilon(C_1)[1]=h_1(v)[1]\cap h_1^\varepsilon(C_1)[1]=p(C_1)[1]$,
  and thus $h(v)\cap h^{\varepsilon'}(C)=\emptyset$.
  \item If $v\in V(C)$, then by the property (c2) of $h_2$, the intersection of
  $h_2(v)[1]=[-1,0]$ and $h_2^\varepsilon(C)[1]\subseteq [0,1)$ is the single point $p_2(C)[1]=0$,
  and thus $p(C)[1]=p_1(C_1)[1]$ and $h^{\varepsilon'}(C)[1]=[p_1(C_1)[1],p_1(C_1)[1]+\varepsilon']$.
  Recall that the property (c2) of $h_1$ implies $h(v)[1]\cap h_1^\varepsilon(C_1)[1]=\{p(C_1)[1]\}$,
  and thus $h(v)[1]\cap h^{\varepsilon'}(C)[1]=\{p(C)[1]\}$.  For $i\in\{2,\ldots, d\}$,
  the property (c2) of $h_1$ implies $h_1^\varepsilon(C_1)[i]\subseteq h_1(v)[i]=h(v)[i]$, and
  since $h^{\varepsilon'}(C)[i]\subseteq h_1^\varepsilon(C_1)[i]$, it follows that
  $h^{\varepsilon'}(C)[i]\subseteq h(v)[i]$.
  \end{itemize}
  \end{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
517
518
\end{proof}

519
The following lemma shows that any graphs has a $C^\star$-clique-sum
Daniel Gonçalves's avatar
Daniel Gonçalves committed
520
extendable representation in $\mathbb{R}^d$, for $d= \omega(G) +
521
\ecbdim(G)$ and for any clique $C^\star$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
522
\begin{lemma}\label{lem-apex-cs}
523
524
525
526
  For any graph $G$ and any clique $C^\star$, we have that $G$ admits a
  $C^\star$-clique-sum extendable touching representation by comparabe
  boxes in $\mathbb{R}^d$, for $d = |V(C^\star)| + \ecbdim(G\setminus
  V(C^\star))$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
527
528
529
530
\end{lemma}
\begin{proof}
  The proof is essentially the same as the one of
  Lemma~\ref{lemma-apex}.  Consider a $\emptyset$-clique-sum
531
  extendable touching representation $h'$ of $G\setminus V(C^\star)$ by
Daniel Gonçalves's avatar
Daniel Gonçalves committed
532
  comparable boxes in $\mathbb{R}^{d'}$, with $d' = \cbdim(G\setminus
533
  V(C^\star))$, and let $V(C^\star) = \{v_1,\ldots,v_k\}$. We now construct
Daniel Gonçalves's avatar
Daniel Gonçalves committed
534
  the desired representation $h$ of $G$ as follows. For each vertex
535
536
  $v_i\in V(C^\star)$ let $h(v_i)$ be the box fulfilling (v1) with
  $d_{v_i} = i$. For each vertex $u\in V(G)\setminus V(C^\star)$, if $i\le
Daniel Gonçalves's avatar
Daniel Gonçalves committed
537
538
  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] =
539
  \alpha_i h'(u)[i-k]$, for some $\alpha_i>0$. The values $\alpha_i>0$
540
  are chosen suffciently small so that $h(u)[i] \subset [0,1)$, whenever $u\notin V(C^\star)$. 
541
  We proceed similarly for the clique points. For any
Daniel Gonçalves's avatar
Daniel Gonçalves committed
542
543
544
  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
545
546
547
  \{v_1,\ldots,v_k\}$, as we set $p(C)[i] = \alpha_i p'(C')[i-k]$. 
  
  As $h'(u) \sqsubset h'(v)$ implies that $h(u) \sqsubset h(v)$, and as 
548
549
  $h(u) \sqsubset h(v_i)$, for every $u\in V(G)\setminus V(C^\star)$ and every 
  $v_i \in V(C^\star)$, we have that $h$ is a touching representation by comparable boxes.
550
  By the construction, it is clear that $h$ is a representation of $G$.
551
  For the $C^\star$-clique-sum extendability, it is clear that the (vertices) conditions hold. 
552
  For the (cliques) condition (c1), let us first consider two distinct cliques $C_1$ and $C_2$
553
  of $G$ such that $|V(C_1)| \ge |V(C_2)|$, and let $C'_i=C_i\setminus V(C^\star)$. If $C'_1 = C'_2$,
554
555
556
  there is a vertex $v_i \in V(C_1) \setminus V(C_2)$, and $p(C_1)[i] = 0 \neq 1/4 = p(C_2)[i]$.
  Otherwise, if $C'_1 \neq C'_2$, we have that $p'(C'_1) \neq p'(C'_2)$, which leads to
  $p(C_1) \neq p(C_2)$ by construction.
557
558
559
560
561
562
563
  For the (cliques) condition (c2), let us first consider a vertex $v\in V(G)\setminus V(C^\star)$ and a clique $C$ of $G$ containing $v$.
  In the first dimensions $i \le k$, we always have $h^\varepsilon(C)[i] \subseteq h(v)[i]$. Indeed, if $v_i \in V(C)$ we have 
  $h^\varepsilon(C)[i] \subseteq [0,1/2] = h(v)[i]$ (as in that case $v$ and $v_i$ are adjacent), and if $v_i \notin V(C)$
  we have $h^\varepsilon(C)[i] \subseteq [1/4,1/2] \subseteq h(v)[i]$. Then for the last $d'$ dimensions, by definition of $h'$,
  we have that $h^\varepsilon(C)[i] \subseteq h(v)[i]$ for every $i>k$, except one, 
  for which $h^\varepsilon(C)[i] \cap h(v)[i] = \{p(C)[i]\}$. This completes the first case 
  and we now consider a vertex $v\in V(G)\setminus V(C^\star)$ and a clique $C$ of $G$ not containing $v$. 
564
565
566
567
  As $v\notin V(C')$, there is an hyperplane 
  ${\mathcal H}' = \{ p\in \mathbb{R}^{d'}\ |\ p[i] = c\}$ that separates $p'(C')$ and $h'(v)$.
  This implies that the following hyperplane 
  ${\mathcal H} = \{ p\in \mathbb{R}^{d}\ |\ p[k+i] = \alpha_{k+i} c\}$ separates $p(C)$ and $h(v)$. 
568
569
  Now we consider a vertex $v_i \in V(C^\star)$, and we note that for any clique $C$ containing $v_i$ 
  we have that $h^\varepsilon(C)[i] \cap h(v_i)[i] = [0,\varepsilon]\cap [-1,0] = \{0\}$, and $h^\varepsilon(C)[j] \subseteq [0,1] = h(v_i)[j]$
570
  for any $j\neq i$. For a clique $C$ that does not contain $v_i$ we have that 
571
  $h^\varepsilon(C)[i] \cap h(v_i)[i] \subset (0,1)\cap [-1,0] = \emptyset$. 
572
  Condition (c2) is thus fulfilled and this completes the proof of the lemma. 
Daniel Gonçalves's avatar
Daniel Gonçalves committed
573
574
575
576
577
578
579
580
\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}
581
  Let $h$ be a touching representation by comparable boxes of $G$ in
Daniel Gonçalves's avatar
Daniel Gonçalves committed
582
583
584
585
586
  $\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]$
587
  by $[a-\varepsilon,b+\varepsilon]$ for each vertex $v$ and dimension
Daniel Gonçalves's avatar
Daniel Gonçalves committed
588
589
590
591
592
593
594
595
596
  $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
597
  $h^\varepsilon(C)$. Formally we define $h_2$ as follows.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
598
599
600
601
602
603
  $$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}$$
604
  For any clique $C'$ of $G$, let us denote $c(C')$, the color set
Daniel Gonçalves's avatar
Daniel Gonçalves committed
605
  $\{c(u)\ |\ u\in V(C')\}$, and let $C$ be one of the maximal cliques
606
  containing $C'$. We now set
Daniel Gonçalves's avatar
Daniel Gonçalves committed
607
608
609
610
611
  $$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}
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
  $$
  As $h_2$ is an extension of $h_1$, and as for all the extra dimensions $j$ ($j>d$)
  we have that $2/5 \in h_2(v)[j]$ for every vertex $v$, we have that $h_2$ is an 
  intersection representation of $G$. To prove that it is touching consider two adjacent 
  vertices $u$ and $v$ such that $c(u)<c(v)$, and let us note that $h_2(u)[d+c(u)] = [0,2/5]$
  and $h_2(v)[d+c(u)] = [2/5,4/5]$. By construction, the boxes of $h_1$ are comparable boxes,
  and as $h_2$ is an extension of $h_1$ such that for all the extra dimensions $j$ ($j>d$) 
  the length of $h_2(v)[j]$ is $2/5$ for every vertex $v$, we have that the boxes in $h_2$ are
  comparables boxes.
  For the $\emptyset$-clique-sum extendability, the (vertices) conditions clearly hold. 
  For the (cliques) conditions, let us first note that the points $p_1(C)$, defined for 
  the maximum cliques, are necessarily distinct. This impies that two cliques $C_1$ and $C_2$, 
  which clique points $p_2(C_1)$ and $p_2(C_2)$ are based on distinct maximum cliques, necessarily lead to distinct points.
  In the case that $C_1$ and $C_2$ belong to some maximal clique $C$, we have that $c(C_1) \neq c(C_2)$ 
  and this implies by construction that $p_2(C_1)$ and $p_2(C_2)$ are distinct. Thus (c1) holds.
627
628
  By construction of $h_1$, we have that if $h_2^{\varepsilon}(C')[i] \cap h_2(v)[i]$ is non-empty for every $i\le d$,
  then we have that $h_2^{\varepsilon}(C')[i] \subset h_2(v)[i]$ for every $i\le d$, 
629
630
  and we have that $v$ belongs to some maximal clique $C$ containing $C'$. If $v\notin V(C')$ note that
  $p_2(C')[d+c(v)] = 1/2 \notin[0,2/5]=h_2(v)[d+c(v)]$, while if $v\in V(C')$ we have that
631
632
633
  $h_2^{\varepsilon}(C')[i] \subset [2/5,1/2+\varepsilon] \subset h_2(v)[i]$ for every dimension $i>d$,
  except if $c(v)=i-d$, and in that case $h_2(v)[i] \cap h_2^{\varepsilon}(C')[i] = 
  [0,2/5]\cap[2/5,2/5+\varepsilon] = \{2/5\}$. We thus have that (c2) holds, and this concludes the proof of the lemma.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
634
635
636
637
638
639
640
\end{proof}





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

Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
642
643
Dujmovi{\'c} et al.~\cite{DJM+} proved the following result.
\begin{theorem}\label{thm-prod}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
644
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
645
\begin{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
646
647
\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
648
\end{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
649
650
651
652
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
653
654
\end{theorem}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
655
Let us first bound the comparable box dimension of a graph in terms of
656
its Euler genus.  As paths and $m$-cliques admit touching
Daniel Gonçalves's avatar
Daniel Gonçalves committed
657
658
659
660
661
662
663
664
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
665
\begin{proof}
666
667
668
  Note that there exists a $k$-tree $G'$ having a $k$-clique $C^\star$
  such that $G'\setminus V(C^\star)$ corresponds to $G$.  Let us construct
  a $C^\star$-clique-sum extendable representation of $G'$ and note that
Daniel Gonçalves's avatar
Daniel Gonçalves committed
669
670
671
672
  it induces a $\emptyset$-clique-sum extendable representation of
  $G$.

Note that $G'$ can be obtained by starting with a $(k+1)$-clique
673
containing $C^\star$, and by performing successive full clique-sums of
Daniel Gonçalves's avatar
Daniel Gonçalves committed
674
675
676
$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
677
extendable touching representation by hypercubes. Let us define such
Daniel Gonçalves's avatar
Daniel Gonçalves committed
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
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
702
703
$h^\varepsilon(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^\varepsilon(C)$, and
Daniel Gonçalves's avatar
Daniel Gonçalves committed
704
if $v_i\notin V(C)$ then $h(v_i)[i] = [-1,0]$ if $i\le k$
705
706
707
708
709
710
(resp. $h(v_i)[i] = [0, \frac12]$ if $i= k+1$) and $h^\varepsilon(C)[i] =
[\frac14,\frac14+\varepsilon]$ (resp. $h^\varepsilon(C)[i] =
[\frac34,\frac34+\varepsilon]$). Finally, if $v_i\in V(C)$ we have that
$h(v_i)[i] \cap h^\varepsilon(C)[i] = \{p(C)[i]\}$ and that $h(v_i)[j]
\cap h^\varepsilon(C)[j] = [p(C)[j],p(C)[j]+\varepsilon]$ for any $j\neq i$
and any $\varepsilon <\frac14$.  This concludes the proof of the theorem.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
711
\end{proof}
712
713
714
715
716
717
718
719
Note that actually the bound on the comparable boxes dimension of Theorem~\ref{thm-ktree}
extends to graphs of treewidth $k$. For this, note that the construction in this proof can
provide us with a representation $h$ of any $k$-tree $G$ with hypercubes of distinct sizes. 
Note also that this representation is such that for any two adjacent vertices $u$ and $v$, 
with $h(u) \sqsubset h(v)$ say, the intersection $I = h(u) \cap h(v)$ is a facet of $h(u)$.
Actually $I[i] = h(u)[i]$ for every dimension, except one that we denote $j$. For this 
dimension we have that $I[j]=\{c\}$ for some $c$, and that $h(u)[j]=[c,c+s]$, 
where $s$ is the length of the sides of $h(u)$. In that context to delete an edge $uv$ 
720
one can simply replace $h(u)[j]=[c,c+s]$ with $[c+\varepsilon,c+s]$, for a sufficiently small $\varepsilon$.
721
722
723
724
725
726
One can proceed similarly for any subset of edges, and note that as the hypercubes in $h$ have 
distinct sizes these small perturbations give rise to boxes that are still comparable.
Thus for any treewidth $k$ graph $H$ (that is a subgraph of a $k$-tree $G$) we have $\cbdim(H)\le k+1$.


As every planar graph $G$ has a touching representation by cubes in
Daniel Gonçalves's avatar
Daniel Gonçalves committed
727
728
729
730
731
732
733
734
735
736
737
$\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
738
\end{corollary}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
739
740
741
742
743
744
745
746
747
748
749


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
750
a root clique $C^\star$, they have a $C^\star$-clique-sum extendable
Daniel Gonçalves's avatar
Daniel Gonçalves committed
751
752
753
754
755
756
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
757
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
758
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
759
subpolynomial (though the degree $\log_2 81$ of the polynomial established in Corollary~\ref{cor-genus}
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
760
761
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
762
It would be interesting to prove Theorem~\ref{thm-minor} without using the structure theorem.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
763

Zdenek Dvorak's avatar
Zdenek Dvorak committed
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
\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$
Daniel Gonçalves's avatar
Daniel Gonçalves committed
790
if for every $x\in B$, there exists a translation $A'$ of $A$ such that $x\in A'$ and $\vol(A'\cap B)\ge \tfrac{1}{s}\vol(A)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
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}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
\note{TO REMOVE if we reintroduce tree decomposition earlier !}

\note{Let us recall some notions about treewidth.
  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, such that
\begin{itemize}
\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$.
\end{itemize}
For nodes $x,y\in V(T)$, we write $x\preceq y$ if $x=y$ or $x$ is a descendant of $y$ in $T$.
%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$.
%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
The \emph{width} of the tree decomposition is the maximum of the sizes of the bags minus $1$.  The \emph{treewidth} of a graph is the minimum
of the widths of its tree decompositions.}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
830
831
832
\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$
Daniel Gonçalves's avatar
Daniel Gonçalves committed
833
is fractionally treewidth-fragile, with a function $f(k) = O_{t,s,d}\bigl(k^{d}\bigr)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
834
835
836
837
838
\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$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
839
840
Let us define $\ell_{i,j}\in \mathbb{R}^+$ for $i=1,\ldots, n$ and $j\in\{1,\ldots,d\}$ as an approximation of $|ksd\omega(v_i)[j]|$ such that $\ell_{i-1,j} / \ell_{i,j}$ is a positive integer. Formally
it is defined as follows.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
841
842
\begin{itemize}
\item Let $\ell_{1,j}=ksd|\omega(v_1)[j]|$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
843
844
845
846
847
848
\item For $i=2,\ldots, n$, let $\ell_{i,j} = \ell_{i-1,j}$, if
  $\ell_{i-1,j} < ksd|\omega(v_i)[j]|$, and otherwise let
  $\ell_{i,j}$ be lowest fraction of $\ell_{i-1,j}$ that is
  greater than $ksd|\omega(v_i)[j]|$, formally $\ell_{i,j} =
  \min\{\ell_{i-1,j}/b \ |\ b\in
  \mathbb{N}^+ \text{ and } \ell_{i-1,j}/b \ge ksd|\omega(v_i)[j]|\}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
849
\end{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
Let the real $x_j\in [0,\ell_{1,j}]$ be chosen uniformly at random,
and let $\HH^i_j$ be the set of hyperplanes in $\mathbb{R}^d$
consisting of the points whose $j$-th coordinate is equal to
$x_j+m\ell_{i,j}$ for some $m\in\mathbb{Z}$. As $\ell_{i,j}$ is a
multiple of $\ell_{i',j}$ whenever $i\le i'$, we have that $\HH^i_j
\subseteq \HH^{i'}_j$ whenever $i\le i'$.  For $i\in\{1,\ldots,n\}$,
the \emph{$i$-grid} is $\HH^i=\bigcup_{j=1}^d \HH^i_j$, and we let the
$0$-grid $\HH^0=\emptyset$.  Similarly as above we have that $\HH^i
\subseteq \HH^{i'}$ whenever $i\le i'$.

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^a$,
that is such that $x_j+m\ell_{a,j}\in \omega(v_a)[j]$, for some
$j\in\{1,\ldots,d\}$ and some $m\in \mathbb{Z}$.  First, let us argue
that $\text{Pr}[v_a\in X]\le 1/k$.  Indeed, the set $[0,\ell_{1,j}]\cap \bigcup_{m\in\mathbb{Z}} (\omega(v_a)[j]-m\ell_{a,j})$
Zdenek Dvorak's avatar
Zdenek Dvorak committed
865
has measure $\tfrac{\ell_{1,j}}{\ell_{a,j}}\cdot |\omega(v_a)[j]|$, implying that for fixed $j$, this happens with probability
Daniel Gonçalves's avatar
Daniel Gonçalves committed
866
867
$|\omega(v_a)[j]|/\ell_{a,j}$.  Let $a'$ be the largest integer such
that $a'\le a$ and $\ell_{a',j} < \ell_{a'-1,j}$ if such an index exists,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
868
869
870
871
872
873
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$.

Daniel Gonçalves's avatar
Daniel Gonçalves committed
874
875
Let us now bound the treewidth of $G-X$.  
For $a\ge 0$, an \emph{$a$-cell} is a maximal connected subset of $\mathbb{R}^d\setminus (\cup_{H\in \HH^a} H)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
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]|$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
896
897
898
\item If $a>1$ and $\ell_{a,j}=\ell_{a-1,j}$, then $\ell_{a,j}=\ell_{a-1,j}<2ksd|\omega(v_a)[j]|$ (otherwise $\ell_{a,j}=\ell_{a-1,j}/b$ for some integer $b\ge 2$).
\item If $a>1$ and $\ell_{a,j} < \ell_{a-1,j}$, then $\ell_{a-1,j}\ge b\times ksd|\omega(v_a)[j]|$ for some integers $b\ge 2$. Now let $b$ be the greatest such integer (that is such that $\ell_{a-1,j} < (b+1)\times ksd|\omega(v_a)[j]|$) and note that
$$\ell_{a,j}=\frac{\ell_{a-1,j}}{b}<\tfrac{b+1}{b}ksd|\omega(v_a)[j]|<\tfrac{3}{2}ksd|\omega(v_a)[j]|.$$
Zdenek Dvorak's avatar
Zdenek Dvorak committed
899
900
901
\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)$,
Daniel Gonçalves's avatar
Daniel Gonçalves committed
902
903
there exists a translation $B_i$ of $\omega(v_a)$ that intersects $C\cap \iota(v_i)$ and such that $\vol(B_i\cap\iota(v_i))\ge \tfrac{1}{s}\vol(\omega(v_a))$.
Note that as $B_i$ intersects $C$, we have that $B_i\subseteq C'$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
904
905
906
907
908
909
910
911
912
913
914
915
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}

916
917
918
919
920
921
922
923
924
925
926
927
928
929
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
930
931
932
\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
933

Zdenek Dvorak's avatar
Zdenek Dvorak committed
934
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
935
936
937
\bibliography{data}

\end{document}