Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs

We introduce some preliminaries in section 2. In section 3, we discuss basic properties of sphere dimension, particularly the connection to circle graphs. In section 4, we prove our main result that ${𝒞}_t^d$ has strongly sublinear separators. We prove that ${𝒞}^d$ has bounded asymptotic dimension in section 5. We conclude with some open problems in section 6.

Let $𝒢$ be a class of geometric objects in a given space, for example, unit squares in the plane. Then an intersection graph of $𝒢$ is a graph $G$ whose vertices can be identified with objects in $𝒢$ such that there is an edge between two vertices in $G$ if and only if the two corresponding objects intersect. Similarly, we write $G(𝒢)$ for the graph with vertex-set $𝒢$ where two vertices are adjacent if they have a non-empty intersection. The ply of $𝒢$ is the maximum size of a set of objects in $𝒢$ with a non-empty common intersection.

Our proof of theorem 1 relies on a theorem of Plotkin, Rao, and Smith [46] and Dvořák and Norin [18] which characterises classes that admit strongly sublinear separators in terms of forbidden shallow minors. We give some relevant definitions.

Given a positive integer $r$, we say that a graph $H$ is an $r$-shallow minor of a graph $G$ if there is a function $\phi :V(H)\to 2^{V(G)}$ such that:

• $\mathrm{■}$

  for every $x\in V(H)$, the subgraph of $G$ induced by $\phi (x)$ contains a rooted spanning tree of height at most $r$,

• $\mathrm{■}$

  for all distinct $x,y\in V(H)$, the sets $\phi (x)$ and $\phi (y)$ are disjoint, and

• $\mathrm{■}$

  for every $xy\in E(H)$, there is an edge in $G$ with one end in $\phi (x)$ and the other in $\phi (y)$.

We call $\phi$ an $r$-shallow minor model of $H$ in $G$. For $v\in V(H)$, we call $\phi (v)$ the bag of $v$.

Recall that a balanced separator in an $n$-vertex graph $G$ is a set $S\subseteq V(G)$ so that each component of $G-S$ has at most $\frac{2}{3}n$ vertices. A graph class $𝒞$ has strongly sublinear separators if there exist $\epsilon >0$ so that for any $n$-vertex graph $H$ which is an induced subgraph of a graph in $𝒞$, the graph $H$ has a balanced separator of size $𝒪(n^{1-\epsilon })$. (The big-$𝒪$ notation can hide a constant factor that depends on $𝒞$.) Note that to obtain strongly sublinear separators, it suffices to show that there exists $\delta >0$ so that there are balanced separators of size $\widetilde{𝒪}(n^{1-\delta })$. In order to provide this, we show that there exists $\delta >0$ so that there are separators of size $\widetilde{𝒪}(n^{1-\delta })$. Plotkin, Rao, and Smith [46] proved that any graph with a forbidden shallow minor has a small balanced separator.

We apply this theorem with $r$ being a small power of $n$ and $h$ being a polynomial in $r$. With this choice of parameters, theorem 3 yields a sufficiently small balanced separator.

Let $G$ be a graph, $r\in \mathbb{N}$, and $\le$ be an ordering of the vertices of $G$. For a vertex $v\in V(G)$, we call a vertex $u\in V(G)$ strongly $r$-reachable from $v$ if $u\le v$ and there exists a $v$-$u$-path $P$ of length at most $r$ in $G$ such that $u$ is the only vertex in $P$ that is smaller than $v$ with respect to $\le$. The $r$-width of $\le$ is the maximum over all $v\in V(G)$ of the number of vertices which are strongly $r$-reachable from $v$. Finally, the $r$-strong colouring number of a graph $G$, denoted ${\mathrm{𝗌𝖼𝗈𝗅}}_r(G)$, is the minimum $r$-width over all possible vertex orderings of $G$. We require the observation that intersection graphs of balls of bounded ply have bounded strong colouring numbers.

We also use the following well-known observation that graphs with large shallow clique minors have large strong colouring numbers.

