comparable-box-dimension.tex 16.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
\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
Daniel Gon\c{c}alves\thanks{...}
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$}
if there exists a function $f:V(G)\to \OO$ (called the \emph{touching representation by objects from $\OO$})
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$.
This result motivated a number of strenthenings and variations~\cite{...}; most relevantly for us, every planar graph is
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$.
For example, all complete bipartite graphs $K_{n,m}$ are touching graphs of axis-aligned boxes in $\mathbb{R}^d$, where the vertices in
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$
boxes (a \emph{box} is the cartesian product of intervals of non-zero length).
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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
first natural graph class with olynomial strong coloring numbers and superpolynomial weak coloring numbers
(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.
This gives arbitrarily precise approximation algorithms for alll monotone maximization problems that are
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}

Let us start with a simple lemma saying that 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
117
118
119
120
121
122
123
We need a bound on the clique number in terms of the comparable box dimension.
For a box $B=I_1\times \cdots I_d$ and $i\in\{1,\ldots,d\}$, let $B[i]=I_i$.
\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}
...
\end{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
124

Zdenek Dvorak's avatar
Zdenek Dvorak committed
125
126
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
127
128
such that
\begin{itemize}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
129
130
\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
131
\end{itemize}
132
For nodes $x,y\in V(T)$, we write $x\preceq y$ if $x=y$ or $x$ is a descendant of $y$ in $T$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
133
134
135
136
137
138
139
140
141
For each vertex $v\in V(G)$, let $p(v)$ be the node $x\in V(T)$ such that $v\in \beta(x)$ nearest to the root of $T$.
The \emph{adhesion} of the tree decomposition is the maximum of $|\beta(x)\cap\beta(y)|$ over distinct $x,y\in V(T)$,
and its \emph{width} is the maximum of the sizes of the bags minus $1$.  The \emph{treewidth} of a graph is the minimum
of the widths of its tree decompositions.  We will need to know that graphs of bounded treewidth have bounded dimension.
In fact, we will prove the following stronger fact (TODO: Was this published somehere before?)

\begin{lemma}\label{lemma-tw}
Let $(T,\beta)$ be a tree decomposition of a graph $G$ of width $t$.
Then $G$ has a touching representation $h$ by hypercubes in $R^{t+1}$ such that
142
143
for $u,v\in V(G)$, if $p(u)\preceq p(v)$, then $h(u)\sqsubseteq h(v)$.
Moreover, the representation can be chosen so that no two hypercubes have the same size.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
144
145
146
147
148
\end{lemma}
\begin{proof}
...
\end{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
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
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 arrangef 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 arbitrary number of clique-sums.

It will be convenient to work in the setting of tree decompositions.
Consider a tree decompostion $(T,\beta)$ of a graphs $G$.
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}
If $(T,\beta)$ is a tree decompositon of $G$ of adhesion $a$, then $(T,\pi)$ is a tree decomposition of $T_\beta$ of width at most $a$.
169
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
170
171
\end{lemma}
\begin{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
172
173
174
175
176
177
178
179
180
181
182
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$.
183
184
185
186
187
188
189

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
190
191
192
193
194
195
196
197
198
199
200
\end{proof}

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

\begin{theorem}
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},
201
202
$T_\beta$ has a touching representation $h$ by hypercubes in $\mathbb{R}^{a+1}$ such that
$h(x)\sqsubseteq h(y)$ whenever $x\preceq y$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
203
Since $T_\beta$ has treewidth at most $a$, it has a proper coloring $\varphi$ by colors $\{0,\ldots,a\}$.
204
205
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
206
207
there exists a box $E_i(x)$ such that
\begin{itemize}
208
209
210
211
212
\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
213
\end{itemize}
214
215
216
217
218
219
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
220
221
222
223
224

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
225
$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
226
227
228
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$.
229
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
230
If $x\neq y$, then $y\in\pi(x)$ and $xy\in E(T_\beta)$, implying that $h(x)\cap h(y)\neq\emptyset$.
231
232
233
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
234
235
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
236

237
238
239
240
241
242
243
244
245
246
247
248
249
250
%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
251

Zdenek Dvorak's avatar
Zdenek Dvorak committed
252
253
\section{Exploiting the product structure}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
254
255
256
\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
257

Zdenek Dvorak's avatar
Zdenek Dvorak committed
258
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
259
260
261
\bibliography{data}

\end{document}