comparable-box-dimension.tex 63.7 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
\documentclass[a4paper,USenglish,cleveref,autoref,thm-restate]{socg-lipics-v2021}
\bibliographystyle{plainurl}

\title{On comparable box dimension}

\titlerunning{On comparable box dimension}

\author{Zden\v{e}k Dvo\v{r}\'ak}{Charles University, Prague, Czech Republic}{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.}
\author{Daniel Gon\c{c}alves}{LIRMM, Université de Montpellier, CNRS, Montpellier, France}{goncalves@lirmm.fr}{}{Supported by the ANR grant GATO ANR-16-CE40-0009.}
\author{Abhiruk Lahiri}{Charles University, Prague, Czech Republic}{abhiruk@iuuk.mff.cuni.cz}{}{Partially supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.}
\author{Jane Tan}{Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom}{jane.tan@maths.ox.ac.uk}{}{}
Torsten Ueckerdt's avatar
Torsten Ueckerdt committed
12
\author{Torsten Ueckerdt}{Karlsruhe Institute of Technology, Karlsruhe, Germany}{torsten.ueckerdt@kit.edu}{}{}
13

Torsten Ueckerdt's avatar
Torsten Ueckerdt committed
14
\authorrunning{Z. Dvo\v{r}\'ak, D. Gon\c{c}alves, A. Lahiri, J. Tan, and T. Ueckerdt}
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

\Copyright{Zden\v{e}k Dvo\v{r}\'ak Daniel Gon\c{c}alves, Abhiruk Lahiri, Jane Tan and Torsten Ueckerdt}

\ccsdesc[500]{Theory of computation~Computational geometry}
\ccsdesc[500]{Mathematics of computing~Graphs and surfaces}

\keywords{geometric graphs, minor-closed graph classes, treewidth fragility}

%\category{} %optional, e.g. invited paper

%\relatedversion{} %optional, e.g. full version hosted on arXiv, HAL, or other respository/website
%\relatedversiondetails[linktext={opt. text shown instead of the URL}, cite=DBLP:books/mk/GrayR93]{Classification (e.g. Full Version, Extended Version, Previous Version}{URL to related version} %linktext and cite are optional

%\supplement{}%optional, e.g. related research data, source code, ... hosted on a repository like zenodo, figshare, GitHub, ...
%\supplementdetails[linktext={opt. text shown instead of the URL}, cite=DBLP:books/mk/GrayR93, subcategory={Description, Subcategory}, swhid={Software Heritage Identifier}]{General Classification (e.g. Software, Dataset, Model, ...)}{URL to related version} %linktext, cite, and subcategory are optional

%\funding{(Optional) general funding statement \dots}%optional, to capture a funding statement, which applies to all authors. Please enter author specific funding statements as fifth argument of the \author macro.

\acknowledgements{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.}%optional

%\nolinenumbers %uncomment to disable line numbering

%\hideLIPIcs  %uncomment to remove references to LIPIcs series (logo, DOI, ...), e.g. when preparing a pre-final version to be uploaded to arXiv or another public repository

%Editor-only macros:: begin (do not touch as author)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\EventEditors{John Q. Open and Joan R. Access}
\EventNoEds{2}
\EventLongTitle{42nd Conference on Very Important Topics (CVIT 2016)}
\EventShortTitle{CVIT 2016}
\EventAcronym{CVIT}
\EventYear{2016}
\EventDate{December 24--27, 2016}
\EventLocation{Little Whinging, United Kingdom}
\EventLogo{}
\SeriesVolume{42}
\ArticleNo{23}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Zdenek Dvorak's avatar
Zdenek Dvorak committed
53
54
55
56
57
58
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{colonequals}
\usepackage{epsfig}
Jane Tan's avatar
Jane Tan committed
59
\usepackage{tikz}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
60
61
\usepackage{url}
\newcommand{\GG}{{\cal G}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
62
\newcommand{\HH}{{\cal H}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
63
64
65
66
67
68
69
70
71
72
73
\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
74
\newcommand{\ecbdim}{\brm{dim}^{ext}_{cb}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
75
76
\newcommand{\tw}{\brm{tw}}
\newcommand{\vol}{\brm{vol}}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
77
78
79
80
81
82
83
%%%%%


\begin{document}
\maketitle

\begin{abstract}
84
85
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
86
87
88
89
$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
90
91
92
93
\end{abstract}

\section{Introduction}

94
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$}
95
if there exists a function $f:V(G)\to \OO$ (called a \emph{touching representation by objects from $\OO$})
96
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
97
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$.
98
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
99

Jane Tan's avatar
Jane Tan committed
100
101
102
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.
103
104
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
105
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$
106
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
107
Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} noticed that this issue disappears if we forbid such a combination of
108
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$.
109
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
110
A \emph{touching representation by comparable boxes} of a graph $G$ is a touching representation $f$ by boxes
111
112
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$.
113
Let us remark that the comparable box dimension of every graph $G$ is at most $|V(G)|$, see Section~\ref{sec-vertad} for details.
114
Then for a class $\GG$ of graphs, let $\cbdim(\GG)\colonequals\sup\{\cbdim(G):G\in\GG\}$. Note that $\cbdim(\GG)=\infty$ if the
Zdenek Dvorak's avatar
Zdenek Dvorak committed
115
116
117
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,
118
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
119
numbers, which implies that $\GG$ has strongly sublinear separators.  They also provided an example showing
120
121
that for many functions $h$, the class of graphs with strong coloring numbers bounded by $h$ has infinite
comparable box dimension\footnote{In their construction $h(r)$ has to be at least 3, and has to tend to $+\infty$.}. Dvo\v{r}\'ak et al.~\cite{wcolig}
122
proved that graphs of comparable box dimension $3$ have exponential weak coloring numbers, giving the
123
first natural graph class with polynomial strong coloring numbers and superpolynomial weak coloring numbers
Zdenek Dvorak's avatar
Zdenek Dvorak committed
124
125
126
127
128
129
130
131
132
133
134
(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.
135
This gives arbitrarily precise approximation algorithms for all monotone maximization problems that are
Zdenek Dvorak's avatar
Zdenek Dvorak committed
136
137
138
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
139
\section{Parameters}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
140

141
142
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
143
\begin{lemma}\label{lemma-cliq}
144
For any graph $G$, we have $\omega(G)\le 2^{\cbdim(G)}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
145
146
\end{lemma}
\begin{proof}
147
148
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
149
150
151
152
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
153
154
155
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
156
\end{proof}
157
158
159
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
160

161
162
163
164
165
166
167
In the following we consider the chromatic number $\chi(G)$, and two
of its variants.  An \emph{acyclic coloring} (resp. \emph{star coloring}) of a graph $G$ is a proper
coloring such that any two color classes induce a forest (resp. star forest, i.e., a
graph not containing any 4-vertex path).  The \emph{acyclic chromatic number} $\chi_a(G)$ (resp. \emph{star chromatic
  number} $\chi_s(G)$) of $G$ is the minimum number of colors in an acyclic (resp. star)
coloring of $G$.  We will need the fact that all the variants of the chromatic number
are at most exponential in the comparable box dimension; this follows
168
from~\cite{subconvex}, although we include an argument to make the
Daniel Gonçalves's avatar
Daniel Gonçalves committed
169
dependence clear.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
170
\begin{lemma}\label{lemma-chrom}
171
For any graph $G$ we have $\chi(G)\le 3^{\cbdim(G)}$, $\chi_a(G)\le 5^{\cbdim(G)}$ and $\chi_s(G) \le 2\cdot 9^{\cbdim(G)}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
172
173
\end{lemma}
\begin{proof}
174
175
176
We focus on the star chromatic number and note that the chromatic number and the acyclic chromatic number may be bounded similarly.
Suppose that $G$ has comparable box dimension $d$ witnessed by a representation $f$, and let $v_1, \ldots, v_n$
be the vertices of $G$ written so that $\vol(f(v_1)) \geq \ldots \geq \vol(f(v_n))$.
177
178
Equivalently, we have $f(v_i)\sqsubseteq f(v_j)$ whenever $i>j$. Now define a greedy coloring $c$ so that $c(v_i)$ is
the smallest color such that $c(v_i)\neq c(v_j)$ for any $j<i$ for which either $v_jv_i\in E(G)$ or there
179
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.
180
181

It remains to bound the number of colors used. Suppose we are coloring $v_i$. We shall bound the number of vertices
182
183
$v_j$ such that $j<i$ and such that 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)$
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)/\vol(f(v_i))-1=5^d-1$.
184

Zdenek Dvorak's avatar
Zdenek Dvorak committed
185
186
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)$
187
is at most $(3^d-1)^2$. This means that when choosing the color of $v_i$ greedily, we only need to avoid colors of at most $(5^d-1) + (3^d-1) + (3^d-1)^2$ vertices, so $2\cdot 9^d$ colors suffice.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
188
189
\end{proof}

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
\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
216
217
218
219

\section{Operations}

It is clear that given a touching representation of a graph $G$, one
220
easily obtains a touching representation by boxes of an induced
Daniel Gonçalves's avatar
Daniel Gonçalves committed
221
222
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
223
consider other basic operations on graphs. In the following, to describe
Torsten Ueckerdt's avatar
Torsten Ueckerdt committed
224
the boxes, we are going to use the Cartesian product $\times$ defined among boxes ($A\times B$ is the box whose projection on the first dimensions gives the box $A$, while the projection on the remaining dimensions gives the box $B$) or we are going to provide its projections for every dimension ($A[i]$ is the interval obtained from projecting $A$ on its $i^\text{th}$ dimension).
Daniel Gonçalves's avatar
Daniel Gonçalves committed
225

226
\subsection{Vertex addition}\label{sec-vertad}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247

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
248
249
250
251
252
253
254
255
256
257
258
259
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
260
261
262

\begin{lemma}\label{lemma-sp}
  Consider a graph $H$ having a touching representation $h$ in
263
264
265
  $\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
266
267
268
\end{lemma}
\begin{proof}
  The proof simply consists in taking a product of the two
269
270
  representations.  Indeed, consider a touching respresentation $g$ of $G$ by 
  comparable boxes in $\mathbb{R}^{d_G}$, with
271
  $d_G=\cbdim(G)$, and the representation $h$ of $H$.  Let us define a
Daniel Gonçalves's avatar
Daniel Gonçalves committed
272
273
  representation $f$ of $G\boxtimes H$ in $\mathbb{R}^{d_G+d_H}$ as
  follows.
274
  \[f((u,v))[i]=\begin{cases}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
275
  g(u)[i]&\text{ if $i\le d_G$}\\
276
  h(v)[i-d_G]&\text{ if $i > d_G$}
277
  \end{cases}\]
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
  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
300
301
302
\end{proof}


303
\subsection{Taking a subgraph}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
304

305
306
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
307
308
309
310
311
312
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
313
\begin{lemma}\label{lemma-subg}
314
If $G$ is a subgraph of a graph $G'$, then $\cbdim(G)\le \cbdim(G')+\frac12 \chi^2_s(G')$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
315
316
317
\end{lemma}
\begin{proof}
As we can remove the boxes that represent the vertices, we can assume $V(G')=V(G)$.
318
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
319
320
be a star coloring of $G'$ using colors $\{1,\ldots,c\}$, where $c=\chi_s(G')$.

321
322
323
324
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
325
326
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
327
\[h(v)[d_{i,j}]=\begin{cases}
328
329
330
[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.}
331
\end{cases}\]
332
Note that the boxes in this extended representation are comparable,
Zdenek Dvorak's avatar
Zdenek Dvorak committed
333
334
as in the added dimensions, all the boxes have size $1$.

335
336
337
338
339
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
340
341

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
342
$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
343
344
$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$.

345
Consequently, $h$ is a touching representation of $G$ by comparable boxes in dimension $d+\binom{c}{2}\le d+c^2 /2$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
346
347
348
349
350
\end{proof}

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

\begin{corollary}\label{cor-subg}
351
If $G$ is a subgraph of a graph $G'$, then $\cbdim(G)\le \cbdim(G')+2\cdot 81^{\cbdim(G')}\le 3\cdot 81^{\cbdim(G')}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
352
353
\end{corollary}

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
357

Daniel Gonçalves's avatar
Daniel Gonçalves committed
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
\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}
376
377
378
379
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
380
\begin{itemize}
381
\item[] {\bf(vertices)} For each $u\in V(C^\star)$, there exists a dimension $d_u$,
382
  such that:
383
384
  \subitem\emph{(v0)} $d_u\neq d_{u'}$ for distinct $u,u'\in V(C^\star)$,
  \subitem\emph{(v1)} each vertex $u\in V(C^\star)$ satisfies $h(u)[d_u] = [-1,0]$ and
385
    $h(u)[i] = [0,1]$ for any dimension $i\neq d_u$, and
386
  \subitem\emph{(v2)} each vertex $v\notin V(C^\star)$ satisfies $h(v) \subset [0,1)^d$.
387
\item[] {\bf(cliques)} For every clique $C$ of $G$, there exists
388
  a point $p(C)\in [0,1)^d\cap \left( \bigcap_{v\in V(C)} h(v) \right)$
389
  such that, defining the \emph{clique box} $h^\varepsilon(C)$
390
  by setting $h^\varepsilon(C)[i] = [p(C)[i],p(C)[i]+\varepsilon]$ for every dimension
391
  $i$, the following conditions are satisfied:
392
393
%  \begin{itemize}
  \subitem\emph{(c1)} For any two cliques $C_1\neq C_2$, $h^\varepsilon(C_1) \cap
394
    h^\varepsilon(C_2) = \emptyset$ (equivalently, $p(C_1) \neq p(C_2)$).
395
  \subitem\emph{(c2)} A box $h(v)$ intersects $h^\varepsilon(C)$ if and only if
Daniel Gonçalves's avatar
Daniel Gonçalves committed
396
    $v\in V(C)$, and in that case their intersection is a facet of
397
398
    $h^\varepsilon(C)$ incident to $p(C)$.  That is, there exists a dimension $i_{C,v}$
    such that for each dimension $j$,
399
    \[h(v)[j]\cap h^\varepsilon(C)[j] = \begin{cases}
400
401
    \{p(C)[i_{C,v}] \}&\text{if $j=i_{C,v}$}\\
    [p(C)[j],p(C)[j]+\varepsilon]&\text{otherwise.}
402
    \end{cases}\]
403
%  \end{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
404
405
\end{itemize}
\end{definition}
406
Note that the root clique can be empty, that is the
Daniel Gonçalves's avatar
Daniel Gonçalves committed
407
408
empty subgraph with no vertices.  In that case the clique is denoted
$\emptyset$.  Let $\ecbdim(G)$ be the minimum dimension such that $G$
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
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}

428
429
The following lemma ensures that clique-sum extendable representations
behave well with respect to full clique-sums.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
430
\begin{lemma}\label{lem-cs}
431
432
433
434
  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
435
  clique-sum of these two graphs on any clique $C_1$ of $G_1$, and on
436
437
  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
438
  $\mathbb{R}^{\max(d_1,d_2)}$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
439
\end{lemma}
440
441
442
The proof is in the appendix, but the idea is to translate (allowing
also exchanges of dimensions) and scale $h_2$ to fit in
$h_1^\varepsilon(C_1)$.
443
444
The following lemma enables us to pick the root clique at the expense of increasing
the dimension by $\omega(G)$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
445
\begin{lemma}\label{lem-apex-cs}
446
447
448
  For any graph $G$ and any clique $C^\star$, the graph $G$ admits a
  $C^\star$-clique-sum extendable touching representation by comparable
  boxes in $\mathbb{R}^d$, for $d = |V(C^\star)| + \ecbdim(G\setminus V(C^\star))$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
449
\end{lemma}
450
451
  The proof is also in the appendix, but it essentially the same as the one of
  Lemma~\ref{lemma-apex}.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
452
453
454
455
456
457
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}
458
  Let $h$ be a touching representation of $G$ by comparable boxes in
Daniel Gonçalves's avatar
Daniel Gonçalves committed
459
460
461
  $\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
462
  sufficiently small real $\alpha>0$ we increase each box in $h$ by
Daniel Gonçalves's avatar
Daniel Gonçalves committed
463
  $2\alpha$ in every dimension, that is we replace $h(v)[i] = [a,b]$
464
465
466
467
468
469
470
471
  by $[a-\alpha,b+\alpha]$ for each vertex $v$ and dimension
  $i$. We choose $\alpha$ sufficiently small so that the boxes representing
  non-adjacent vertices remain disjoint, and thus the resulting representation $h_1$ is
  an intersection representation of the same graph $G$.  Moreover, observe that
  for every clique $C$ of $G$, the intersection $I_C=\bigcap_{v\in V(C)} h_1(v)$ is
  a box with non-zero edge lengths. For any clique $C$ of $G$, let
  $p_1(C)$ be a point in the interior of $I_C$ different from the points
  chosen for all other cliques.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
472
473
474

  Now we add $\chi(G)$ dimensions to make the representation touching
  again, and to ensure some space for the clique boxes
475
  $h^\varepsilon(C)$. Formally we define $h_2$ as follows.
476
  \[h_2(u)[i]=\begin{cases}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
477
  h_1(u)[i]&\text{ if $i\le d$}\\
478
479
  [1/5,3/5]&\text{ if $i>d$ and $c(u) < i-d$}\\
  [0,2/5]&\text{ if $i>d$ and $c(u) = i-d$}\\
Daniel Gonçalves's avatar
Daniel Gonçalves committed
480
  [2/5,4/5]&\text{ otherwise (if $c(u) > i-d > 0$)}
481
  \end{cases}\]
482
483
  For any clique $C$ of $G$, let $c(C)$ denote the color set $\{c(u)\ |\ u\in V(C)\}$.
  We now set
484
  \[p_2(C)[i]=\begin{cases}
485
  p_1(C)[i] &\text{ if $i\le d$}\\
486
  2/5 &\text{ if $i>d$ and $i-d \in c(C)$}\\
Daniel Gonçalves's avatar
Daniel Gonçalves committed
487
488
  1/2 &\text{ otherwise}
  \end{cases}
489
  \]
490
491
492
493
  As $h_2$ is an extension of $h_1$, and as in each dimension $j>d$,
  $h_2(v)[j]$ is an interval of length $2/5$ containing the point $2/5$ for every vertex $v$,
  we have that $h_2$ is an intersection representation of $G$ by comparable boxes.
  To prove that it is touching consider two adjacent 
494
  vertices $u$ and $v$ such that $c(u)<c(v)$, and let us note that $h_2(u)[d+c(u)] = [0,2/5]$
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
  and $h_2(v)[d+c(u)] = [2/5,4/5]$. 
  
  For the $\emptyset$-clique-sum extendability, the \textbf{(vertices)} conditions are void.
  For the \textbf{(cliques)} conditions, since $p_1$ is chosen to be injective, the mapping $p_2$
  is injective as well, implying that (c1) holds.
 
  Consider now a clique $C$ in $G$ and a vertex $v\in V(G)$.  If $c(v)\not\in c(C)$, then
  $h_2(v)[c(v)+d]=[0,2/5]$ and $p_2(C)[c(v)+d]=1/2$, implying that $h_2^{\varepsilon}(C)\cap h_2(v)=\emptyset$.
  If $c(v)\in c(C)$ but $v\not\in V(C)$, then letting $v'\in V(C)$ be the vertex of color $c(v)$,
  we have $vv'\not\in E(G)$, and thus $h_1(v)$ is disjoint from $h_1(v')$.  Since $p_1(C)$ is contained
  in the interior of $h_1(v')$, it follows that $h_2^{\varepsilon}(C)\cap h_2(v)=\emptyset$.
  Finally, suppose that $v\in C$.  Since $p_1(C)$ is contained in the interior of $h_1(v)$,
  we have $h_2^{\varepsilon}(C)[i] \subset h_2(v)[i]$ for every $i\le d$.  For $i>d$ distinct from $d+c(v)$,
  we have $p_2^{\varepsilon}(C)[i]\in\{2/5,1/2\}$ and $[2/5,3/5]\subseteq h_2(v)[i]$, and thus
  $h_2^{\varepsilon}(C)[i] \subset h_2(v)[i]$.  For $i=d+c(v)$, we have $p_2^{\varepsilon}(C)[i]=2/5$
  and $h_2(v)[i]=[0,2/5]$, and thus $h_2^{\varepsilon}(C)[i] \cap h_2(v)[i]=\{p_2^{\varepsilon}(C)[i]\}$.
  Therefore, (c2) holds.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
512
513
514
\end{proof}


515
516
Together, the lemmas from this section show that comparable box dimension is almost preserved by
full clique-sums.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
517

518
519
\begin{corollary}
\label{cor-csum}
520
521
Let $\GG$ be a class of graphs of chromatic number at most $k$.  If $\GG'$ is the class
of graphs obtained from $\GG$ by repeatedly performing full clique-sums, then
522
\[\cbdim(\GG')\le \cbdim(\GG) + 2k.\]
523
524
525
526
527
528
529
530
531
532
533
\end{corollary}
\begin{proof}
Suppose a graph $G$ is obtained from $G_1, \ldots, G_m\in\GG$ by performing full clique-sums.
Without loss of generality, the labelling of the graphs is chosen so that we first
perform the full clique-sum on $G_1$ and $G_2$, then on the resulting graph and $G_3$, and so on.
Let $C^\star_1=\emptyset$ and for $i=2,\ldots,m$, let $C^\star_i$ be the root clique of $G_i$ on which it is
glued in the full clique-sum operation.  By Lemmas~\ref{lem-ecbdim-cbdim} and \ref{lem-apex-cs},
$G_i$ has a $C_i^\star$-clique-sum extendable touching representation by comparable boxes in $\mathbb{R}^d$,
where $d=\cbdim(\GG) + 2k$.  Repeatedly applying Lemma~\ref{lem-cs}, we conclude that
$\cbdim(G)\le d$.
\end{proof}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
534

535
536
537
538
539
540
By Lemmas~\ref{lemma-chrom} and \ref{lemma-subg}, this gives the following bounds.
\begin{corollary}\label{cor-csump}
Let $\GG$ be a class of graphs of comparable box dimension at most $d$.
\begin{itemize}
\item The class $\GG'$ of graphs obtained from $\GG$ by repeatedly performing full clique-sums
has comparable box dimension at most $d + 2\cdot 3^d$.
541
542
\item The closure of $\GG'$ by taking subgraphs
has comparable box dimension at most $1250^d$.
543
544
545
\end{itemize}
\end{corollary}
\begin{proof}
546
The former bound directly follows from Corollary~\ref{cor-csum} and the bound on the chromatic number
547
548
549
550
551
552
553
554
555
556
557
558
559
from Lemma~\ref{lemma-chrom}.  For the latter one, we need to bound the star chromatic number of $\GG'$.
Suppose a graph $G$ is obtained from $G_1, \ldots, G_m\in\GG$ by performing full clique-sums.
For $i=1,\ldots, m$, suppose $G_i$ has an acyclic coloring $\varphi_i$ by at most $k$ colors.
Note that the vertices of any clique get pairwise different colors, and thus by permuting the colors,
we can ensure that when we perform the full clique-sum, the vertices that are identified have the same
color.  Hence, we can define a coloring $\varphi$ of $G$ such that for each $i$, the restriction of
$\varphi$ to $V(G_i)$ is equal to $\varphi_i$.  Let $C$ be the union of any two color classes of $\varphi$.
Then for each $i$, $G_i[C\cap V(G_i)]$ is a forest, and since $G[C]$ is obtained from these graphs
by full clique-sums, $G[C]$ is also a forest.  Hence, $\varphi$ is an acyclic coloring of $G$
by at most $k$ colors.  By~\cite{albertson2004coloring}, $G$ has a star coloring by at most $2k^2-k$ colors.
Hence, Lemma~\ref{lemma-chrom} implies that $\GG'$ has star chromatic number at most $2\cdot 25^d - 5^d$.
The bound on the comparable box dimension of subgraphs of graphs from $\GG'$ then follows from Lemma~\ref{lemma-subg}.
\end{proof}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
560
561

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

563
564
565
A \emph{$k$-tree} is any graph obtained by repeated full clique-sums on cliques of size $k$ from cliques of size at most $k+1$.
A \emph{$k$-tree-grid} is a strong product of a $k$-tree and a path.
An \emph{extended $k$-tree-grid} is a graph obtained from a $k$-tree-grid by adding at most $k$ apex vertices.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
566
567
Dujmovi{\'c} et al.~\cite{DJM+} proved the following result.
\begin{theorem}\label{thm-prod}
568
Any graph $G$ is a subgraph of the strong product of a $k$-tree-grid and $K_m$, where
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
569
\begin{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
570
571
\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
572
\end{itemize}
573
574
575
Moreover, for every $t$, there exists an integer $k$ such that any
$K_t$-minor-free graph $G$ is a subgraph of a graph obtained by repeated clique-sums
from extended $k$-tree-grids.
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
576
577
\end{theorem}

Daniel Gonçalves's avatar
Daniel Gonçalves committed
578
Let us first bound the comparable box dimension of a graph in terms of
579
its Euler genus.  As paths and $m$-cliques admit touching
Daniel Gonçalves's avatar
Daniel Gonçalves committed
580
581
representations with hypercubes of unit size in $\mathbb{R}^{1}$ and
in $\mathbb{R}^{\lceil \log_2 m \rceil}$ respectively, by
582
583
Lemma~\ref{lemma-sp} it suffices to bound the comparable box
dimension of $k$-trees.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
584
585
586
587

\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
588
\begin{proof}
589
590
591
592
593
594
595
596
597
598
  Let $H$ be a complete graph with $k+1$ vertices and let $C^\star$ be
  a clique of size $k$ in $H$.  By Lemma~\ref{lem-cs}, it suffices
  to show that $H$ has a $C^\star$-clique-sum extendable touching representation
  by hypercubes in $\mathbb{R}^{k+1}$.  Let $V(C^\star)=\{v_1,\ldots,v_k\}$.
  We construct the representation $h$ so that (v1) holds with $d_{v_i}=i$ for each $i$;
  this uniquely determines the hypercubes $h(v_1)$, \ldots, $h(v_k)$.
  For the vertex $v_{k+1} \in V(H)\setminus V(C^\star)$, we set $h(v_{k+1})=[0,1/2]^{k+1}$.
  This ensures that the \textbf{(vertices)} conditions holds.

  For the \textbf{(cliques)} conditions, let us set
Daniel Gonçalves's avatar
Daniel Gonçalves committed
599
600
the point $p(C)$ for every clique $C$ as follows:
\begin{itemize}
601
602
  \item $p(C)[i] = 0 $ for every $i\le k$ such that $v_i\in C$
  \item $p(C)[i] = \frac14 $ for every $i\le k$ such that $v_i\notin C$
Daniel Gonçalves's avatar
Daniel Gonçalves committed
603
604
605
  \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}
606
607
By construction, it is clear that for each vertex $v\in V(H)$, $p(C) \in h(v)$ if and only if
$v\in V(C)$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
608
609

For any two distinct cliques $C_1$ and $C_2$ the points $p(C_1)$ and
610
611
612
613
614
615
616
617
618
619
620
621
$p(C_2)$ are distinct.  Indeed, by symmetry we can assume that for some $i$,
we have $v_i\in V(C_1)\setminus V(C_2)$, and this implies that $p(C_1)[i] < p(C_2)[i]$.
Hence, the condition (v1) holds.

Consider now a vertex $v_i$ and a clique $C$.  As we observed before, if $v_i\not\in V(C)$,
then $p(C) \not\in h(v_i)$, and thus $h^\varepsilon(C)$ and $h(v_i)$ are disjoint (for sufficiently small $\varepsilon>0$).
If $v_i\in C$, then the definitions ensure that $p(C)[i]$ is equal to the maximum of $h(v_i)[i]$,
and that for $j\neq i$, $p(C)[j]$ is in the interior of $h(v_i)[j]$, implying
$h(v_i)[j] \cap h^\varepsilon(C)[j] = [p(C)[j],p(C)[j]+\varepsilon]$ for sufficiently small $\varepsilon>0$.
\end{proof}
The \emph{treewidth} $\tw(G)$ of a graph $G$ is the minimum $k$ such that $G$ is a subgraph of a $k$-tree.
Note that actually the bound on the comparable box dimension of Theorem~\ref{thm-ktree}
622
extends to graphs of treewidth at most $k$ (see the proof in the appendix).
623
624
625
\begin{corollary}\label{cor-tw}
Every graph $G$ satisfies $\cbdim(G)\le\tw(G)+1$.
\end{corollary}
626
627

As every planar graph $G$ has a touching representation by cubes in
628
629
$\mathbb{R}^3$~\cite{felsner2011contact}, we have that $\cbdim(G)\le 3$.
For the graphs with higher Euler genus we can also derive upper
Daniel Gonçalves's avatar
Daniel Gonçalves committed
630
631
632
633
634
635
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'$
636
of $G$ such that $\cbdim(G')\le 6+\lceil \log_2 \max(2g,3)\rceil$.
637
Consequently, \[\cbdim(G)\le 3\cdot 81^7 \cdot \max(2g,3)^{\log_2 81}.\]
Zdenek Dvorak's avatar
Minors.    
Zdenek Dvorak committed
638
\end{corollary}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
639

640
641
642
643
644
645
Similarly, we can deal with proper minor-closed classes.
\begin{proof}[Proof of Theorem~\ref{thm-minor}]
Let $\GG$ be a proper minor-closed class.  Since $\GG$ is proper, there exists $t$ such that $K_t\not\in \GG$.
By Theorem~\ref{thm-prod}, there exists $k$ such that every graph in $\GG$ is a subgraph of a graph obtained by repeated clique-sums
from extended $k$-tree-grids.  As we have seen, $k$-tree-grids have comparable box dimension at most $k+2$,
and by Lemma~\ref{lemma-apex}, extended $k$-tree-grids have comparable box dimension at most $2k+2$.
646
By Corollary~\ref{cor-csump}, it follows that $\cbdim(\GG)\le 1250^{2k+2}$.
647
\end{proof}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
648

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
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
\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
682
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
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
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}

703
Let us recall some notions about treewidth.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
704
705
706
707
708
709
710
711
712
713
714
  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$.
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
715
716
of the widths of its tree decompositions.  Let us remark that the value of treewidth obtained via this definition coincides
with the one via $k$-trees which we used in the previous section.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
717

Zdenek Dvorak's avatar
Zdenek Dvorak committed
718
719
720
\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
721
is fractionally treewidth-fragile, with a function $f(k) = O_{t,s,d}\bigl(k^{d}\bigr)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
722
723
724
725
726
\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$.
727
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
Daniel Gonçalves's avatar
Daniel Gonçalves committed
728
it is defined as follows.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
729
730
\begin{itemize}
\item Let $\ell_{1,j}=ksd|\omega(v_1)[j]|$.
Daniel Gonçalves's avatar
Daniel Gonçalves committed
731
732
733
734
735
736
\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
737
\end{itemize}
Daniel Gonçalves's avatar
Daniel Gonçalves committed
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
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
753
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
754
755
$|\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
756
757
758
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,
759
\[\frac{|\omega(v_a)[j]|}{\ell_{a,j}}\le \frac{s\omega(v_{a'})[j]}{ksd|\omega(v_{a'})[j]|}=\frac{1}{kd}.\]
Zdenek Dvorak's avatar
Zdenek Dvorak committed
760
761
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
762
Let us now bound the treewidth of $G-X$.  
763
For $a\ge 0$, an \emph{$a$-cell} is a maximal connected subset of $\mathbb{R}^d\setminus \bigl(\bigcup_{H\in \HH^a} H\bigr)$.
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
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
784
785
\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
786
\[\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
787
788
789
\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
790
791
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
792
793
794
795
796
797
798
799
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
800
\[|\beta(C)|-1\le (2ksd+2)^dst=f(k),\]
Zdenek Dvorak's avatar
Zdenek Dvorak committed
801
802
803
as required.
\end{proof}

804
805
806
807
808
809
810
811
812
813
814
815
816
817
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
818
\bibliography{data}
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962

\appendix

\section{Omitted proofs}

\newtheorem*{lemma-A}{Lemma~\ref{lem-cs}}
\begin{lemma-A}
  Consider two graphs $G_1$ and $G_2$, given with a $C^\star_1$- and a
  $C^\star_2$-clique-sum extendable representations $h_1$ and $h_2$ by comparable boxes
  in $\mathbb{R}^{d_1}$ and $\mathbb{R}^{d_2}$,
  respectively. Let $G$ be the graph obtained by performing a full
  clique-sum of these two graphs on any clique $C_1$ of $G_1$, and on
  the root clique $C^\star_2$ of $G_2$.  Then $G$ admits a $C^\star_1$-clique
  sum extendable representation $h$ by comparable boxes in
  $\mathbb{R}^{\max(d_1,d_2)}$.
\end{lemma-A}
\begin{proof}
  By Lemma~\ref{lemma-add}, we can assume that $d_1=d_2$; let $d=d_1$.
  The idea is to translate (allowing also exchanges of dimensions) and
  scale $h_2$ to fit in $h_1^\varepsilon(C_1)$. Consider an $\varepsilon >0$
  sufficiently small so that $h_1^\varepsilon(C_1)$ satisfies all the
  \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}\]

  Now let us consider $G_2$ and its representation $h_2$. Here the
  vertices of $C^\star_2$ are also denoted $v_1,\ldots,v_k$, and
  without loss of generality, the \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
  representation by comparable boxes. The fact that the boxes are
  comparable follows from the fact that those of $h_1$ and $h_2$
  are comparable and from the scaling of $h_2$:  By construction both
  $h_1(v) \sqsubseteq h_1(u)$ and $h_2(v) \sqsubseteq h_2(u)$ imply
  $h(v) \sqsubseteq h(u)$, and for any vertex $u\in V(G_1)$ and any
  vertex $v\in V(G_2) \setminus V(C^\star_2)$, we have $h(v) \subset h_1^\varepsilon(C_1) \sqsubseteq h(u)$.

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

  Finally, let us consider the $C^\star_1$-clique-sum extendability. The \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}
\end{proof}

\newtheorem*{lemma-B}{Lemma~\ref{lem-apex-cs}}
\begin{lemma-B}
  For any graph $G$ and any clique $C^\star$, the graph $G$ admits a
  $C^\star$-clique-sum extendable touching representation by
  comparable boxes in $\mathbb{R}^d$, for $d = |V(C^\star)| +
  \ecbdim(G\setminus V(C^\star))$.
\end{lemma-B}
\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^\star)$ by
  comparable boxes in $\mathbb{R}^{d'}$, with $d' = \cbdim(G\setminus
  V(C^\star))$, and let $V(C^\star) = \{v_1,\ldots,v_k\}$. We now construct
  the desired representation $h$ of $G$ as follows. For each vertex
  $v_i\in V(C^\star)$, let $h(v_i)$ be the box in $\mathbb{R}^d$ uniquely determined
  by the condition (v1) with $d_{v_i} = i$. For each vertex $u\in V(G)\setminus V(C^\star)$,
  if $i\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] =
  \alpha h'(u)[i-k]$, for some $\alpha>0$. The value $\alpha>0$
Torsten Ueckerdt's avatar
Torsten Ueckerdt committed
963
  is chosen sufficiently small so that $h(u)[i] \subset [0,1)$ whenever $u\notin V(C^\star)$. 
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
  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 refer to the clique point $p'(C')$ of $C'=C\setminus
  \{v_1,\ldots,v_k\}$, and we set $p(C)[i] = \alpha p'(C')[i-k]$. 
  
  By the construction, it is clear that $h$ is a touching representation of $G$.
  As $h'(u) \sqsubset h'(v)$ implies that $h(u) \sqsubset h(v)$, and as 
  $h(u) \sqsubset h(v_i)$ for every $u\in V(G)\setminus V(C^\star)$ and every 
  $v_i \in V(C^\star)$, we have that $h$ is a representation by comparable boxes.

  For the $C^\star$-clique-sum extendability, the \textbf{(vertices)} conditions hold by the construction.
  For the \textbf{(cliques)} condition (c1), let us consider distinct cliques $C_1$ and $C_2$
  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$,
  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$, then $p'(C'_1) \neq p'(C'_2)$, which implies
  $p(C_1) \neq p(C_2)$ by construction.

  For the \textbf{(cliques)} condition (c2), let us first consider a vertex $v\in V(G)\setminus V(C^\star)$ and
  a clique $C$ of $G$ containing $v$.  In the dimensions $i\in\{1,\ldots,k\}$, we always have
  $h^\varepsilon(C)[i] \subseteq h(v)[i]$. Indeed, if $v_i \in V(C)$, then
  $h^\varepsilon(C)[i] \subseteq [0,1/2] = h(v)[i]$, as in this case $v$ and $v_i$ are adjacent;
  and if $v_i \notin V(C)$, then $h^\varepsilon(C)[i] \subseteq [1/4,1/2] \subseteq h(v)[i]$.
  By the property (c2) of $h'$,
  we have $h^\varepsilon(C)[i] \subseteq h(v)[i]$ for every $i>k$, except one, 
  for which $h^\varepsilon(C)[i] \cap h(v)[i] = \{p(C)[i]\}$. 
  
  Next, let us consider a vertex $v\in V(G)\setminus V(C^\star)$ and a clique $C$ of $G$ not containing $v$. 
  As $v\notin V(C')$, the condition (c2) for $h'$ implies that $p'(C')$ is disjoint from $h'(v)$,
  and thus $p(C)$ is disjoint from $h(v)$.
  
  Finally, we consider a vertex $v_i \in V(C^\star)$.  Note that for any clique $C$ containing $v_i$,
  we have that $h^\varepsilon(C)[i] \cap h(v_i)[i] = [0,\varepsilon]\cap [-1,0] = \{0\}$, and $h^\varepsilon(C)[j] \subseteq [0,1] = h(v_i)[j]$
  for any $j\neq i$. For a clique $C$ that does not contain $v_i$ we have that 
  $h^\varepsilon(C)[i] \cap h(v_i)[i] \subset (0,1)\cap [-1,0] = \emptyset$. 
  Condition (c2) is thus fulfilled and this completes the proof of the lemma. 
\end{proof}