comparable-box-dimension.tex 15 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
71
72
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
\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
long and wide boxes: Two boxes are \emph{comparable} if a translation of one of them is a subset of the other one.
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
103
In particular, this implies that $\cbdim(G)\le |V(G)$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
104
105
106
107
\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
108
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
109
110
111
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
112
Then $h$ is a touching representation of $G$ by comparable boxes in $\mathbb{R}^{d+1}$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
113
114
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
%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}

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
137

Zdenek Dvorak's avatar
Zdenek Dvorak committed
138
139
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
140
141
such that
\begin{itemize}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
142
143
\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
144
\end{itemize}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
145
146
147
148
149
150
151
152
153
154
155
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
for $u,v\in V(G)$, if $p(u)\neq p(v)$ and $p(u)$ is an ancestor of $p(v)$ in $T$,
then $\vol(h(u))>\vol(h(v))$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
156
157
158
159
160
\end{lemma}
\begin{proof}
...
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
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$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
181
182
\end{lemma}
\begin{proof}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
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
220
221
222
223
224
225
226
227
228
229
230
231
232
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$.
\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},
$T_\beta$ has a touching representation $h$ by hypercubes in $\mathbb{R}^{a+1}$. Moreover,
letting $\prec$ be a linear ordering on $V(T)$ in a non-decreasing order according to the volume of the hypercubes assigned by $h$,
we have that $x\prec y$ whenever $x$ is a descendant of $y$ in $T$.
Since $T_\beta$ has treewidth at most $a$, it has a proper coloring $\varphi$ by colors $\{0,\ldots,a\}$.
For every $x\in V(T)$, let $f_x$ be a touching representation of the torso of $x$ by comparable boxes in $\mathbb{R}^d$
for $d=\cbdim(\GG)$.  We scale and translate the representations so that for every $x\in V(T)$ and $i\in\{0,\ldots,a\}$,
there exists a box $E_i(x)$ such that
\begin{itemize}
\item whenever $x\prec y$, we have $E_i(x)\subseteq E_i(y)$ and a translation of $E_i(x)$ is a subset of every box of
the representation $f_y$ whenever $x\prec y$,
\item if $i=\varphi(x)$, then all boxes of $f_x$ are subsets of $E_i(x)$, and
\item if $i\neq p(v)$ and $K=\{v\in\beta(x):\varphi(p(v))=i\}$, then letting $y=p(v)$ for $v\in K$ (and noting that this $y$
is unique, since $\varphi$ is a proper coloring of $T_\beta$ and that $K$ is a clique in $G_y$), the box $E_i(x)$
contains a point belonging to $\bigcap_{v\in K} f_y(v)$.
\end{itemize}

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
$p(u)\prec p(v)$, then this is due to the scaling of $f_{p(u)}$.  Next, let us argue $f(u)$ and $f(v)$ have disjoint
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$.
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$.
If $x\neq y$, then $y\in\pi(x)$ and $xy\in E(T_\beta)$, implying that $h(x)\cap h(y)\neq\emptyset$.
Moreover, $x\prec y$, implying that $E_i(u)\cap E_i(v)\neq\emptyset$ for $i=0,\ldots,a$.
Hence, again we have $f(u)\cap f(v)\neq\emptyset$.
Zdenek Dvorak's avatar
Zdenek Dvorak committed
233
234
\end{proof}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
235
236


Zdenek Dvorak's avatar
Zdenek Dvorak committed
237
238
\section{Exploiting the product structure}

Zdenek Dvorak's avatar
Zdenek Dvorak committed
239
240
241
\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
242

Zdenek Dvorak's avatar
Zdenek Dvorak committed
243
\bibliographystyle{siam}
Zdenek Dvorak's avatar
Zdenek Dvorak committed
244
245
246
\bibliography{data}

\end{document}