Let $G$ be a graph, and let ${\mathrm{𝖽𝗂𝗌𝗍}}_G(\cdot ,\cdot )$ denote its usual graph metric. If the graph is clear from the context, we drop the index. Let $𝒰$ be a family of subsets of $V(G)$. We say that $𝒰$ is $D$-bounded if each set $U\in 𝒰$ has diameter at most $D$. We say that $𝒰$ is $r$-disjoint if for any $a,b$ belonging to different elements of $𝒰$ we have $\mathrm{𝖽𝗂𝗌𝗍}(a,b)>r$.

We say that $D:{ℝ}_{+}\to {ℝ}_{+}$ is an n-dimensional control function for a graph class $𝒞$, if for any $G\in 𝒞$ and $r>0$, $V(G)$ has a cover $𝒰={\bigcup }_{i=1}^{n+1}{𝒰}_i$ such that each ${𝒰}_i$ is $r$-disjoint and each element of $𝒰$ is $D(r)$-bounded. The asymptotic dimension of $𝒞$ denoted by $\mathrm{𝖺𝗌𝖽𝗂𝗆}(𝒞)$, is the least integer $n$ such that $𝒞$ has an $n$-dimensional control function. If no such integer $n$ exists, then $\mathrm{𝖺𝗌𝖽𝗂𝗆}(𝒞)$ is infinite. The Assouad–Nagata dimension of $𝒞$, denoted by $\mathrm{𝖠𝖭𝖽𝗂𝗆}(𝒞)$, is defined similarly, except that we insist that $D(r)\in 𝒪(r)$.

For $d=1$ this is so by definition. For $d\ge 2$, suppose $\mathrm{\Theta }=\{H_v\mid v\in V(G)\}$ is a $d$-sphere representation of $G$, i.e. a family of elements of ${\mathscr{H}}_d$ witnessing that $G$ is a $d$-sphere graph. Assume that no $H_v$ contains the north pole $\{0,\mathrm{\dots },0,1\}$ of ${𝕊}^d$, which we can since $G$ is countable (which is a much stronger assumption than we actually need). Notice that $H_v\cap {𝕊}^d$ is homeomorphic to ${𝕊}^{d-1}$ for every $v$. Letting $f$ be the stereographic projection of ${𝕊}^d$ onto ${ℝ}^d$, we observe that $f(H_v\cap {𝕊}^d)≕H_v^{\prime }$ is also homeomorphic to ${𝕊}^{d-1}$, where we use the well-known property of stereographic projection that it preserves spheres not containing the north pole [44, Lemma 4.2]. Then $G$ is isomorphic to the intersection graph of the family ${\mathrm{\Theta }}^{\prime }=\{H_v^{\prime }\mid v\in V(G)\}$ by construction.

Conversely, we use $f^{-1}$ to stereographically project a representation of $G$ as an intersection graph of spheres in ${ℝ}^d$ (avoiding the origin) to a $d$-sphere graph representation. $◀$

We now give some other observations about sphere graphs and sphere dimension. As a warm-up, we observe that if $G$ is planar, then it has sphere dimension $2$. This is because the Circle Packing Theorem [35] asserts that every finite³³3More generally, this applies to any connected, locally finite, planar graph; see [31] and references therein. planar graph admits a sphere packing in ${ℝ}^2$. (A sphere packing of a graph $G$ is an arrangement of closed euclidean spheres $\{S_v:v\in V(G)\}$ in ${ℝ}^d$ or ${𝕊}^d$ such that $S_v\cap S_w$ is empty whenever $vw\notin E(G)$ and $S_v\cap S_w$ is a single point whenever $vw\in E(G)$. In other words, $G$ is the tangency graph of the family $\{S_v:v\in V(G)\}$.) It is known that every finite graph $G$ admits a sphere packing in ${ℝ}^d$ for $d\le |V(G)|-1$ [22], and so $G\in {𝒞}^{|V(G)|-1}$. This proves the following observation.

Conversely, we prove the following.

We may assume that $d\ge 2$ since it is well known that not every graph is a circle graph; see [5]. Let $n$ be an integer; we think of $n$ as being large in comparison to $d$.

