comparable-box-dimension.tex 27.5 KB
Newer Older
Zdenek Dvorak's avatar
Zdenek Dvorak committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
\documentclass[10pt]{article}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{colonequals}
\usepackage{epsfig}
\usepackage{url}
\newcommand{\GG}{{\cal G}}
\newcommand{\CC}{{\cal C}}
\newcommand{\OO}{{\cal O}}
\newcommand{\PP}{{\cal P}}
\newcommand{\RR}{{\cal R}}
\newcommand{\col}{\text{col}}
\newcommand{\vol}{\text{vol}}

\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}}
%%%%%


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

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

\begin{document}
\maketitle

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

\section{Introduction}

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

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

Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} proved some basic properties of this notion.  In particular,
they proved that if a class $\GG$ has finite comparable box dimension, then it has polynomial strong coloring
numbers, which implies that $\GG$ has strongly sublinear separators.  They also provided an example showing
that for any function $h$, the class of graphs with strong coloring numbers bounded by $h$ has infinite
comparable box dimension.  Dvo\v{r}\'ak et al.~\cite{wcolig}
proved that graphs of comparable box dimension $3$ have exponential weak coloring number, giving the
85
first natural graph class with polynomial strong coloring numbers and superpolynomial weak coloring numbers
Zdenek Dvorak's avatar
Zdenek Dvorak committed
86
87
88
89
90
91
92
93
94
95
96
(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.
97
This gives arbitrarily precise approximation algorithms for all monotone maximization problems that are
Zdenek Dvorak's avatar
Zdenek Dvorak committed
98
99
100
101
102
expressible in terms of distances between the solution vertices and tractable on graphs of bounded treewidth~\cite{distapx}
or expressible in the first-order logic~\cite{logapx}.

\section{Operations}

103
Let us start with a simple lemma saying that the addition of a vertex increases the comparable box dimension by at most one.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
104
In particular, this implies that $\cbdim(G)\le |V(G)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
105
106
107
108
\begin{lemma}\label{lemma-apex}
For any graph $G$ and $v\in V(G)$, we have $\cbdim(G)\le \cbdim(G-v)+1$.
\end{lemma}
\begin{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
109
Let $f$ be a touching representation of $G-v$ by comparable boxes in $\mathbb{R}^d$, where $d=\cbdim(G-v)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
110
111
112
For each $u\in V(G)\setminus\{v\}$, let $h(u)=[0,1]\times f(u)$ if $uv\in E(G)$ and 
$h(u)=[1/2,3/2]\times f(u)$ if $uv\not\in E(G)$.  Let $h(v)=[-1,0]\times [-M,M] \times \cdots \times [-M,M]$,
where $M$ is chosen large enough so that $f(u)\subseteq [-M,M] \times \cdots \times [-M,M]$ for every $u\in V(G)\setminus\{v\}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
113
Then $h$ is a touching representation of $G$ by comparable boxes in $\mathbb{R}^{d+1}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
114
115
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
116
We need a bound on the clique number in terms of the comparable box dimension.
117
For a box $B=I_1\times \cdots \times I_d$ and $i\in\{1,\ldots,d\}$, let $B[i]=I_i$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
118
119
120
121
\begin{lemma}\label{lemma-cliq}
If $G$ has a touching representation $f$ by comparable boxes in $\mathbb{R}^d$, then $\omega(G)\le 2^d$.
\end{lemma}
\begin{proof}
122
123
124
125
 For any clique $A = \{a_1,\ldots,a_w\}$ in $G$, the corresponding boxes $f(a_1),\ldots,f(a_w)$ have pairwise non-empty intersection.
 Since axis-aligned boxes have the Helly property, there is a point $p \in \mathbb{R}^d$ contained in $f(a_1) \cap \cdots \cap f(a_w)$.
 As each box is full-dimensional, its interior intersects at least one of the $2^d$ orthants at $p$.
 Since $f$ is a touching representation, $f(a_1),\ldots,f(a_d)$ have pairwise disjoint interiors and hence $w \leq 2^d$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
126
\end{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
127

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

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

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

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

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

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

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
222
223
224
Next, let us deal with clique-sums.  A \emph{clique-sum} of two graphs $G_1$ and $G_2$ is obtained from their disjoint union
by identifying vertices of a clique in $G_1$ and a clique of the same size in $G_2$ and possibly
deleting some of the edges of the resulting clique.  The main issue to overcome in obtaining a representation for a clique-sum
225
226
is that the representations of $G_1$ and $G_2$ can be ``degenerate''. Consider e.g.\ the case that $G_1$ is represented
by unit squares arranged in a grid; in this case, there is no space to attach $G_2$ at the cliques formed by four squares intersecting
Zdenek Dvorak's avatar
Zdenek Dvorak committed
227
in a single corner.  This can be avoided by increasing the dimension, but we need to be careful so that the dimension stays bounded
228
even after an arbitrary number of clique-sums.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
229
230

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

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

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

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

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

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

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

Note that only bound the comparable box dimension of a supergraph
of $G$.  To deal with this issue, we show that the comparable box dimension of a subgraph
is at most exponential in the comparable box dimension of the whole graph.
This is essentially Corollary~25 in~\cite{subconvex}, but since the setting is somewhat
different and the construction of~\cite{subconvex} uses rotated boxes,
we provide details of the argument.

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

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

Consequently, when choosing the color of $v_i$ greedily, we only need to avoid colors of at most
$$(5^d-1) + (3^d-1) + (3^d-1)^2<5^d+9^d<2\cdot 9^d$$
vertices.
\end{proof}

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

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

For any distinct colors $i,j\in\{1,\ldots,c\}$, let $A_{i,j}\subseteq V(G)$ consist of vertices $u$ of color $i$
such that there exists a vertex $v$ of color $j$ such that $uv\in E(G')$ and $uv\not\in E(G)$.
Let us define a representation $h$ by boxes in $\mathbb{R}^{d+\binom{c}{2}}$ by starting from the representation $f$ and,
for each pair $i<j$ of colors, adding a dimension $d_{i,j}$ and setting
$h(v)[d_{i,j}]=[1/3,4/3]$ for $v\in A_{i,j}$, $h(v)[d_{i,j}]=[-4/3,-1/3]$ for $v\in A_{j,i}$,
and $h(v)[d_{i,j}](v)=[-1/2,1/2]$ otherwise.  Note that the boxes in this extended representation are comparable,
as in the added dimensions, all the boxes have size $1$.

Suppose $uv\in E(G)$, where $\varphi(u)=i$ and $\varphi(v)=j$ and say $i<j$.  The boxes $f(u)$ and $f(v)$ touch.
We cannot have $u\in A_{i,j}$ and $v\in A_{j,u}$, as then $G'$ would contain a 4-vertex path in colors $i$ and $j$.
Hence, in any added dimension $d'$, at least one of $h(u)$ and $h(v)$ is represented by the interval $[-1/2,1/2]$,
and thus $h(u)[d']\cap h(v)[d']\neq\emptyset$.  Therefore, the boxes $h(u)$ and $h(v)$ touch.

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

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

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

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

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

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

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
398
399
400
\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
401

Zdenek Dvorak's avatar
Zdenek Dvorak committed
402
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
403
404
405
\bibliography{data}

\end{document}