comparable-box-dimension.tex 41.1 KB
 Zdenek Dvorak committed Sep 06, 2021 1 2 3 4 5 6 7 8 9 \documentclass[10pt]{article} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{amssymb} \usepackage{colonequals} \usepackage{epsfig} \usepackage{url} \newcommand{\GG}{{\cal G}}  Zdenek Dvorak committed Sep 16, 2021 10 \newcommand{\HH}{{\cal H}}  Zdenek Dvorak committed Sep 06, 2021 11 12 13 14 15 16 17 18 19 20 21 \newcommand{\CC}{{\cal C}} \newcommand{\OO}{{\cal O}} \newcommand{\PP}{{\cal P}} \newcommand{\RR}{{\cal R}} \newcommand{\eps}{\varepsilon} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mf}[1]{\mathfrak{#1}} \newcommand{\bb}[1]{\mathbb{#1}} \newcommand{\brm}[1]{\operatorname{#1}} \newcommand{\cbdim}{\brm{dim}_{cb}}  Zdenek Dvorak committed Sep 16, 2021 22 23 \newcommand{\tw}{\brm{tw}} \newcommand{\vol}{\brm{vol}}  Zdenek Dvorak committed Sep 06, 2021 24 25 26 27 28 29 30 31 32 33 34 35 36 37 %%%%% \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  Torsten Ueckerdt committed Sep 07, 2021 38 Daniel Gon\c{c}alves\thanks{...}\and  Zdenek Dvorak committed Sep 06, 2021 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 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$}  Torsten Ueckerdt committed Sep 07, 2021 57 if there exists a function $f:V(G)\to \OO$ (called a \emph{touching representation by objects from $\OO$})  Zdenek Dvorak committed Sep 06, 2021 58 59 60 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$.  Torsten Ueckerdt committed Sep 07, 2021 61 This result motivated a number of strengthenings and variations~\cite{...}; most relevantly for us, every planar graph is  Zdenek Dvorak committed Sep 06, 2021 62 63 64 65 66 67 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$.  Torsten Ueckerdt committed Sep 07, 2021 68 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 committed Sep 06, 2021 69 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$  Torsten Ueckerdt committed Sep 07, 2021 70 boxes (a \emph{box} is the Cartesian product of intervals of non-zero length).  Zdenek Dvorak committed Sep 06, 2021 71 Dvo\v{r}\'ak, McCarty and Norin~\cite{subconvex} noticed that this issue disappears if we forbid such a combination of  Zdenek Dvorak committed Sep 07, 2021 72 73 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 committed Sep 06, 2021 74 75 76 77 78 79 80 81 82 83 84 85 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  Torsten Ueckerdt committed Sep 07, 2021 86 first natural graph class with polynomial strong coloring numbers and superpolynomial weak coloring numbers  Zdenek Dvorak committed Sep 06, 2021 87 88 89 90 91 92 93 94 95 96 97 (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.  Torsten Ueckerdt committed Sep 07, 2021 98 This gives arbitrarily precise approximation algorithms for all monotone maximization problems that are  Zdenek Dvorak committed Sep 06, 2021 99 100 101 102 103 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}  Torsten Ueckerdt committed Sep 07, 2021 104 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 committed Sep 06, 2021 105 In particular, this implies that $\cbdim(G)\le |V(G)$.  Zdenek Dvorak committed Sep 06, 2021 106 107 108 109 \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 committed Sep 06, 2021 110 Let $f$ be a touching representation of $G-v$ by comparable boxes in $\mathbb{R}^d$, where $d=\cbdim(G-v)$.  Zdenek Dvorak committed Sep 06, 2021 111 112 113 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 committed Sep 06, 2021 114 Then $h$ is a touching representation of $G$ by comparable boxes in $\mathbb{R}^{d+1}$.  Zdenek Dvorak committed Sep 06, 2021 115 116 \end{proof}  Zdenek Dvorak committed Sep 06, 2021 117 We need a bound on the clique number in terms of the comparable box dimension.  Torsten Ueckerdt committed Sep 07, 2021 118 For a box $B=I_1\times \cdots \times I_d$ and $i\in\{1,\ldots,d\}$, let $B[i]=I_i$.  Zdenek Dvorak committed Sep 06, 2021 119 120 121 122 \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}  Torsten Ueckerdt committed Sep 07, 2021 123 124 125 126  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 committed Sep 06, 2021 127 \end{proof}  Zdenek Dvorak committed Sep 06, 2021 128   Zdenek Dvorak committed Sep 06, 2021 129 130 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 committed Sep 06, 2021 131 132 such that \begin{itemize}  Zdenek Dvorak committed Sep 06, 2021 133 134 \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 committed Sep 06, 2021 135 \end{itemize}  Zdenek Dvorak committed Sep 07, 2021 136 For nodes $x,y\in V(T)$, we write $x\preceq y$ if $x=y$ or $x$ is a descendant of $y$ in $T$.  Torsten Ueckerdt committed Sep 07, 2021 137 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 committed Sep 06, 2021 138 139 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  Torsten Ueckerdt committed Sep 07, 2021 140 141 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 committed Sep 06, 2021 142 143 144  \begin{lemma}\label{lemma-tw} Let $(T,\beta)$ be a tree decomposition of a graph $G$ of width $t$.  Zdenek Dvorak committed Sep 08, 2021 145 146 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)$.  Zdenek Dvorak committed Sep 07, 2021 147 Moreover, the representation can be chosen so that no two hypercubes have the same size.  Zdenek Dvorak committed Sep 06, 2021 148 149 \end{lemma} \begin{proof}  Zdenek Dvorak committed Sep 08, 2021 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 220 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 $ij$. We greedily color the vertices in order, giving $v_i$ the smallest color different from the colors of all vertices $v_j$ such that $jj$ 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_1i$ 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 $mt+2$.} \end{cases}$$Clearly, this is a touching representation by comparable boxes. \end{proof} Combining Theorem~\ref{thm-prod}, Lemma~\ref{lemma-ps}, and the results of the previous section, we obtain the following corollary, which in particular implies Theorem~\ref{thm-minor}. \begin{corollary}\label{cor-minor} For every graph G of Euler genus g, there exists a supergraph G' of G such that \cbdim(G')\le 6+\lceil \log_2 \max(2g,3)\rceil. Consequently,$$\cbdim(G)\le 5\cdot 81^7 \cdot (2g+3)^{\log_2 81}.$$Moreover, for every k there exists d such that if K_k\not\preceq_m(G), then \cbdim(G)\le d. \end{corollary} Note that the graph obtained from K_{2n} by deleting a perfect matching has Euler genus \Theta(n^2) and comparable box dimension n, showing that the dependence of the comparable box dimension cannot be subpolynomial (though the degree \log_2 81 of the polynomial established in Corollary~\ref{cor-minor} certainly can be improved). The dependence of the comparable box dimension on the size of the forbidden minor that we established is not explicit, as Theorem~\ref{thm-prod} is based on the structure theorem of Robertson and Seymour~\cite{robertson2003graph}. It would be interesting to prove this part of Corollary~\ref{cor-minor} without using the structure theorem.  Zdenek Dvorak committed Sep 16, 2021 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 \section{Fractional treewidth-fragility} Suppose G is a connected planar graph and v is a vertex of G. For an integer k\ge 2, give each vertex at distance d from v the color d\bmod k. Then deleting the vertices of any of the k colors results in a graph of treewidth at most 3k. This fact (which follows from the result of Robertson and Seymour~\cite{rs3} on treewidth of planar graphs of bounded radius) is (in the modern terms) the basis of Baker's technique~\cite{baker1994approximation} for design of approximation algorithms. However, even quite simple graph classes (e.g., strong products of three paths~\cite{gridtw}) do not admit such a coloring (where the removal of any color class results in a graph of bounded treewidth). However, a fractional version of this coloring concept is still very useful in the design of approximation algorithms~\cite{distapx} and applies to much more general graph classes, including all graph classes with strongly sublinear separators and bounded maximum degree~\cite{twd}. We say that a class of graphs \GG is \emph{fractionally treewidth-fragile} if there exists a function f such that for every graph G\in\GG and integer k\ge 2, there exist sets X_1, \ldots, X_m\subseteq V(G) such that each vertex belongs to at most m/k of them and \tw(G-X_i)\le f(k) for every i (equivalently, there exists a probability distribution on the set \{X\subseteq V(G):\tw(G-X)\le f(k)\} such that \text{Pr}[v\in X]\le 1/k for each v\in V(G)). For example, the class of planar graphs is (fractionally) treewidth-fragile, since we can let X_i consist of the vertices of color i-1 in the coloring described at the beginning of the section. Our main result is that all graph classes of bounded comparable box dimension are fractionally treewidth-fragile. We will show the result in a more general setting, motivated by concepts from~\cite{subconvex} and by applications to related representations. The argument is motivated by the idea used in the approximation algorithms for disk graphs by Erlebach et al.~\cite{erlebach2005polynomial}. For a measurable set A\subseteq \mathbb{R}^d, let \vol(A) denote the Lebesgue measure of A. For two measurable subsets A and B of \mathbb{R}^d and a positive integer s, we write A\sqsubseteq_s B if for every x\in B, there exists a translation A' of A such that \vol(A'\cap B)\ge \tfrac{1}{s}\vol(A). Note that for two boxes A and B, we have A\sqsubseteq_1 B if and only if A\sqsubseteq B. An \emph{s-comparable envelope representation} (\iota,\omega) of a graph G in \mathbb{R}^d consists of two functions \iota,\omega:V(G)\to 2^{\mathbb{R}^d} such that for some ordering v_1, \ldots, v_n of vertices of G, \begin{itemize} \item for each i, \omega(v_i) is a box, \iota(v_i) is a measurable set, and \iota(v_i)\subseteq \omega(v_i), \item if i1 and \ell_{a,j}=\ell_{a-1,j}, then b_{a,j}=1, implying \ell_{a,j}=\ell_{a-1,j}<2ksd|\omega(v_a)[j]|. \item If a>1 and \ell_{a,j}>\ell_{a-1,j}, then \ell_{a-1,j}\ge 2ksd|\omega(v_a)[j]| and$$\ell_{a,j}=\frac{\ell_{a-1,j}}{\lfloor \frac{\ell_{a-1,j}}{ksd|\omega(v_a)[j]|}\rfloor}<\tfrac{3}{2}ksd|\omega(v_a)[j]|.\end{itemize} Hence, \ell_{a,j}<2ksd |\omega(v_a)[j]|. Let C' be the box with the same center as C and with |C'[j]|=(2ksd+2)|\omega(v_a)[j]|. For any v_i\in \beta(C)\setminus\{v_a\}, we have i\le a and \iota(v_i)\cap C\neq\emptyset, and since \omega(v_a)\sqsubseteq_s \iota(v_i), there exists a translation B_i\subseteq C' of \omega(v_a) such that \vol(B_i\cap\iota(v_i))\ge \tfrac{1}{s}\vol(\omega(v_a)). Since the representation has thickness at most t, \begin{align*} \vol(C')&\ge \vol\left(C'\cap \bigcup_{v_i\in \beta(C)\setminus\{v_a\}} \iota(v_i)\right)\\ &\ge \vol\left(\bigcup_{v_i\in \beta(C)\setminus\{v_a\}} B_i\cap\iota(v_i)\right)\\ &\ge \frac{1}{t}\sum_{v_i\in \beta(C)\setminus\{v_a\}} \vol(B_i\cap\iota(v_i))\\ &\ge \frac{\vol(\omega(v_a))(|\beta(C)|-1)}{st}. \end{align*} Since \vol(C')=(2ksd+2)^d\vol(\omega(v_a)), it follows that|\beta(C)|-1\le (2ksd+2)^dst=f(k), as required. \end{proof}  Zdenek Dvorak committed Sep 16, 2021 573 574 575 576 577 578 579 580 581 582 583 584 585 586 The proof that (generalizations of) graphs with bounded comparable box dimensions have sublinear separators in~\cite{subconvex} is indirect; it is established that these graphs have polynomial coloring numbers, which in turn implies they have polynomial expansion, which then gives sublinear separators using the algorithm of Plotkin, Rao, and Smith~\cite{plotkin}. The existence of sublinear separators is known to follow more directly from fractional treewidth-fragility. Indeed, since $\text{Pr}[v\in X]\le 1/k$, there exists $X\subseteq V(G)$ such that $\tw(G-X)\le f(k)$ and $|X|\le |V(G)|/k$. The graph $G-X$ has a balanced separator of size at most $\tw(G-X)+1$, which combines with $X$ to a balanced separator of size at most $V(G)|/k+f(k)+1$ in $G$. Optimizing the value of $k$ (choosing it so that $V(G)|/k=f(k)$), we obtain the following corollary of Theorem~\ref{thm-twfrag}. \begin{corollary} For positive integers $t$, $s$, and $d$, every graph $G$ with an $s$-comparable envelope representation in $\mathbb{R}^d$ of thickness at most $t$ has a sublinear separator of size $O_{t,s,d}\bigl(|V(G)|^{\tfrac{d}{d+1}}\bigr).$ \end{corollary}  Zdenek Dvorak committed Sep 06, 2021 587 588 589 \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 committed Sep 06, 2021 590   Zdenek Dvorak committed Sep 06, 2021 591 \bibliographystyle{siam}  Zdenek Dvorak committed Sep 06, 2021 592 593 594 \bibliography{data} \end{document}