Let $G_n$ be a graph of minimum degree $n$ that does not contain a triangle as a subgraph, and such that $G_n$ remains connected after removing the closed neighbourhood $N[y]≔N(y)\cup \{y\}$ of any $y\in V(G_n)$; for example, $G_n$ could be a portion of the $n$-dimensional cubic lattice. Suppose $G_n$ can be realised as a $d$-sphere graph, and therefore as an intersection graph of spheres $\{S_v\mid v\in V(G_n)\}$ in ${ℝ}^d$ by observation 6. Pick a sphere of minimum radius among the $S_v$. Then, the spheres representing the neighbours of $v$ intersect $S_v$ and are mutually disjoint since $G_n$ is triangle-free. Moreover, there is no triple $S_x,S_y,S_z$ of such spheres such that $S_y$ lies in the interior of $S_x$ and $S_z$ lies in the interior of $S_y$ because $N[y]$ would separate $x$ from $z$ in this case. Thus, after deleting any such spheres lying in the interior of others, we are left with at least $n/2$ spheres with disjoint interiors intersecting $S_v$, each of radius at least that of $S_v$. By a volume argument, the number of such spheres is bounded by a function of $d$. Thus $G_n$ is not a $d$-sphere graph when $n$ is large enough. $◀$

It is possible to strengthen observation 8 by providing cubic graphs of arbitrarily high sphere dimension. Indeed, this is a corollary of theorem 1, as we now discuss. Let $\{G_n^d:n\in \mathbb{N}\}$ be a family of cubic expander graphs with ${lim}_{n\to \mathrm{\infty }}|V(G_n^d)|=\mathrm{\infty }$. Then, since expanders do not have small separators, at most finitely many members of this family can have sphere dimension at most $d$ by theorem 1 and by Lee’s [37] separator theorem for circle graphs. Alternatively, we can let $\{G_n^d:n\in \mathbb{N}\}$ be a family of finite cubic graphs of asymptotic dimension more than $2d+1$; for instance, such graphs can be obtained from a portion of the $(2d+2)$–dimensional hypercubic lattice by replacing each vertex with a subcubic tree. Then at most finitely many members of this family can have sphere dimension at most $d$ by the result of [19] that our theorem 18 generalises.

We sort the vertices in $𝒩$ by containment and consider $\le$ to be this ordering. For every path $P\in 𝒫$ and every vertex $x\in V(P)$, the neighbourhood of $x$ in $𝒩$ is an interval with respect to $\le$. We denote this interval by $I_x$. The first two conditions of the lemma guarantee that every sphere in $𝒩$ is a neighbour of at least one vertex in $P$. Thus, since $|𝒩|=t(r+1)$ and $P$ has length at most $r$, every $P\in 𝒫$ contains a vertex $x_P$ with $|I_{x_P}|\ge t$. Also, there are at most $t(r+1)$ choices for the first vertex (according to $\le$) inside $I_{x_P}$. Therefore, there are $t$ vertices of the form $x_P$ (on different paths) such that their intervals all start in the same vertex. These $t$ vertices, plus the first $t$ vertices in their intervals, yield the desired $K_{t,t}$-subgraph. $◀$

Using this insight, we next prove that “minimal” graphs that contain a certain shallow clique minor cannot be represented by spheres with too much nesting.

Suppose towards a contradiction that there is a nested set $𝒩\subseteq 𝒮$ of size at least $36t^4{(3r+1)}^3$. Let $\phi$ be an $r$-shallow minor model of $K_h$ in $G$. For each vertex $x\in V(K_h)$, we fix some rooted spanning tree $T_x$ of the subgraph of $G$ induced on $\phi (x)$ of height at most $r$. Note that, as $G$ is minimal with respect to containing an $r$-shallow $K_h$-minor, every vertex of $G$ is in a bag of $\phi$. Similarly, for every vertex $x\in V(K_h)$, every leaf of $T_x$ has an edge to some other bag which has no other neighbours in $T_x$. We now break into cases based on whether many vertices in $𝒩$ lie in the same bag or in different bags.

