comparable-box-dimension.tex 22.8 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
Note that in Theorem~\ref{thm-cs}, we only get a representation of a supergraph
of $G$.  
Zdenek Dvorak's avatar
Zdenek Dvorak committed
311

312
313
314
315
316
317
318
319
320
321
322
323
324
325
%We will need the fact that the 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$ is $3^d$-colorable.
%\end{lemma}
%\begin{proof}
%We actually show that $G$ is $(3^d-1)$-degenerate.  Since every induced subgraph of $G$ also
%has a comparable box representation in $\mathbb{R}^d$, it suffices to show that the minimum degree of $G$
%is less than $3^d$.  Let $v$ be a vertex of $G$ such that $f(v)$ has the smallest volume.  For every neighbor $u$ of $v$,
%there exists a translation $B_u$ of $f(v)$ such that $B_u\subseteq f(u)$ and $B_u$ touches $f(v)$.
%Note that $f(v)\cup \bigcup_{u\in N(v)} B_u$ is a union of internally disjoint translations of $f(v)$ contained in
%a box obtained from $f(v)$ by scaling it by a factor of three, and thus $1+|N(v)|\le 3^d$.
%\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
326

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

Zdenek Dvorak's avatar
Zdenek Dvorak committed
329
330
331
\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
332

Zdenek Dvorak's avatar
Zdenek Dvorak committed
333
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
334
335
336
\bibliography{data}

\end{document}