First, consider the case that at least $6t^2{(3r+1)}^2$ vertices of $𝒩$ lie in a single bag, say the bag of $x\in V(K_h)$. As $T_x$ has height at most $r$, at least a $\frac{1}{(r+1)}$ proportion of these elements all have the same distance to the root of $T_x$. Thus, there exists a set $𝒳\subseteq 𝒩$ of size at least $6t^2(3r+1)$ such that all vertices in $𝒳$ are not only in $T_x$ but also have the same distance to the root of $T_x$. So, no vertex in $𝒳$ lies on the path between the root of $T_x$ and another vertex in $𝒳$. For each $X\in 𝒳$, we fix an arbitrary leaf vertex $\mathrm{\ell }(X)$ of $T_x$ that is a descendent of $X$ in $T_x$. (It is possible that $\mathrm{\ell }(X)=X$.) Let us denote the path of $T_x$ joining $X$ and $\mathrm{\ell }(X)$ by $P(X)$. Since all of the vertices in $𝒳$ have the same distance to the root, the paths $\{P(X)\mid X\in 𝒳\}$ are pairwise vertex-disjoint. Additionally, for each of these leaves $\mathrm{\ell }(X)$, there is a vertex $y(X)\in V(K_h)$ such the bag of $y(X)$ has an edge to $\mathrm{\ell }(X)$ and does not have an edge to any other vertex in $\phi (x)$. Thus, since the leaves $\{\mathrm{\ell }(X)\mid X\in 𝒳\}$ are all distinct, the vertices $\{y(X)\mid X\in 𝒳\}$ are also all distinct.

Now we sort the elements of $𝒳$ by containment as $X_1,\mathrm{\dots },X_{|𝒳|}$. We pair up the first $t^2(6r+2)$ elements of $𝒳$ with the last $t^2(6r+2)$ elements of $𝒳$. So we consider the pairs $(X_1,X_{|𝒳|})$, $(X_2,X_{|𝒳|-1})$, and so on. As $K_h$ is the complete graph, for every pair $(X_i,X_{|𝒳|-i+1})$ there is a path between $X_i$ and $X_{|𝒳|-i+1}$ whose vertex-set is contained in $P(X_i)\cup \phi (y(X_i))\cup \phi (y(X_{|𝒳|-i+1}))\cup P(X_{|𝒳|-i+1})$. The two paths $P(X_i)$ and $P(X_{|𝒳|-i+1})$ have length at most $r-1$ since no vertex in $𝒳$ is the root of $T_x$. In each of the two bags $\phi (y(X_i))$ and $\phi (y(X_{|𝒳|-i+1}))$, we can choose paths of length at most $2r$. Finally, we need $3$ edges to join the parts together. So overall, this path between $X_i$ and $X_{|𝒳|-i+1}$ has length at most $2(r-1)+2(2r)+3=6r+1$ (see figure 1). Note that $|𝒳|\ge 6t^2(3r+1)=3t^2(6r+2)\ge 2t^2(6r+2)+t(6r+2)$. So at least $t(6r+2)$ spheres lie between any two paired spheres in $𝒳$. Thus, by lemma 9, $G$ contains $K_{t,t}$ as a subgraph, a contradiction.

Second, consider the case that there exists a set $𝒳\subseteq 𝒩$ of size at least $6t^2(3r+1)$ so that every pair of vertices in $𝒳$ lie in different bags of $\phi$. So for every $X\in 𝒳$, there exists a vertex $y(X)\in V(K_h)$ such that $X$ lies in $\phi (y(X))$. Again, we sort the elements of $𝒳$ by containment as $X_1,\mathrm{\dots },X_{|𝒳|}$ and pair the first and last elements. This time, we pair the first $t(4r+2)$ elements of $𝒳$ with the last $t(4r+2)$ elements of $𝒳$. So for $1\le i\le t(4r+2)$, the sphere $X_i$ is paired to the sphere $X_{|𝒳|-i+1}$. As $K_h$ is the complete graph, there exists a path between $X_i$ and $X_{|𝒳|-i+1}$ of length at most $4r+1$ in the subgraph of $G$ induced by $\phi (y(X_i))\cup \phi (y(X_{|𝒳|-i+1}))$ (see figure 2). Additionally, $|𝒳|\ge 6t^2(3r+1)=3t^2(6r+2)\ge 2t(4r+2)+t^2(4r+2)$. Thus, at least $t^2(4r+2)$ spheres lie between any two paired spheres in $𝒳$. Thus, again by lemma 9, $G$ contains $K_{t,t}$ as a subgraph, a contradiction.

One of the two cases must occur, and so this completes the proof of lemma 10. $◀$

It is known, as seen in lemma 4, that intersection graphs of balls of small ply have bounded strong colouring number. We make use of this to show that we can obtain a similar result for sphere intersection graphs excluding a $K_{t,t}$-subgraph, assuming they can be represented without a large set of nested spheres.

We claim that the collection $\{\mathrm{𝖻𝖺𝗅𝗅}(S)\mid S\in 𝒮\}$ of balls in ${ℝ}^d$ has ply at most $2kt$. This yields the desired statement by lemma 4.

So, let $𝒳\subseteq 𝒮$ be a collection of spheres such that their common intersection as balls is non-empty, that is, such that ${\bigcap }_{X\in 𝒳}\mathrm{𝖻𝖺𝗅𝗅}(X)\ne \mathrm{\varnothing }$. Let us consider the poset $⪯$ on $𝒳$ where for any spheres $X,X^{\prime }\in 𝒳$, we have $X⪯X^{\prime }$ if $X$ is contained in $X^{\prime }$. Every chain in this poset has size at most $k$ by the assumption about nested sets. Next, note that a single point in ${ℝ}^d$ lies in at most $2t$ pairwise incomparable (according to $⪯$) spheres in $𝒳$, as otherwise, $G$ would contain a clique of size $2t$ and therefore have $K_{t,t}$ as a subgraph. Thus, every antichain in this poset has size at most $2t$, and the lemma follows. $◀$

The penultimate step is to combine lemmata 10 and 11 with observation 5 in order to exclude shallow minors from the class ${𝒞}_t^d$.

For convenience, we set $h=72t^5{(3r+2)}^{d+3}$. Suppose for a contradiction that there is a graph $G\in {𝒞}_t^d$ which contains $K_h$ as an $r$-shallow minor. Choose such a graph $G$ with as few vertices as possible. Let $𝒮$ be a collection of spheres in ${ℝ}^d$ such that $G=G(𝒮)$. Then by lemma 10, every nested subset of $𝒮$ has size at most $36t^4{(3r+1)}^3$. So by lemma 11, the $(4r+1)$-strong colouring number of $G$ is at most $2(36t^4{(3r+1)}^3)t{(2r+2)}^d$. Note that

Finally, by observation 5, the $(4r+1)$-strong colouring number of $G$ is at least $h-1$. So $h-1\le {\mathrm{𝗌𝖼𝗈𝗅}}_{4r+1}(G)\le h-2$, a contradiction. $◀$

Now we can combine our results with the theorem of Plotkin, Rao, and Smith [46] (stated as theorem 3) to obtain strongly sublinear separators in graphs of sphere dimension at most $d$ which exclude a $K_{t,t}$-subgraph. We restate the theorem below for convenience.

See 1

Let $G\in {𝒞}_t^d$. For convenience, set $r=n^{\frac{1}{2d+8}}$. (We omit floors and ceilings for the sake of readability when they do not affect the proof.) By lemma 12, $G$ does not have a clique of size $72t^5{(3r+2)}^{d+3}$ as an $r$-shallow minor. Since $72t^5{(3r+2)}^{d+3}\in {𝒪}_d(t^5{r}^{d+3})$, by theorem 3 we have that $G$ contains a balanced separator of size

$◀$

It is enough to show that if there is an edge of weight 2 between vertices $x,y$ in $(\widehat{G},\lambda )$, then in $G$, there is a vertex adjacent to both $x$ and $y$. Since there is an edge of weight 2 between vertices $x,y$ in $(\widehat{G},\lambda )$, there exists some positive integer $i$ such that $x,y\in D_i$, and without loss of generality, we may assume that $x$ is contained in $y$. Let $P$ be a path of length $i$ between $x$ and $v$, and let $z$ be the unique vertex of $D_{i-1}\cap V(P)$. Then $z$ intersects $x$ and ${\bigcup }_{u\in V(P)}u$ contains a curve $C$ from $x$ to a point in $v$ not contained in $w$ for any $w\in V(G)$. Since the curve $C$ starts in the interior of $y$ and ends in its exterior, $C$ must intersect $y$. Therefore, $y$ is adjacent to a vertex of $P$. However, $y$ is non-adjacent to $x$ in $G$ and cannot be adjacent to any vertex of $D_0\cup \mathrm{\cdots }\cup D_{i-2}$ since $y\in D_i$. Therefore, $y$ must be adjacent to $z$ in $G$. Hence, the distance between $x$ and $y$ in $G$ is equal to 2, as desired. $◀$

Let ${ℒ}_{d,\alpha }^i$ be the class of weighted graphs that are $(i,1)$-quasi-isometric to a graph in ${ℬ}_{\alpha }^d$. Note that ${ℒ}_{d,\alpha }^1\subseteq {ℒ}_{d,\alpha }^2\subseteq \mathrm{\cdots }$. Let ${ℒ}_{d,\alpha }=({ℒ}_{d,\alpha }^1,{ℒ}_{d,\alpha }^2,\mathrm{\dots })$. We show that ${\widehat{𝒞}}_{\alpha }^d$ is ${ℒ}_{d,\alpha }$-layerable.

Let $(\widehat{G},\lambda )\in {\widehat{𝒞}}_{\alpha }^d$, let $G\in {𝒞}_{\alpha }^d$ be the graph obtained from $(\widehat{G},\lambda )$ by removing its edges of weight 2, and let $v$ be the pivot-vertex of $(\widehat{G},\lambda )$. For $x\in V(\widehat{G})$, let $p(x)≔d_{\widehat{G}}(v,x)$. Then, $p$ is a real projection of $(\widehat{G},\lambda )$. Let $S>0$, and let $A\subseteq V(\widehat{G})$ be some maximal $(p,S)$-bounded set in $(\widehat{G},\lambda )$. Then, there exists some non-negative integer $t$ such that $A$ is the set of vertices in $(\widehat{G},\lambda )$ (or equivalently $G$) whose distance from $v$ is between $t$ and $t+\lceil S\rceil$; indeed, we can let $t≔\min \{p(x)\mid x\in A\}$.

Let $M$ be the set of maximal vertices of $G[A]$. Observe that $(\widehat{G},\lambda )[M]=G[M]$ contains no edge of weight 2 and furthermore that it is a graph in ${ℬ}_{\alpha }^d$. Let $f:A\to M$ be such that for every $u\in A$, $f(u)$ is some maximal vertex containing $u$. We shall show that $f$ is a $(2\lceil S\rceil +4,1)$-quasi-isometry from $(\widehat{G},\lambda )[A]$ to $G[M]$, which implies that $(\widehat{G},\lambda )[A]\in {ℒ}_{d,\alpha }^{2\lceil S\rceil +4}$ and therefore that ${\widehat{𝒞}}_{\alpha }^d$ is ${ℒ}_{d,\alpha }$-layerable as we desire.

If there is an edge of weight 1 or 2 between vertices $x$ and $y$ of $(\widehat{G},\lambda )[A]$, then $f(x)$ and $f(y)$ intersect or coincide, and therefore ${\mathrm{𝖽𝗂𝗌𝗍}}_{G[M]}(f(x),f(y))\le 1$. It follows that ${\mathrm{𝖽𝗂𝗌𝗍}}_{G[M]}(f(x),f(y))\le {\mathrm{𝖽𝗂𝗌𝗍}}_{(\widehat{G},\lambda )[A]}(x,y)$ for every pair of vertices $x,y\in A$.

Consider some $m\in M$. Note that $f^{-1}(m)$ is non-empty since $f(m)=m$, and so $f$ is surjective. We aim to show that each vertex $x$ of $f^{-1}(m)$ has distance at most $S+2$ from $m$ in $(\widehat{G},\lambda )[A]$. Let $x_0{x}_1\mathrm{\dots }{x}_{\mathrm{\ell }}$ be a $v$–$x$ geodesic in $(\widehat{G},\lambda )$ (or $G$), i.e. a path with $x_0=v$, $x_{\mathrm{\ell }}=x$ and $p(x_i)={\mathrm{𝖽𝗂𝗌𝗍}}_{(\widehat{G},\lambda )}(v,x_i)=i$ for each $i$. Then ${\bigcup }_{i=0}^{\mathrm{\ell }}{x}_i$ contains a curve $C$ from $x$ to a point in $v$ not contained in the interior of $z$ for any $z\in V(G)\backslash v$. Since the curve $C$ starts in the interior of $\mathrm{𝖼𝖼𝗅}(m)$ and ends outside the interior of $\mathrm{𝖼𝖼𝗅}(m)$, it follows that $m$ is adjacent in $G$ to some vertex of $\{x_0,\mathrm{\dots },x_{\mathrm{\ell }}$}. We further have that $m$ must be adjacent to one of $x_{p(m)-1},x_{p(m)},x_{p(m)+1}$. Note that $t\le p(m)\le p(x)=\mathrm{\ell }\le t+\lceil S\rceil$ since $m,x\in A$. If either $p(m)>t$ or $m$ is adjacent to one of $x_{p(m)}$ or $x_{p(m)+1}$, then there is a path in $G[A]$ (and thus in $(\widehat{G},\lambda )[A]$) between $m$ and $x$ of length at most $\lceil S\rceil +1$. So, we may assume now that $p(m)=t$ and that $m$ is non-adjacent to both $x_{p(m)}$ and $x_{p(m)+1}$. It follows that $x_{p(m)}$ is contained in $\mathrm{𝖼𝖼𝗅}(m)$ and that $m$ is adjacent to $x_{p(m)-1}$ in $G$. Therefore, there is an edge of weight 2 in $(\widehat{G},\lambda )$ between $m$ and $x_{p(m)}$. Hence, there is a path of length at most $\lceil S\rceil +2$ in $(\widehat{G},\lambda )[A]$ between $m$ and $x$. Thus, $x$ has distance at most $\lceil S\rceil +2$ from $m$ in $(\widehat{G},\lambda )[A]$.

So $f^{-1}(m)$ has radius at most $\lceil S\rceil +2$ in $(\widehat{G},\lambda )[A]$ and therefore diameter at most $2\lceil S\rceil +4$. Thus, as $G[M]$ is a graph, for every $x,y\in A$, we have that ${(2\lceil S\rceil +4)}^{-1}{\mathrm{𝖽𝗂𝗌𝗍}}_{(\widehat{G},\lambda )[A]}(x,y)-1\le {\mathrm{𝖽𝗂𝗌𝗍}}_{G[M]}(f(x),f(y))$. Hence $f$ is a $(2\lceil S\rceil +4)$-quasi-isometry between $(\widehat{G},\lambda )[A]$ and $G[M]$. $◀$

We have assembled all the ingredients to prove the main result of this section:

By lemma 16, the asymptotic dimension of ${𝒞}_{\alpha }^d$ and ${\widehat{𝒞}}_{\alpha }^d$ is equal. By lemma 17, ${\widehat{𝒞}}_{\alpha }^d$ is ${ℒ}_{d,\alpha }$-layerable. The graph classes ${ℒ}_{d,\alpha }^1,{ℒ}_{d,\alpha }^2,\mathrm{\dots }$ all have asymptotic dimension at most $2d+1$ by lemma 15 and theorem 13. Therefore, by theorem 14, ${\widehat{𝒞}}_{\alpha }^d$ has asymptotic dimension at most $2d+2$. Hence ${𝒞}_{\alpha }^d$ has asymptotic dimension at most $2d+2$. $◀$