$f$ to the vertices $f_{1}$ and $f_{2},$ thereby creating the tree $T.$ It is
straight forward to check that $(T,\beta)$ meets all requirements of the
strengthened claim which is a direct contradiction to the choice of our
counterexample. Observe that it is possible to determine if such a
decomposition exists, at least with a slightly worse approximation factor, by
using the techniques from [4].

Hence, in particular, we obtain that for each separation $(X_{1},X_{2})$ of
order at most $\alpha-1$ there exists a unique $i\in[2]$ such that $|X_{i}\cap
A|>|X_{1}\cap X_{2}|.$ This immediately implies that $A$ is a
$(\alpha,\frac{2}{3})$-linked set. Hence $\mathcal{T}\coloneqq\mathcal{T}_{A}$
is a tangle of order
$\alpha=2\mathsf{p}(6\mathbf{R}{(r_{1},t_{1},\dots,t_{k})}^{2})+1.$ We may now
use Theorem 3.1 to find a large wall whose associated tangle is a truncation
of $\mathcal{T}_{A}$ in time
$2^{\mathcal{O}(\mathsf{poly}(t)^{c_{2}})}|V(G)|^{2}|E(G)|\log(|V(G)|)$. By
Theorem 4.1 and the fact that $G$ does not contain $\mathscr{H}^{j}_{t_{j}}$
as a minor for any $j\in[k],$ we obtain a set $A_{f}\subseteq V(G)$ where

$\displaystyle|A_{f}|\leq\mathbf{v}_{\mathsf{b}}(T_{1},\dots,t_{k})(2\mathbf{v}_{\mathsf{d}}(t_{1},\dots,t_{k})+1)+\mathbf{a}(t_{1},\dots,t_{k}),$

a surface $\Sigma$ which is of Euler-genus at most
$\mathbf{g}_{\mathsf{o}}(t_{1},\dots,t_{k})$ if it is orientable and of Euler-
genus at most $\mathbf{g}_{\mathsf{n}}(t_{1},\dots,t_{k})$ otherwise, and a
$\Sigma$-decomposition $\delta$ of breadth at most
$\mathbf{v}_{\mathsf{b}}(t_{1},\dots,t_{k})$ and depth at most
$\mathbf{v}_{\mathsf{d}}(t_{1},\dots,t_{k})$ for $G-A_{f}$ which is
$(\mathcal{T}-A_{f})$-central.

What remains is to show how, for each cell $c$ of $\delta$ which has more than
two vertices on its boundary and at least one vertex in its interior, we
obtain a smaller graph with a bounded size set that will take the place of
$A.$ For each such graph, as it does not form a counterexample, we then obtain
a decomposition meeting the requirements of our strengthened claim. By
combining all of these tree decompositions we will finally find a
decomposition for $G$ and thereby contradict the existence of a
counterexample.

Before we do this, however, let $d\coloneqq
2\mathbf{v}_{\mathsf{d}}(t_{1},\dots,t_{k})$ and
$a\coloneqq\mathbf{a}(t_{1},\dots,t_{k}).$ Now observe that
$a+d+3<\mathbf{R}{(r_{1},t_{1},\dots,t_{k})}^{2}$ by the choice of $r_{1}$ and
the fact that the deletion of $a$ vertices of an
$\mathbf{R}(r_{1},t_{1},\dots,t_{k})$-wall still leaves an $r$-wall intact. It
follows that $a+d+3<\frac{1}{2}\alpha$ and thus, for any separation $(X,Y)$ of
$G$ of order at most $a+d+3$ we have $(X,Y)\in\mathcal{T}$ or
$(Y,X)\in\mathcal{T}.$ In case $(X,Y)\in\mathcal{T},$ we also get, from the
definition of $\mathcal{T},$ that $|(A\cap X)\cup(X\cap Y)|<\alpha.$ This
observation will allow us to obtain tree decompositions as desired for all
part of the graph we are about to separate from the graph drawn on the
boundaries of the cells of $\delta.$

Let $X_{f}$ be the collection of all vertices of $G-A_{f}$ which are drawn in
some vortex of $\delta$ together with the vertices of $A_{f}.$

Let $\mathcal{V}$ be the collection of all vortices of $\delta.$ For each
$c\in\mathcal{V}$ let $(G_{c},\Omega_{c})$ be the corresponding vortex
society, and let $n_{c}\coloneqq|V(\Omega_{c})|.$ Let us fix a linear order
$v^{c}_{1},\dots,v^{c}_{n_{c}}$ of $V(\Omega_{c})$ such that there exists a
linear decomposition $\langle
L^{c}_{1},\dots,L^{c}_{n_{c}},v^{c}_{1},\dots,v^{c}_{n_{c}}\rangle$ of
adhesion at most $\mathbf{v}_{\mathsf{d}}(t_{1},\dots,t_{k})$ of
$(G_{c},\Omega_{c}).$ We set $Y^{c}_{i}\coloneqq(L^{c}_{i}\cap
L^{c}_{i-1})\cup(L^{c}_{i}\cap L^{c}_{i+1})\cup\\{v^{c}_{i}\\}$ where
$L^{c}_{0}=L^{c}_{i+1}=\emptyset.$ Observe that every vertex drawn on the
closure of $c$ must belong to some $L^{c}_{i},$ moreover, we have that
$\bigcup_{i=1}^{n_{c}}L^{c}_{i}\subseteq X_{f}.$ Finally, let $A_{c}\coloneqq
Y^{c}_{i}\cup A_{f}\cup(L^{c}_{i}\cap A).$

For every $c\in\mathcal{V}$ and $i\in[n_{c}]$ let $H^{c}_{i}\coloneqq
G[L^{c}_{i}\cup A_{f}].$ Notice that $(V(G)\setminus(L^{c}_{i}\setminus
Y^{c}_{i}),L^{c}_{i}\cup A_{f})\in\mathcal{T}$ is a separation of order at
most $d+a+1$ in $G$ and $H^{c}_{i}-A_{f}=G_{c}[Y^{c}_{i}].$ Moreover, it
follows from the discussion above that $|A_{c}|<\alpha,$ and thus
$(V(G)\setminus(L^{c}_{i}\setminus(Y^{c}_{i}\cup A)),L^{c}_{i}\cup A_{f})$ is
a separation of order less than $\alpha$ in $G.$ Notice that htis argument
also yields the, bound $\alpha$ on the width of the linear decomposition
$\langle L^{c}_{1},\dots,L^{c}_{n_{c}}v^{c}_{1},\dots,v^{c}_{n_{c}}\rangle.$

By the minimality of our counterexample, we obtain a tree decomposition
$(T^{c}_{i},\beta^{c}_{i})$ with root $f^{c}_{i}$ satisfying the requirements
of the strengthened claim for every $H^{c}_{i},$ $A_{c},$ and
$t_{1},\dots,t_{k},r.$

Now let $\mathcal{C}$ be the collection of all non-vortex cells of $\delta.$
For every $c\in\mathcal{C}$ let $H^{c}$ be the subgraph of $G$ with vertex set
$V(\Sigma(c))\cup A_{f}$ and edge set $E(\Sigma(c))$ together with all edges
that have at least one endpoint in $A_{f}$ and the other in $V(H^{c}).$ Let
$N^{c}$ be the set of vertices of $G$ which are drawn on the boundary of the
closure of $c.$ Let $\Omega^{c}$ be the cyclic permutation of the vertices of
$N\setminus A$ obtained by following along the boundary of $c$ clockwise. By
deleting $A$ in addition to $A_{f}$ it is possible that we slightly changed
the way $H^{c}$ attaches to the rest of $G.$ To fix this, we apply Theorem 3.2
to $(H^{c}-A,\Omega^{c})$ and enhance $\delta$ by possibly refining $c$ into
smaller cells wherever possible. Note that the application of Theorem 3.2
guarantees that the formation of a torso by removing the interiors of non-
vortex cells yields a minor of $G.$ From now on, we will assume that all cells
have been refined in this way.

Observe that $(V(G)\setminus(V(\Sigma(c))\setminus N^{c}),V(H^{c}))$ is a
separation of $G$ of order at most $a+3<\frac{1}{2}\alpha.$ By the discussion
above and the fact that $\delta$ is $(\mathcal{T}-A_{f})$-central, it follows
that $(V(G)\setminus(V(\Sigma(c))\setminus N^{c}),V(H^{c}))\in\mathcal{T}$ and
$|A\cap V(H^{c})|\leq a+3<\frac{1}{2}\alpha.$ Hence,
$(V(G)\setminus(V(\Sigma(c))\setminus(N^{c}\cup A)),V(H^{c}))$ is a separation
of order less than $\alpha$ in $G.$

Let $H^{c}_{1},\dots H^{c}_{n_{c}}$ be the components of $H^{c}-A-A_{f}.$ Let
$A^{c}_{i}\coloneqq A_{f}\cup(V(H^{c})\cap
A)\cup(V(H^{c}_{i})\cap(V(G)\setminus(V(\Sigma(c))\setminus N^{c}))).$ For
each $c\in\mathcal{C}$ and $i\in[n_{c}]$ we obtain, from the minimality of our
counterexample, a tree decomposition $(T^{c}_{i},\beta^{c}_{i})$ with root
$f^{c}_{i}$ for $H^{c}_{i},$ $A^{c}_{i},$ and $t_{1},\dots,t_{k},$ which
satisfies the requirements of the strengthened claim.

We may now construct a tree decomposition for $G$ as follows. Let $f$ be a
vertex, let $X_{f}\coloneqq A\cup
A_{f}\cup\bigcup_{c\in\mathcal{V}}\bigcup_{i=1}^{n_{c}}Y^{c}_{i}$ and set

$\displaystyle\beta(f)\coloneqq
V(G)\setminus((\bigcup_{c\in\mathcal{C}\cup\mathcal{V}}\bigcup_{i\in[n_{c}]}V(H^{c}_{i}))\cup\bigcup_{c\in\mathcal{C}\cup\mathcal{V}}\bigcup_{i\in[n_{c}]}A^{c}_{i}).$

It follows from the construction of the $A^{c}_{i}$ and the definition of
$\delta$ that, for the torso $G_{f}$ of $G$ at $f$,$G_{f}-A-A_{f}$ has a
$\Sigma$-decomposition $\delta^{\prime}$ of depth at most
$\mathbf{v}_{\mathsf{d}}(t_{1},\dots,t_{k})$ and breadth at most
$\mathbf{v}_{\mathsf{b}}(t_{1},\dots,t_{k}).$ Moreover, $G_{f}-X_{f}$ is a
minor of $G$ since $X_{f}$ contains all vertices which are drawn in the
vortices of $\delta^{\prime}$ together with the apex set $A\cup A_{f}$ and
anything that attaches to this graph does so in separations of order at most
three which are obtained from applications of Theorem 3.2.

For every $c\in\mathcal{V}\cup\mathcal{C}$ and every $i\in[n_{c}]$ introduce
the edge $f^{c}_{i}f.$ And enhance $\beta$ by $\beta^{c}_{i}.$ Let $(T,\beta)$
be the resulting tree decomposition with root $f.$ We conclude by observing
that $(T,\beta)$ satisfies the requirements of the strengthened claim and thus
contradicts the choice of our counterexample. ∎

###  4.3 The local structure of a surface

The final piece of technology we will need is to describe how Kawarabayashi,
Thomas, and Wollan capture a surface in their version of the local structure
theorem [32].

The purpose of the following definitions is to introduce the concept of
$\Sigma$-configurations which are meant as a strengthening of
$\Sigma$-decompositions in a way that makes it possible to describe how a
clique minor might appear during the inductive process of constructing the
surface in the proof of Subsection 4.3. Please note that we will not make full
use of the infrastructure provided by a $\Sigma$-configuration. This is,
because a part of it is designed to be used within an induction where the
surface is built by iteratively finding large transactions.

######  Definition  (Nest).

Let $\rho=(\Gamma,\mathcal{D})$ be a rendition of a society $(G,\Omega)$ in a
surface $\Sigma$ and let $\Delta\subseteq\Sigma$ be an arcwise connected set.
A _nest in $\rho$ around $\Delta$ of order $s$_ is a sequence
$\mathcal{C}=(C_{1},C_{2},\dots,C_{s})$ of disjoint cycles in $G$ such that
each of them is grounded in $\rho,$ and the trace of $C_{i}$ bounds a closed
disk $\Delta_{i}$ in such a way that
$\Delta\subseteq\Delta_{1}\subsetneq\Delta_{2}\subsetneq\dots\subsetneq\Delta_{s}\subseteq\Sigma.$

Let $(G,\Omega)$ be a society and $\rho=(\Gamma,\mathcal{D})$ be a rendition
of $(G,\Omega)$ in a surface $\Sigma.$ Let $C$ be a cycle in $G$ that is
grounded in $\rho$ such that the trace $T$ of $C$ bounds a closed disk $D$ in
$\Sigma.$ Let $L$ be the subgraph of $G$ with vertex set
$\pi_{\rho}(N(\rho)\cap T)$ and no edges. We define the _outer graph of $C$ in
$\rho$_ as the graph

$\displaystyle L\cup\bigcup_{c\in C(\rho)\text{ and }c\not\subseteq
D}\Sigma(c)$

We define the _inner graph of $C$ in $\rho$_ as the graph

$\displaystyle L\cup\bigcup_{c\in C(\rho)\text{ and }c\subseteq D}\Sigma(c)$

Finally, we define the inner society of $C$ in $\rho$ as follows. Let
$\Omega^{\prime}$ be the cyclic permutation of $V(L)$ obtained by traversing
$T$ clockwise. If $G^{\prime}$ is the inner graph of $C$ in $\rho,$ then the
_inner society of $C$ in $\rho$_ is the society
$(G^{\prime},\Omega^{\prime}).$

Let $\mathcal{C}=\\{C_{1},\dots,C_{s}\\}$ be a collection of pairwise vertex-
disjoint cycles and $\mathcal{P}=\\{P_{1},\dots,P_{k}\\}$ be a linkage. We say
that $\mathcal{P}$ is _orthogonal_ to $\mathcal{C}$ if every $P_{i}$ has a
non-empty intersection with each cycle of $\mathcal{C}$ such that there exists
an endpoint $p_{i}$ of $P_{i}$ for which the cycles $C_{1},\dots,C_{s}$ appear
in the order listed when traversing along $P_{i}$ starting from $p_{i}$, and
$P_{i}\cap C_{j}$ is a (possibly trivial) subpath of $P_{i}$ for all
$i\in[k]$, $j\in[s]$.

Figure 11: An illustration of a pair $(\mathcal{C},\mathcal{P})$ overlaying a
wall $W$.

Let $G$ be a graph, $W$ a wall in $G,$ $\mathcal{C}$ a nest in $G,$ and
$\mathcal{P}$ a linkage which is orthogonal to $\mathcal{C}.$

We say that $(\mathcal{P},\mathcal{C})$ _overlays $W$_ if we can fix the
horizontal paths of $W$ to be $H_{1},\dots,H_{k}$ and the vertical paths
$V_{1},\dots,V_{\ell}$ such that there exist injective maps
$\phi_{\text{hor}}\colon\mathcal{C}\to\\{H_{1},\dots,H_{k}\\}$ and
$\phi_{\text{vert}}\colon\mathcal{P}\to\\{V_{1},\dots,V_{\ell}\\}$ such that
for all $P\in\mathcal{P}$ and $C\in\mathcal{C},$
$\phi_{\text{hor}}(C)\cap\phi_{\text{vert}}(P)\subseteq P\cap C.$ See Figure
11 for an illustration.

Let $C$ be some cycle grounded in a $\Sigma$-decomposition $\delta$ of a graph
$G$. We say that a linkage $\mathcal{L}$ is _coterminal with a linkage
$\mathcal{P}$ up to level $C$_ if there exists
$\mathcal{P}^{\prime}\subseteq\mathcal{P}$ such that
$H\cap\mathcal{L}=H\cap\mathcal{P^{\prime}}$ where $H$ denotes the outer graph
of $C$. When $\mathcal{C}=\\{C_{1},\dots,C_{\ell}\\}$ is a nest in $\delta$,
and it is clear from the context to which nest we are referring, we will
abbreviate “coterminal with $\mathcal{P}$ up to level $C_{i}$” by “coterminal
with $\mathcal{P}$ up to level $i$”.

######  Definition  ($\Sigma$-Configuration).

Let $G$ be a graph, let $\Sigma=\Sigma^{(h,c)}$ be a surface, and let
$\delta=(\Gamma,\mathcal{D})$ be a $\Sigma$-decomposition of $G.$ Let $W$ be a
wall in $G,$ $W_{1}$ a subwall of $W,$ and $W_{0}$ an $r$-subwall of $W_{1}.$
Assume that there exist cells $c_{0},c_{1}\in C(\delta)$ and a closed disk
$\Delta_{0}\subseteq\Sigma$ such that:

  * •

No cell in $C(\delta)\setminus\\{c_{0},c_{1}\\}$ is a vortex.

  * •

The vortex society $(G_{0},\Omega_{0})$ of $c_{0}$ in $\delta$ has a vortex-
free rendition, $W_{0}\subseteq G_{0},$ and there exists a vortex free
rendition of $(G_{0},\Omega_{0})$ for which $W_{0}$ is flat.

  * •

The cell $c_{0}\subseteq\Delta_{0}\subseteq\Sigma\setminus c_{1}$ and the
boundary of $\Delta_{0}$ intersect no cell of $\delta.$

  * •

The complementary society $(G_{2},\Omega_{2})$ to the vortex society of
$c_{0}$ has a cylindrical rendition
$\rho_{2}=(\Gamma_{2},\mathcal{D}_{2},c_{2})$ with a nest $\mathcal{C}_{2},$
where $\Gamma_{2}=\Gamma,$ $C(\rho_{2})\setminus c_{2}=\\{c\in C(\delta)\mid
c\subseteq\Delta_{0}\\}\setminus\\{c_{0}\\},$
$N(\rho_{2})=N(\delta)\cap\Delta_{0},$
$\Sigma_{\rho_{2}}(c_{2})=\bigcup_{c\not\subseteq\Delta_{0}}\Sigma_{\delta}(c),$
and $\Sigma_{\delta}(c)=\Sigma_{\rho_{2}}(c)$ for every $c\in
C(\rho_{2})\setminus\\{c_{2}\\}.$

  * •

The vortex society of $c_{1}$ in $\delta$ has a cylindrical rendition
$\rho_{1}=(\Gamma_{1},\mathcal{D}_{1},c_{1}^{\prime})$ with a nest
$\mathcal{C}_{1}.$

Let $\widetilde{\Delta_{0}}$ denote the set of vertices of $N(\rho)$ on the
boundary of $\Delta_{0}.$ Let $X_{1},X_{2}$ be two complementary segments of
$\Omega_{2}.$ Assume that there exists a set
$\gamma=\\{(\mathcal{L}_{i},X_{i}^{2})\mid i\in[c+h]\\}$ and disjoint linkages
$\mathcal{P}_{1},\mathcal{P}_{2}$ in $(G_{2},\Omega_{2})$ such that:

  * •

$\mathcal{P}_{1}$ is a linkage from $X_{1}$ to
$\Sigma_{\rho_{1}}(c_{1}^{\prime})$ which is orthogonal to both
$\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ and
$(\mathcal{P}_{1},\mathcal{C}_{1})$ overlays $W_{1}.$

  * •

The linkage $\mathcal{P}_{2}$ is a linkage from $X_{2}$ to
$\widetilde{\Delta_{0}}$ which is orthogonal to $\mathcal{C}_{2}$ and
$(\mathcal{P}_{1}\cup\mathcal{P}_{2},\mathcal{C}_{2})$ overlays $W_{1}.$

  * •

For $i\in[c+h],$ $\mathcal{L}_{i}$ is a transaction on $(G_{2},\Omega_{2})$
and $X^{2}_{i}\subseteq X_{2}$ is a segment of $\Omega_{2}.$ The transactions
$\mathcal{L}_{1},\dots,\mathcal{L}_{c+h}$ are pairwise disjoint with endpoints
in $X_{i}^{2}$ and, moreover, $X_{1}^{2},\dots,X^{2}_{c+h}$ are also pairwise
disjoint. For all $i,$ $\mathcal{L}_{i}$ is coterminal with $\mathcal{P}_{2}$
up to level $1$ of $\mathcal{C}_{2}$ in $\rho_{2}$ and $\mathcal{L}_{i}$ is
disjoint from $\Sigma_{\delta}(c_{1})$ and disjoint from $\mathcal{P}_{1}.$

  * •

The transactions $\mathcal{L}_{1},\dots,\mathcal{L}_{h}$ are handle
transactions, each of thickness $θ,$ and the transactions
$\mathcal{L}_{h+1},\dots,\mathcal{L}_{c+h}$ are crosscap transactions, each of
thickness $θ.$

  * •

Let $\mathcal{P}_{1}=\\{P_{1},\dots,P_{m}\\},$ for $i\in[m]$ let $x_{i}$ be
the endpoint of $P_{i}$ in $X_{1}$ and let $y_{i}$ be the last vertex of
$P_{i}$ in $\widetilde{c_{1}}.$ If $x_{1},\dots,x_{m}$ appear in $\Omega_{2}$
in the order listed, then $y_{1},\dots,y_{m}$ appear on $\widetilde{c_{1}}$ in
the order listed.

In those circumstances (neglecting the wall $W$) we say that
$(W_{1},W_{0},\delta,c_{0},c_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{P}_{1},\mathcal{P}_{2},\gamma)$
is a _$\Sigma$ -configuration_ with parameters
$(r,|\mathcal{C}_{1}|,|\mathcal{C}_{2}|,|\mathcal{P}_{1}|,θ,c,h).$ The cell
$c_{1}$ is called the _exceptional cell of $\delta$_.

For an illustration of a $\Sigma$-configuration consider (a), (b), and (c) in
Figure 12.

Figure 12: A $\Sigma$-configuration of a graph (a), (b), and (c)) together
with a rendition of bounded breadth and depth of its exceptional cell (d)).
(a) The vortex-free rendition of the vortex society of $c_{0}$ together with
the wall $W_{0}$ which is grounded in this rendition. On the boundary of
$c_{0}$ one can find one endpoint of every path in $\mathcal{P}_{1}$. Notice
that each such endpoint coincides with a branch vertex of $W_{0}$. (b) A
rendition of the complementary society $(G_{2},\Omega_{2})$ to the vortex
society of $c_{0}$. This rendition contains the nest $\mathcal{C}_{2}$ of the
special cell $c_{2}$, a part of the linkage $\mathcal{P}_{1}$ which connects
$W_{0}$ to the boundary of $c_{1}^{\prime}$, the transactions
$\mathcal{L}_{i}$ which are either handle or crosscap transactions on
$(G_{2},\Omega_{2})$ and reach into the interior of $c_{2}$. The linkage
$\mathcal{P}_{2}$ (not highlighted) consists of the subpaths of the members of
the $\mathcal{L}_{i}$ connecting the boundary of $c_{1}$ to the boundary of
$c_{2}$. Finally, the figure depicts the exceptional cell $c_{1}$. (c) The
cylindrical rendition of the vortex society of $c_{1}$, its vortex
$c_{1}^{\prime}$, its nest $\mathcal{C}_{1}$, and the remaining part of
$\mathcal{P}_{1}$. (d) An alternative rendition of the vortex society of
$c_{1}$, this time a rendition of bounded breadth and depth where each vortex
is surrounded by a private nest and each such nest together with its vortex
lives in a private disk. This rendition is guaranteed to exist due to
Subsection 4.3.

######  Proposition  (Theorem 11.4, [32]).

Let $r,s_{2},M,t\geq 1$ be integers with $M\geq t,$ $s_{2}\geq 2t.$ Let
$\mu=\left\lfloor\frac{1}{10^{5}t^{26}}t^{10^{7}t^{26}}\cdot M\right\rfloor.$
Let

$\displaystyle R=49152t^{24}(r+2s_{2})+\mu.$

Let $G$ be a graph, and let $W$ be an $R$-wall in $G.$ Then either $G$
contains $K_{t}$ as a minor, or there exist integers $c,h\geq 0$ with
$c+h\leq{t+1\choose 2},$ a set $A\subseteq V(G)$ of size at most $\mu,$ a
surface $\Sigma=\Sigma^{(h,c)}$, and a $\Sigma$-configuration
$(W_{1},W_{0},\delta,c_{0},c_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{P}_{1},\mathcal{P}_{2},\gamma)$
of $G-A$ with parameters $(r,M,s_{2},M,M,c,h)$.

Moreover, the vortex society of $c_{1}$ has a rendition
$\rho_{1}=(\Gamma_{1},\mathcal{D}_{1})$ of breadth at most $2t^{2}$ and depth
at most $\mu$ and such that

  * •

for each vortex cell $c\in C(\rho_{1})$ there exists a nest $\mathcal{C}_{c}$
of order $M$ in $\rho_{1}$ around the unique disk $\Delta\in\mathcal{D}$
corresponding to $c,$ and

  * •

for each vortex cell $c\in C(\rho_{1})$ let $\Delta_{c}\subseteq\Sigma$ be the
disk bounded by the trace of $C_{M}\in\mathcal{C}_{c},$ then for each pair of
distinct vortex cells $c,c^{\prime}\in C(\rho_{1})$ we have that
$\Delta_{c}\cap\Delta_{c^{\prime}}=\emptyset.$

For an illustration of the outcome of Subsection 4.3 see (a), (b), and (d) in
Figure 12. Please notice that the structure of the nests for the vortices of
$\rho_{1}$ is not made explicit in [32]. However, the existence of these nests
follows from the proofs as explained, for example, in [47].

##  5 The upper bound

We are finally ready to prove the upper bound portion of Theorem 1.2. To do
this we will first show how to extract a Dyck-grid of chosen order from a
$\Sigma$-configuration. Then, we use this technique to prove a local structure
theorem for the case where $\Sigma$ belongs to a fixed closed set of surfaces.

###  5.1 A local structure theorem for excluding Dyck-grids

######  Lemma .

Let $c,h,t,r,s_{2}$ be non-negative integers. In case $c=0$ let
$c_{0}=h_{0}=0,$ if $c=2p+1$ let $c_{0}=1$ and $h_{0}=p,$ and if $c=2p\neq 0$
let $c_{0}=2$ and $h_{0}=p-1.$ Finally, let $g=2h+c.$ Assume that

$\displaystyle r\geq 16t\text{, }M\geq(162^{2g}+4)t,\text{ and
}s_{2}\geq(162^{2g}+4)t.$

If $G$ is a graph with a $\Sigma$-configuration
$(W_{1},W_{0},\delta,c_{0},c_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{P}_{1},\mathcal{P}_{2},\gamma)$
with parameters $(r,M,s_{2},M,M,c,h)$ where $\Sigma=\Sigma^{(h,c)}$ then $G$
contains an $\mathscr{D}^{h+h_{0},c_{0}}_{t}$-expansion which is grounded in
$\delta$.

###### Proof.

The claim follows quickly from the assumptions on the numbers and the
definition of $\Sigma$-configurations.

Let us first describe how to find a mixed surface grid in the
$\Sigma$-configuration. Consider the $\Sigma$-configuration
$(W_{1},W_{0},\delta,o_{0},o_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{P}_{1},\mathcal{P}_{2},\gamma).$

In case $c+h=0$ we may conclude immediately as $W_{0}$ is an $r$-wall where
$r\geq 16t.$ Hence, $W_{0}$ contains the $(t,4t)$-cylindrical grid, and
therefore $\mathscr{D}_{t}^{(0,0)},$ as a minor. Moreover, $W_{0}$ is grounded
in $\delta$.

So from now on we may assume that $c+h\geq 1.$ We first collect the cycles
necessary for the cylindrical grid which will host the crosscap and handle
transactions. Let us number the cycles of $\mathcal{C}_{2}$ as
$C_{1},C_{2},\dots,C_{s_{2}}$ as in the definition of a nest. Let $H_{0}$ be
the subgraph of $G$ consisting of the union of the cycles
$C_{1},\dots,C_{162^{2g}t}.$ For each $i\in[c+h]$ let $Q_{i}$ be the subgraph
of $G$ obtained as follows. For each $L\in\mathcal{L}_{i}$ there exist paths
$P_{1},P_{2}\in\mathcal{P}_{1}$ such that $L$ is coterminal with
$\\{P_{1},P_{2}\\}$ up to level $162^{2g}t.$ For each $j\in[2],$ let $x_{j}$
be the last vertex of $P_{j}$ on $C_{162^{2g}t}$ when traversing along $P_{j}$
starting on $V(\Omega_{2}).$ Moreover, let $y_{j}$ be the last vertex of
$P_{j}$ in $C_{1}\cap L$ when traversing along $P_{j}$ starting on $x_{j}$ and
moving towards $\Sigma_{\rho_{1}}(c_{1}^{\prime}).$ Let $L^{\prime}$ be the
subpath of $L$ with endpoints $y_{1}$ and $y_{2}.$ Finally, we define
$\hat{L}$ to be the path $x_{1}P_{1}y_{1}L^{\prime}y_{2}P_{2}x_{2}.$ Observe,
that both $P_{1}$ and $P_{2}$ are orthogonal with
$\\{C_{1},\dots,C_{162^{2g}t}\\},$ and $L^{\prime}$ is internally disjoint
from $H_{0}.$ Then $Q_{i}$ is defined as the union of the paths $\hat{L}$ for
all $L\in\mathcal{L}_{i}.$ Now, let $H_{1}$ be the union of $H_{0}$ with the
graphs $Q_{i}$ for all $i\in[c+h].$

Observe that $H_{1}$ contains a mixed surface grid of order $162^{2g}t$ with
$c$ crosscaps and $h$ handles as a minor since each of the linkages
$\mathcal{L}_{i}$ has order at least $(162^{2g}+4)t$ which allows forgetting
$4t$ of the consecutive $L^{\prime}$-paths.

Finally, notice that every cycle in $\mathcal{C}_{2}$ is grounded in $\delta$.
Moreover, any path $\hat{L}$ as above closes two cycles with $C_{162^{2g}t}$,
each of which is grounded in $\delta$. It follows that $H_{1}$ is grounded in
$\delta$ and thus, the claim now follows from Theorem 2.1. ∎

We now have everything in place to prove the local structure theorem for
excluding Dyck-grids. The statement we prove here is more general than the one
required Theorem 1.1 as we want to allow for the exclusion of any pair of
incomparable surfaces. That is, in the following we fix an Euler-genus
$g_{1}=2h_{1}$ and an Euler-genus $g_{2}=c_{2}+2h_{2}$ where $c_{2}\in[2]$ and
$g_{1}$ represents a surface of orientable genus $h_{1}$ while $g_{2}$
represents a non-orientable surface. To ensure that the two surfaces are
incomparable, we also require $0\leq h_{2}<h_{1}$ since otherwise we could
find a Dyck-grid with $h_{1}$ handles as a minor in any Dyck-grid with $h_{2}$
handles and $c_{2}$ crosscaps.

######  Theorem 5.1.

Let $k,h_{1},h_{2},c_{2}$ be non-negative integers where $c_{2}\in[0,2]$ and
$0\leq h_{2}<h_{1}.$ Let $g_{1}\coloneqq 2h_{1},$ $g_{2}\coloneqq
c_{2}+2h_{2}$ if $c_{2}\neq 0$ and $g_{2}\coloneqq 0$ otherwise, and
$g\coloneqq\max\\{g_{1},g_{2}\\}$. Moreover, fix $t\coloneqq 12(162^{2g}+4)k.$

Define

$\displaystyle\mathbf{a}_{g_{1},g_{2}}$ $\displaystyle\coloneqq
t^{10^{7}t^{26}}$ $\displaystyle\mathbf{g}_{\mathsf{o},g_{1},g_{2}}$
$\displaystyle\coloneqq g_{1}-1$
$\displaystyle\mathbf{g}_{\mathsf{n},g_{1},g_{2}}$ $\displaystyle\coloneqq
g_{2}-1\text{ if }c_{0}\neq 0\text{, and }g_{1}\text{ otherwise}$
$\displaystyle\mathbf{v}_{\mathsf{b},{g_{1},g_{2}}}$ $\displaystyle\coloneqq
2t^{2}$ $\displaystyle\mathbf{v}_{\mathsf{d},{g_{1},g_{2}}}$
$\displaystyle\coloneqq t^{10^{7}t^{26}}$
$\displaystyle\mathbf{R}_{g_{1},g_{2}}$ $\displaystyle\coloneqq
49152t^{24}(r+16t)+\left\lceil\frac{5}{2}t^{10^{7}t^{26}}\right\rceil.$

Moreover, we set

$\mathfrak{D}_{g_{1},g_{2}}\coloneqq\\{\mathscr{D}^{(h_{1},0)}=\langle\mathscr{D}^{(h_{1},0)}_{i}\rangle_{i\in\mathbb{N}},\mathscr{D}^{(h_{2},c_{2})}=\langle\mathscr{D}^{(h_{2},c_{2})}_{i}\rangle_{i\in\mathbb{N}}\\}$

in case $c_{2}\neq 0$ and

$\mathfrak{D}_{g_{1},g_{2}}\coloneqq\\{\mathscr{D}^{(h_{1},0)}=\langle\mathscr{D}^{(h_{1},0)}_{i}\rangle_{i\in\mathbb{N}}\\}$

otherwise. Then the local structure theorem
$\mathfrak{S}(\mathfrak{D}_{g_{1},g_{2}},\mathbf{a}_{g_{1},g_{2}},\mathbf{g}_{\mathsf{o},g_{1},g_{2}},\mathbf{g}_{\mathsf{n},g_{1},g_{2}},\mathbf{v}_{\mathsf{b},{g_{1},g_{2}}},\mathbf{v}_{\mathsf{d},{g_{1},g_{2}}},\mathbf{R}_{g_{1},g_{2}})$
is valid.

To prove Theorem 5.1 we start by showing that we can always either find a
Dyck-grid of order $k$ which corresponds to one of the two fixed Euler-genus
$g_{1}$ and $g_{2}$, or we find a $\Sigma$-configuration whose parameters
depend only on $k,$ $g_{1},$ and $g_{2}$ where the Euler-genus of $\Sigma$ is
strictly less than $g_{1}$ if $\Sigma$ is orientable, and strictly less than
$g_{2}$ if $\Sigma$ is non-orientable and $g_{2}\neq 0$ or at most $g_{1}$ if
$\Sigma$ is non-orientable but $g_{2}=0,$

######  Lemma .

Let $k,h_{1},h_{2},c_{2}$ be non-negative integers where $c_{2}\in[0,2]$ and
$0\leq h_{2}<h_{1}.$ Let $g_{1}\coloneqq 2h_{1},$ $g_{2}\coloneqq
2h_{2}+c_{2}$ if $c_{2}\neq 0$ and $g_{2}\coloneqq 0$ otherwise, and
$g\coloneqq\max\\{g_{1},g_{2}\\}$. Moreover, let $t\geq 12(162^{2g}+4)k$ be an
integer.

Finally, let $r,s_{2},M\geq 1$ be integers with $r\geq 16t,$ $s_{2}\geq 2M\geq
2t,$ and set
$\mu\coloneqq\left\lfloor\frac{1}{10^{5}t^{26}}t^{10^{7}t^{26}}\cdot
M\right\rfloor.$ Fix

$\displaystyle R\coloneqq 49152t^{24}(r+2s_{2})+\mu.$

Let $G$ be a graph, and let $W$ be an $R$-wall in $G.$

Then either $G$ contains $\mathscr{D}^{(h_{1},0)}_{k}$ or, in case $c_{2}\neq
0,$ $\mathscr{D}^{(h_{2},c_{2})}_{k}$ as a minor, or there exist integers
$c,h\geq 0$ with $2h<g_{1},$ $2h+c<g_{2}$ if $c\neq 0$ and $c_{2}\neq 0,$ and
$2h+c\leq g_{1}$ if $c\neq 0$ and $c_{2}=0,$ a set $A\subseteq V(G)$ of size
at most $\mu,$ a surface $\Sigma=\Sigma^{(h,c)}$, and a $\Sigma$-configuration
$(W_{1},W_{0},\delta,o_{0},o_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{P}_{1},\mathcal{P}_{2},\gamma)$
of $G-A$ with parameters $(r,M,s_{2},M,M,c,h)$.

Moreover, the vortex society of $o_{1}$ has a rendition $\rho_{1}$ of breadth
at most $2t^{2}$ and depth at most $\mu$ such that

  * •

for each vortex cell $c\in C(\rho_{1})$ there exists a nest $\mathcal{C}_{c}$
of order $M$ in $\rho_{1}$ around the unique disk $\Delta\in\mathcal{D}$
corresponding to $c,$ and

  * •

for each vortex cell $c\in C(\rho_{1})$ let $\Delta_{c}\subseteq\Sigma$ be the
disk bounded by the trace of $C_{M}\in\mathcal{C}_{c},$ then for each pair of
distinct vortex cells $c,c^{\prime}\in C(\rho_{1})$ we have that
$\Delta_{c}\cap\Delta_{c^{\prime}}=\emptyset.$

###### Proof.

We use Subsection 4.3 to either obtain a $K_{t}$-minor or a set $A\subseteq
V(G)$ of size at most $\mu$ together with integers $c,h\leq{t+1\choose 2},$ a
surface $\Sigma$ of Euler-genus $2h+c,$ and a $\Sigma$-configuration
$(W_{1},W_{2},\delta,o_{0},o_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\gamma)$
of $G-A$ with parameters $(r,M,s_{2},M,M,c,h)$ such that the vortex society of
$c_{1}$ in $\delta$ has depth at most $\mu$ and breadth at most $2t^{2}$
together with the desired properties for the nests.

In case we find the $K_{t}$-minor, we contain every graph on $12(162^{2g}+4)k$
vertices as a minor and thus, in particular, both
$\mathscr{D}^{(h_{1},0)}_{k}$ and $\mathscr{D}^{(h_{2},c_{2})}_{k}.$ So in
this case we are done.

In case $c=2n\neq 0,$ let $h^{\prime}\coloneqq h+n-1$ and $c^{\prime}\coloneqq
2$, similarly, if $c=0$ we set $h^{\prime}\coloneqq h$ and
$c^{\prime}\coloneqq c=0$. Moreover, if $c=2n+1,$ let $h^{\prime}\coloneqq
h+n$ and $c^{\prime}\coloneqq 1.$ By Subsection 5.1 we find
$D\coloneqq\mathscr{D}^{(h^{\prime},c^{\prime})}_{12k}$ as a minor of $G.$

What follows is an analysis on the numbers $h^{\prime},c^{\prime},c,$ and $h$
in relation to $g_{1}$ and $g_{2}.$

Suppose $h^{\prime}\geq h_{1},$ then $D$ contains
$\mathscr{D}_{k}^{(h_{1},0)}$ as a minor, and we are done. So we may assume
$h^{\prime}<h_{1}$ in the following. This settles the cases where $c=0$ or
$c_{2}=0$ since both situations imply that $2h^{\prime}+c^{\prime}\leq
2h<g_{1}.$

From now on we may assume $c,c_{2}\neq 0$ which implies that
$c^{\prime},c_{2}\in[2].$

Let us first assume that $c^{\prime}=1$ and $2h^{\prime}+c^{\prime}\geq
2h_{2}+c_{2}.$ If $c_{2}=1$ we immediately obtain $h^{\prime}\geq h_{2}.$
Hence, we may find $\mathscr{D}^{(h_{2},c_{2})}_{k}$ as a minor in $D$ as
desired. So we may assume $c_{2}=2.$ In this case, however, since the two sums
have different parity we obtain $h^{\prime}>h_{2}.$ We now use Subsection 2.3
to obtain the surface grid $D^{\prime}$ of order $k$ with $h^{\prime}-1$
handles and $c^{\prime}+2$ crosscaps as a minor within $D.$ As
$h^{\prime}-1\geq h_{2}$ and certainly $c^{\prime}+2>c_{2}$ we find
$\mathscr{D}^{(h_{2},c_{2})}_{k}$ as a minor in $D^{\prime}.$

For the final case we assume $c^{\prime}=2$ and again
$2h^{\prime}+c^{\prime}\geq 2h_{2}+c_{2}.$ Since this means $c^{\prime}\geq
2\geq c_{2}\geq 1$ we also obtain $h^{\prime}\geq h_{2}$ which immediately
implies the presence of a $\mathscr{D}^{(h_{2},c_{2})}_{k}$-minor in $D$ as
desired and our proof is complete. ∎

###  5.2 Proof of Theorem 5.1

With Subsection 5.1 at hand our proof of Theorem 5.1 becomes an analogue of
the proof for Theorem 2.11 from [32]. However, we split the proof in half to
make an intermediate structure accessible for future applications. The reason
for this is the requirement of a local structure theorem to produce a
$\Sigma$-decomposition which is $W$-central with respect to a large wall. The
way $W$-centrality is achieved in [32] is by removing additional vertex sets
from the vortices which potentially damages the surrounding nests. Some
applications might need access to the nests around vortices after the fact,
and thus we include an intermediate step here.

The main reason most of the structural theory talks about walls rather than
grids is that walls are subcubic graphs and as such, if they are contained as
minors in a graph, one can find a subdivision as a subgraph. For a similar
reason we define Dyck-walls. Let $c\in[0,2]$, $h$, and $t$ be non-negative
integers. The _elementary $(h,c;t)$-Dyck-wall_ is obtained from
$\mathcal{D}^{h,c}_{2t}$ by deleting the cycles $C_{t+1},\dots,C_{2t}$ and by
deleting the edge $v^{i}_{j}v^{i+1}_{j}$ for every odd $i\in[t-1]$ and every
odd $j\in[8t]$ and for every even $i\in[t-1]$ and even $j\in[8t]$. Moreover,
for each handle and crosscap that was added to create $\mathcal{D}^{h,c}_{2t}$
delete every edge starting on $v^{1}_{\ell}$ where $\ell$ is even. That is, we
delete every second edge. An _$(h,c;t)$ -Dyck-wall_ is a subdivision of the
elementary $(h,c;t)$-Dyck-wall.

Consider an embedding of a $(h,c;t)$-Dyck-wall $D$ in a surface $\Sigma$ of
Euler-genus $2h+c$. Then $C_{t}$ bounds a disk in which no vertex of $D$ is
drawn. We call this disk the _simple face_ of $D$. Similarly, there exists a
unique face which is incident to $C_{1}$ and every handle and every crosscap
of $D$. We call this face the _exceptional face_ of $D$.

Moreover, we will need the following seminal result of Grohe. We say that a
graph $G$ is _quasi- $4$-connected_ if for every separation $(A_{1},A_{2})$ of
order at most three in $G$ there exists a unique $i\in[2]$ such that
$|A_{i}\setminus A_{3-i}|\leq 1$.

######  Proposition  ([25]).

Every graph $G$ has a tree-decomposition $(T,\beta)$ of adhesion at most three
such that for all $t\in V(T)$ the torso $G_{t}$ of $G$ at $t$ is a minor of
$G$ that is either quasi-$4$-connected or a complete graph of order at most
four.

We call a graph $H$ that appears as the torso of a node in a tree-
decomposition of $G,$ as in Subsection 5.2, a _quasi- $4$-connencted
component_ of $G$.

We now provide the following consequence of Subsection 5.1 that reveals
several features of the local structure of a graph where a Dyck-grid is
excluded. Subsection 5.2 is of independent interest and may serve as the
departure point of future developments.

######  Lemma .

Let $h_{1},h_{2},c_{2}$ be non-negative integers where $c_{2}\in[0,2]$ and
$0\leq h_{2}<h_{1}.$ We set

$\displaystyle g_{1}$ $\displaystyle\coloneqq$ $\displaystyle 2h_{1},$
$\displaystyle g_{2}$ $\displaystyle\coloneqq$
$\displaystyle\begin{dcases*}2h_{2}+c_{2}&if $c_{2}\neq 0$\,,\\\\[4.30554pt]
0&otherwise\end{dcases*},and$ $\displaystyle g$ $\displaystyle\coloneqq$
$\displaystyle\max\\{g_{1},g_{2}\\}.$

Let also $k$, $r$, q be non-negative integers, where, $r\geq 16\cdot
12(162^{2g}+4)k$ and $q\geq 6k$, and set

$\displaystyle t$ $\displaystyle\coloneqq$ $\displaystyle 12(162^{2g}+4)k,$
$\displaystyle M$ $\displaystyle\coloneqq$ $\displaystyle 2(162^{2g}+4)q,$
$\displaystyle\mu$ $\displaystyle\coloneqq$
$\displaystyle\left\lfloor\frac{1}{10^{5}t^{26}}t^{10^{7}t^{26}}\cdot
M\right\rfloor,\mbox{\leavevmode\nobreak\ and\leavevmode\nobreak\ }$
$\displaystyle R$ $\displaystyle\coloneqq$ $\displaystyle 49152\cdot
t^{24}(r+4M)+\mu.$

If a graph $G$ contains an $R$-wall $W$, then either,

  1. 1.

$G$ contains $\mathscr{D}^{(h_{1},0)}_{k}$ or, in case $c_{2}\neq 0,$
$\mathscr{D}^{(h_{2},c_{2})}_{k}$ as a minor, or

  2. 2.

there exist

     * •

a surface $\Sigma\coloneqq\Sigma^{(h,c)}$ where

       * –

$2h<g_{1}$,

       * –

if $c\neq 0$ and $c_{2}\neq 0$ then $2h+c<g_{2}$, and

       * –

if $c\neq 0$ and $c_{2}=0$ then $2h+c\leq g_{1}$,

     * •

a set $A\subseteq V(G)$ of size at most $\mu,$ and

     * •

a $\Sigma$-decomposition $\delta=(\Gamma,\mathcal{D})$ of $G-A$ with the
following properties:

       1. (a)

$\delta$ is of breadth at most $2t^{2}$ and depth at most $\mu$,

       2. (b)

if we define $c_{0}$ and $h_{0}$ as follows:

          * –

if $c=0$, let $c_{0}\coloneqq 0$ and $h_{0}\coloneqq h$,

          * –

if $c>0$ and $c+2h$ is even, let $c_{0}\coloneqq 2$ and
$h_{0}\coloneqq\frac{c+2h}{2}-1$, and

          * –

otherwise, let $c_{0}\coloneqq 1$ and $h_{0}\coloneqq\frac{c+2h-1}{2}$,

then there exists an $(h_{0},c_{0};q)$-Dyck-wall $D$ in $G-A$ such that $D$ is
grounded in $\delta$

       3. (c)

there exists an $r$-subwall $W^{\prime}$ of $W$ such that $W^{\prime}$ is
grounded in $\delta,$ and $W^{\prime}$ is drawn in the interior of the disk
defined by the trace of the boundary of the simple face of $D$,

       4. (d)

for each vortex cell $v\in C(\delta)$ there exists a nest $\mathcal{C}_{v}$ of
order $M$ in $\delta$ around the unique disk $\Delta\in\mathcal{D}$
corresponding to $v,$

       5. (e)

for each vortex cell $v\in C(\delta)$ let $\Delta_{v}\subseteq\Sigma$ be the
disk bounded by the trace of $C_{M}\in\mathcal{C}_{v},$ then for each pair of
distinct vortex cells $v,v^{\prime}\in C(\delta)$ we have that
$\Delta_{v}\cap\Delta_{v^{\prime}}=\emptyset,$

       6. (f)

let $\widetilde{\Delta}$ be the disk in $\Sigma$ which is bounded by the trace
of the exceptional face of $D$ and does not contain any vertex of
$W^{\prime}$, for every every vortex $v\in C(\delta)$ we have
$\Delta_{v}\subseteq\widetilde{\Delta}$,

       7. (g)

let $X$ be the set of all vertices of $G$ drawn in the interior of cells of
$\delta$ and let $G_{\delta}$ be the torso of the set $V(G)\setminus(X\cup A)$
in $G-A$, then $G_{\delta}$ is a quasi-$4$-connected component of $G-A$, and

       8. (h)

finally if holds that $\mathcal{T}_{W^{\prime}}\subseteq\mathcal{T}_{W}$ and
$\mathcal{T}_{D}\subseteq\mathcal{T}_{W}$.

###### Proof.

By our choice of parameters we may immediatelly call upon Subsection 5.1. The
first possible outcome of Subsection 5.1 yields a minor model of
$\mathscr{D}^{(h_{1},0)}_{k}$ or, in case $c_{2}\neq 0,$ of
$\mathscr{D}^{(h_{2},c_{2})}_{k}.$

The second outcome provides us with integers $c,h\geq 0$ with $2h<g_{1},$
$2h+c<g_{2}$ if $c\neq 0$ and $c_{2}\neq 0,$ and $2h+c\leq g_{1}$ if $c\neq 0$
and $c_{2}=0,$ a set $A\subseteq V(G)$ of size at most $\mu,$ a surface
$\Sigma$ of Euler-genus $c+2h,$ which can be obtained from the sphere by
adding $h$ handles and $c$ crosscaps, and a $\Sigma$-configuration
$(W_{1},W_{0},\delta,o_{0},o_{1},\Delta_{0},\mathcal{C}_{1},\mathcal{C}_{2},\mathcal{P}_{1},\mathcal{P}_{2},\gamma)$
of $G-A$ with parameters $(r,M,2M,M,M,c,h)$.

Additionally, we have that the vortex society of $o_{1}$ has a rendition
$\rho_{1}=(\Gamma_{1},\mathcal{D}_{1})$ of breadth at most $2t^{2}$ and depth
at most $\mu$ such that

  * •

for each vortex cell $c\in C(\rho_{1})$ there exists a nest $\mathcal{C}_{c}$
of order $M$ in $\rho_{1}$ around the unique disk $\Delta\in\mathcal{D}$
corresponding to $c,$ and

  * •

for each vortex cell $c\in C(\rho_{1})$ let $\Delta_{c}\subseteq\Sigma$ be the
disk bounded by the trace of $C_{M}\in\mathcal{C}_{c},$ then for each pair of
distinct vortex cells $c,c^{\prime}\in C(\rho_{1})$ we have that
$\Delta_{c}\cap\Delta_{c^{\prime}}=\emptyset.$

We extend $\delta$ to a $\Sigma$-decomposition
$\delta^{\prime}=(\Gamma^{\prime},\mathcal{D})$ of $G-A$ by fixing a vortex
free rendition of the vortex society of $o_{0}$ such that the wall $W_{0}$ is
flat in the rendition and fixing a rendition of breath at most $2t^{2}$ and
depth at most $\mu$ of the vortex society of $o_{1}.$ Thus, $\delta^{\prime}$
has breath at most $2t^{2}$ and depth at most $\mu.$

Next, Subsection 5.1 provides us with a minor-model $D^{\prime}$ of
$\mathscr{D}^{h_{0},c_{0}}_{2q}$ which is grounded in $\delta^{\prime}$.
Notice that $D^{\prime}$ contains an $(h_{0},c_{0};q)$-Dyck-wall $D$ as a
subgraph which still is grounded in $\delta^{\prime}$. In particular,
$D^{\prime}$ is also grounded in $\delta$, implying that $D$ is as well. From
the construction of $D^{\prime}$ from the mixed surface grid in Subsection 5.1
it follows that $o_{0}$ sits in the disk bounded by the trace of the simple
face of $D$ while $o_{1}$ belongs to the disk bounded by the exceptional face
of $D$.

We now start to further modify $\delta^{\prime}$ by iterating the following
operation exhaustively. Let $(Y_{1},Y_{2})$ be a separation of order at most
three in $G-A$ such that $Y_{1}\cap Y_{2}$ consists of nodes of
$\delta^{\prime}$ and assume that $(Y_{1},Y_{2})$ does not cross any
separation induced by a non-vortex cell of $\delta^{\prime}$. That is, we
assume that there does not exist a non-vertex cell $x\in C(\delta^{\prime})$
such that $V(\sigma^{\prime}(x))\cap(Y_{1}\setminus Y_{2})\neq\emptyset$ and
$V(\sigma^{\prime}(x))\cap(Y_{2}\setminus Y_{1})\neq\emptyset$. By the
submodularity of separations we may always find such a separation
$(Y_{1},Y_{2})$ if some separation of order at most three with only nodes in
its separator exists. We start with separations of order one, then consider
separations of order two, and finally separations of order three. Without loss
of generality we may assume that $Y_{1}$ contains a row and a column of
$W_{0}$. Moreover, we assume that $Y_{2}$ is maximal with respect to set
containment. This implies that $Y_{1}\setminus Y_{2}$ is connected. Indeed, it
follows from the definition of $\Sigma$-configurations and the
$3$-connectivity of Dyck-grids that also at most one branch vertex of $D$ may
be contained in $Y_{2}\setminus Y_{1}$. Now suppose $Y_{2}\setminus Y_{1}$
contains a node of $\delta^{\prime}$. Let $C_{(Y_{1},Y_{2})}$ be the
collection of all cells $x$ of $\delta^{\prime}$ such that
$V(\sigma^{\prime}(x))\cap(Y_{2}\setminus Y_{1})\neq\emptyset$. It follows
that $V(\sigma^{\prime}(x))\subseteq Y_{2}$ for all $x\in C_{(Y_{1},Y_{2})}$
by our choice of $(Y_{1},Y_{2})$. We may now define a new cell
$c_{(Y_{1},Y_{2})}$ replacing all cells in $C_{(Y_{1},Y_{2})}$ as follows. Let
$\Delta_{(Y_{1},Y_{2})}$ be the disk which is the closure of $\bigcup_{c\in
C_{(Y_{1},Y_{2})}}c$. Now let $c_{(Y_{1},Y_{2})}$ be the cell obtained by
removing the points $\pi^{\prime-1}(y)$, $y\in Y_{1}\cap Y_{2}$, from
$\Delta_{(Y_{1},Y_{2})}$, and notice that all vertices of $Y_{2}\setminus
Y_{1}$ are drawn into the interior of $c_{(Y_{1},Y_{2})}$. Then forget all
cells in $C_{(Y_{1},Y_{2})}$. Let
$\delta^{\prime\prime}=(\Gamma^{\prime\prime},\mathcal{D}^{\prime\prime})$ be
the $\Sigma$-decomposition obtained once the above operation cannot be applied
any more. Notice that $D$ is still grounded in $\delta^{\prime\prime}$ and so
is $W_{0}$. The same is true for all cycles from the nests of the vortices of
$\delta^{\prime\prime}$. This implies that the torso
$G_{\delta^{\prime\prime}}$ contains a Dyck-wall $D^{\prime\prime}$ of the
same order as $D$ which can be obtained by contracting some edges of $D$ and
is quasi-$4$-connected.

If follows that the set $S$ of vertices of $G-A$ corresponding to the nodes of
$\delta^{\prime\prime}$ cannot be split further by separations of order at
most three and $S$ is minimal with this property. Hence, by applying
Subsection 5.2 there must exist a bag of the resulting tree-decomposition
whose vertex set is exactly $S$.

So far we can observe that $\delta^{\prime\prime}$ satisfies condition a)
since it is of breadth at most $2t^{2}$ and depth at most $\mu$. It also holds
that $D$ is grounded in $\delta^{\prime\prime}$ and none of its vertices are
drawn in $\Delta_{c}$ for any vortex of $\delta^{\prime\prime}$, hence
property b) is satisfied. The wall $W_{0}$ is an $r$-subwall of $W$ which is
drawn in the disk bounded by the trace of the simple face of $D$ and rooted in
$\delta^{\prime\prime}$ which implies property c). Moreover, every vortex of
$\delta^{\prime\prime}$ is contained in the disk bounded by the exceptional
face of $D$ as required by d) and all vortices are equipped with nests of
order $M$ which is property e).

These nests are pairwise disjoint and belong to their private disks, hence f)
is satisfied. Finally, the construction above ensures that
$G_{\delta^{\prime\prime}}$ is quasi-$4$-connected and so we also get property
g).

So we are left with discussing the tangles. For this observe that, by the
definition of $\Sigma$-configurations, $W_{0}$ is a subwall of $W_{1}$,
$W_{1}$ is a subwall of $W$, and
$(\mathcal{P}_{1}\cup\mathcal{P}_{2},\mathcal{C}_{2})$ overlays $W_{1}$.
Recall that $D$ consists entirely of cycles from $\mathcal{C}_{2}$ and the
paths from $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$. Since $r,q<M$ it follows
that the $W$-majority side of any separation of order less than $r$ must also
be the $W_{0}$-majority side and the $W$-majority side of any separation of
order less than $q$ must also be the $D$-majority side. Hence, also property
h) holds as desired and our proof is complete. ∎

An advantage of Subsection 5.2 over Theorem 5.1 is that here the parameter $M$
is freely choosable, as long as it is at least $t$. This means that one may
increase the order of the Dyck-wall and the nests around the vortices
arbitrarily and independent of the excluded minors. We continue with the final
step in the proof of Theorem 5.1.

The proof of Subsection 5.2 can be turned into an algorithm that given a graph
$G$, $k,h_{1},h_{2},c_{2},r,M$ and an $R$-wall as above, computes the
structures implied by Subsection 5.2 in time

$\mathcal{O}(M^{2}\cdot 2^{\mathsf{poly}(k\cdot
2^{\max\\{2h_{1},2h_{2}+c_{2}\\}})}|V(G)|^{2}+|V(G)|^{3}).$

This running time comes from two different sources. The quadratic, in
$|V(G)|$, part is due to us calling Subsection 5.1 which in turn calls
Subsection 5.1 from [32]. Here the only additional work that needs to be done
is the extraction of the Dyck-wall as describe din the proof of Subsection
5.1. Since this is purely handling a bounded size object, the main
contribution stems indeed from Subsection 5.1. The second term, cubic in
$|V(H)|$, comes from the refinement of our $\Sigma$-decomposition. In
particular from the requirement that $G_{\delta^{\prime\prime}}$ is
quasi-$4$-connected in the end which makes it necessary to consider all
possible separations of order at most three.

######  Proposition  ([40, 32]).

Let $d\geq 0$ be an integer. Every society of depth at most $d$ has a linear
decomposition of adhesion at most $d.$

###### Proof of Theorem 5.1.

Let us start by discussing the numbers. We set

$\displaystyle M$ $\displaystyle\coloneqq t,$ $\displaystyle s_{2}$
$\displaystyle\coloneqq 2t,$ $\displaystyle r^{\prime}$
$\displaystyle\coloneqq
r+16t+\left\lfloor\frac{1}{10^{5}t^{24}}t^{10^{7}t^{26}}\right\rfloor\text{,
and}$ $\displaystyle\mu$
$\displaystyle\coloneqq\left\lfloor\frac{1}{10^{5}t^{25}}t^{10^{7}t^{26}}\right\rfloor.$

Let $R\coloneqq 49152t^{24}(r^{\prime}+2s_{2})+\mu$ be the constant from
Subsection 5.1 and notice that

$\displaystyle R=49152t^{24}(r^{\prime}+2s_{2})+\mu$
$\displaystyle=49152t^{24}(r^{\prime}+4t)+\mu$ $\displaystyle\leq
49152t^{24}\left(r+16t+\left\lfloor\frac{1}{10^{5}t^{24}}t^{10^{7}t^{26}}\right\rfloor+4t\right)+\left\lfloor\frac{1}{10^{5}t^{25}}t^{10^{7}t^{26}}\right\rfloor$
$\displaystyle\leq
49152t^{24}(r+16t)+\frac{49152t^{24}}{10^{5}t^{24}}t^{10^{7}t^{26}}+2\cdot
10^{5}t^{25}+\left\lfloor\frac{1}{10^{5}t^{25}}t^{10^{7}t^{26}}\right\rfloor$
$\displaystyle\leq
49152t^{24}(r+16t)+\frac{1}{2}t^{10^{7}t^{26}}+2\cdot\frac{10^{5}t^{25}}{10^{5}t^{25}}t^{10^{7}t^{26}}$
$\displaystyle\leq
49152t^{24}(r+16t)+\left\lceil\frac{5}{2}t^{10^{7}t^{26}}\right\rceil=\mathbf{R}_{g_{1},g_{2}}.$

Moreover, we have ensured that $r^{\prime}\geq 16t.$ Let $W$ be an
$\mathbf{R}_{g_{1},g_{2}}$-wall in a graph $G.$

We may call upon Subsection 5.2 with the numbers $k,h_{1},h_{2},c_{2},$
$r^{\prime},s_{2},M$ and $\mu$ and the wall $W.$ In case we find
$\mathscr{D}^{(h_{1},0)}_{k}$ or $\mathscr{D}^{(h_{2},c_{2})}_{k}$ as a minor
we are done, so we may assume the final outcome of Subsection 5.2 to hold.

This means we find a set $A\subseteq V(G)$ of size at most $\mu$ and
$\Sigma$-decomposition $\delta=(\Gamma,\mathcal{D})$ of $G-A$ satisfying
properties a) to h) from Subsection 5.2. What remains is to ensure that
$\delta$ is $W$-central.

Let $y_{1},\dots,y_{n}\in C(\delta)$ be the vortices of the
$\Sigma$-decomposition $\delta.$ Let
$P_{1},\dots,P_{\mathbf{R}_{g_{1},g_{2}}}$ be the horizontal paths and
$Q_{1},\dots,Q_{\mathbf{R}_{g_{1},g_{2}}}$ be the vertical paths of $W.$
Moreover, let

$\displaystyle\mathcal{W}\coloneqq\\{P_{i}\cup Q_{j}\mid
i,j\in[\mathbf{R}_{g_{1},g_{2}}]\text{ where }(V(P_{i})\cup V(Q_{j}))\cap
A=\emptyset\\}.$

Observe that for every $T\in\mathcal{W}$ there exist at least $r^{\prime}-\mu$
vertex disjoint paths in $W-A$ that link $T$ and $W_{0}.$ Thus, the only cells
$y\in C(\delta^{\prime})$ such that an element of $\mathcal{W}$ is a subgraph
of $\Sigma_{\delta^{\prime}}(y)$ are the vortices $y_{i},$ $i\in[n].$

Claim: Let $i\in[n]$ and let $(G_{i},\Omega_{i})$ be the vortex society of
$y_{i}.$ There exists a set $A_{i}\subseteq V(G_{i})$ with $|A_{i}|\leq
2\mu+1$ such that $G_{i}-A_{i}$ does not contain any element of $\mathcal{W}$
as a subgraph.

By Subsection 5.2 there exists a linear decomposition $\langle
X_{1},\dots,X_{m},v_{1},\dots,v_{m}\rangle$ of $(G_{i},\Omega_{i})$ which has
adhesion at most $\mu.$ For every $T\in\mathcal{W}$ with $T\subseteq G_{i}$
let $a_{T}\in[m]$ be the smallest integer such that $V(T)\cap
X_{a_{T}}\neq\emptyset$ and let $b_{T}\in[m]$ be the largest integer with
$V(T)\cap X_{b_{T}}\neq\emptyset$ Notice that the fact that each
$T\in\mathcal{W}$ with $T\subseteq G_{i}$ is connected in $G_{i}$ implies that
$V(T)\cap X_{j}\neq\emptyset$ for all $j\in[a_{T},b_{T}].$ Let $b$ be the
smallest value in the set $\\{b_{T}\mid T\in\mathcal{W}\text{ and }T\subseteq
G_{i}\\}.$ It follows from the fact that $T\cup T^{\prime}$ is connected for
all $T^{\prime},T\in\mathcal{W}$ that $V(T)\cap X_{b}\neq\emptyset$ for every
$T\in\mathcal{W}$ with $T\subseteq G_{i}.$

Let $A_{i}\coloneqq(X_{b}\cap X_{b-1})\cup(X_{b}\cap X_{b+1})\cup\\{v_{b}\\}.$
Since the linear decomposition is of adhesion at most $\mu$ we obtain that
$|A_{i}|\leq 2\mu+1.$

Moreover, $G_{i}-A_{i}$ does not contain any member of $\mathcal{W}$ as a
subgraph as desired. To see this let us assume, towards a contradiction, that
there exists some $T\in\mathcal{W}$ with $T\subseteq G_{i}$ such that
$T\subseteq G_{i}-A_{i}.$ Since $A_{i}$ separates the vertices of
$X_{b}\setminus A_{i}$ from the rest of $G$ and $T$ must intersect $X_{b},$
the only way how $T$ could avoid $A_{i}$ is if $V(T)\subseteq X_{b}\setminus
A_{i}.$ Recall that there exist $r^{\prime}-\mu$ pairwise vertex disjoint
paths in $W-A$ that that link $T$ to $W_{0}$ where $V(W_{0})\cap
V(G_{i})=\emptyset.$ Furthermore, we have

$\displaystyle r^{\prime}-\mu$
$\displaystyle=r+16t+\left\lfloor\frac{1}{10^{5}t^{24}}t^{10^{7}t^{26}}\right\rfloor-\left\lfloor\frac{1}{10^{5}t^{25}}t^{10^{7}t^{26}}\right\rfloor$
$\displaystyle\geq\frac{t}{10^{5}t^{25}}t^{10^{7}t^{26}}-\frac{1}{10^{5}t^{25}}t^{10^{7}t^{26}}-1$
$\displaystyle=\frac{t-1}{10^{5}t^{25}}t^{10^{7}t^{26}}-1$
$\displaystyle>3\mu>|A_{i}|.$

So $A_{i}$ cannot separate $T$ from $W_{0}$, and thus we have reached a
contradiction and the proof of the claim is complete.

Set $\hat{A}\coloneqq A\cup\bigcup_{i\in[n]}A_{i}$ and observe that

$\displaystyle|\hat{A}|$ $\displaystyle\leq 2t^{2}(2\mu+1)+\mu$
$\displaystyle\leq\frac{5t^{2}}{10^{7}t^{25}}t^{10^{7}t^{26}}$
$\displaystyle\leq t^{10^{7}t^{26}}.$

Moreover, from the construction of $\hat{A}$ we obtain that $\hat{A}\setminus
A\subseteq\bigcup_{i\in n}V(\Sigma_{\delta^{\prime}}(y_{i})),$ that is, every
vertex of $\hat{A}$ that does not belong to $A$ belongs to some vortex of
$\delta.$ In particular, this means that $\hat{A}$ is disjoint from $W_{0}.$
Finally, let $\delta^{\prime}$ be the restriction of $\delta$ to the graph
$G-\hat{A}.$ Now, $\delta^{\prime}$ is a $\Sigma$-decomposition of $G-\hat{A}$
which is $W$-central, has breadth at most $2t^{2}$ and depth at most $\mu\leq
t^{10^{7}t^{26}}.$ Moreover, $W_{0}\subseteq W-\hat{A}$ contains an $r$-wall
which is flat in $\delta^{\prime}$ and thus, our proof is complete. ∎

######  Theorem 5.2.

Let $\mathbb{S}$ be a non-empty finite and closed set of surfaces. Let $g_{1}$
be the Euler-genus of the orientable surface in $\mathsf{sobs}(\mathbb{S})$
and $g_{2}$ be the Euler-genus of the non-orientable surface in
$\mathsf{sobs}(\mathbb{S})$ if such a surface exists, otherwise set
$g_{2}\coloneqq 0.$

There exists a function $f\colon\mathbb{N}\to\mathbb{N}$ such that for every
$k\in\mathbb{N},$ every graph $G$ which excludes the orientable Dyck-grid of
order $k$ and Euler-genus $g_{1}$ and, if $g_{2}\neq 0,$ the non-orientable
Dyck-grid of order $k$ and Euler-genus $g_{2}$ satisfies
${\mathbb{S}}\mbox{-}\mathsf{hw}(G)\leq f(k).$

In particular, $G$ has a tree-decomposition $(T,\beta)$ of adhesion less than
$f(k)$ such that for every $d\in V(T),$ either $|\beta(d)|\leq f(k),$ or there
exist a set $A_{d}\subseteq\beta(d)$ of size at most $f(k)$ and a surface
$\Sigma\in\mathbb{S}$ such that $\mathsf{Torso}_{G}(d)-A_{d}$ has a
$\Sigma$-decomposition $\delta$ of width at most $f(k)$ and breadth at most
$f(k).$

${\blacktriangleright}$ Moreover, let $X_{d}$ be the set containing all
vertices of $\mathsf{Torso}_{G}(d)-A_{d}$ which are drawn in some vortex of
$\delta$ together with the vertices of $A_{d}.$ Then

  * i.

for every neighbor $d^{\prime}$ of $d$ in $T$ we have that
$|(\beta(d)\cap\beta(d^{\prime}))\setminus X_{d}|\leq 3$ and

  * ii.

$\mathsf{Torso}_{G}(d)-X_{d}$ is a minor of $G.$

###### Proof.

Let us first assume that $\mathbb{S}=\\{\Sigma^{\varnothing}\\}.$ In this case
$\mathsf{sobs}(\mathbb{S})$ contains only surfaces homeomorphic to the sphere.
Thus, the orientable Dyck-grid and the non-orientable one are both of Euler-
genus zero. Therefore, this case follows immediately from Subsection 3.1.

From now on we may assume $\mathbb{S}$ to contain a non-void surface.

Suppose $g_{2}=0.$ This means that $\mathsf{sobs}(\mathbb{S})$ contains only
orientable surfaces of Euler-genus $g_{1}.$ Notice that this implies that
$\mathbb{S}$ contains a non-orientable surface of Euler-genus $g_{1}$ and
$g_{1}+1$.

Let $g_{1}=2h_{1}.$ Now let $k\in\mathbb{N}$ be some integer and $G$ be some
graph that excludes $\mathscr{D}^{(h_{1},0)}_{k}$ as a minor. In case
$k\in[0,1]$ this graph is planar, and thus our claim follows from Subsection
3.1. Thus, we may assume $k\geq 2.$ Finally, let $t\coloneqq
12(162^{2g_{1}}+4)k.$ Let

$\displaystyle\mathbf{a}_{g_{1},0}$ $\displaystyle\coloneqq t^{10^{7}t^{26}}$
$\displaystyle\mathbf{g}_{\mathsf{o},g_{1},0}$ $\displaystyle\coloneqq
g_{1}-1$ $\displaystyle\mathbf{g}_{\mathsf{n},g_{1},0}$
$\displaystyle\coloneqq{g_{1}}$
$\displaystyle\mathbf{v}_{\mathsf{b},{g_{1},0}}$ $\displaystyle\coloneqq
2t^{2}$ $\displaystyle\mathbf{v}_{\mathsf{d},{g_{1},0}}$
$\displaystyle\coloneqq t^{10^{7}t^{26}}$ $\displaystyle\mathbf{R}_{g_{1},0}$
$\displaystyle\coloneqq
49152t^{24}(r+16t)+\left\lceil\frac{5}{2}t^{10^{7}t^{26}}\right\rceil.$

Moreover, let
$\mathfrak{D}\coloneqq\\{\mathscr{D}^{(h_{1},0)}=\langle\mathscr{D}^{(h_{1},0)}_{i}\rangle_{i\in\mathbb{N}},\\}.$
Then
$\mathfrak{S}(\mathfrak{D}_{g_{1},0},\mathbf{a}_{g_{1},0},\mathbf{g}_{\mathsf{o},g_{1},0},\mathbf{g}_{\mathsf{n},g_{1},0},\mathbf{v}_{\mathsf{b},{g_{1},0}},\mathbf{v}_{\mathsf{d},{g_{1},0}},\mathbf{R}_{g_{1},0})$
is valid by Theorem 5.1.

Our claim now follows immediately from Theorem 4.2.

Hence, we may now assume $\mathsf{sobs}(\mathbb{S})$ to contain a non-void
surface which is non-orientable and one that is orientable. Thus, there exist
integers $g_{1}$ and $g_{2}$ where $g_{2}\neq 0$ such that every orientable
surface in $\mathsf{sobs}(\mathbb{S})$ has Euler-genus $g_{1}$ and every non-
orientable surface in $\mathsf{sobs}(\mathbb{S})$ has Euler-genus $g_{2}.$ In
particular, we may assume for every orientable
$\Sigma\in\mathsf{sobs}(\mathbb{S})$ and every non-orientable
$\Sigma^{\prime}\in\mathsf{sobs}(\mathbb{S})$ that
$\Sigma\not\preceq\Sigma^{\prime}$ and $\Sigma^{\prime}\not\preceq\Sigma.$

Let $g_{1}=2h_{1}$ and $g_{2}=2h_{2}+c_{2}$ where $c_{2}\in[2].$ From the
discussion above it follows that $h_{2}<h_{1}.$ Now let $k\in\mathbb{N}$ be
some integer and $G$ be some graph that excludes both
$\mathscr{D}^{(h_{1},0)}_{k}$ and $\mathscr{D}^{(h_{2},c_{2})}_{k}$ as minors.
In case $k\in[0,1]$ both of these graphs are planar, and thus our claim
follows from Subsection 3.1. Thus, we may assume $k\geq 2.$ Finally, let
$g\coloneqq\max\\{g_{1},g_{2}\\}$ and $t\coloneqq 12(162^{2g}+4)k.$ Let
$\mathbf{a}_{g_{1},g_{2}}\coloneqq\mathbf{a}_{g_{1},0}$,
$\mathbf{g}_{\mathsf{o},g_{1},g_{2}}\coloneqq\mathbf{g}_{\mathsf{o},g_{1},0}$,
$\mathbf{v}_{\mathsf{b},{g_{1},g_{2}}}\coloneqq\mathbf{v}_{\mathsf{b},{g_{1},0}}$,
$\mathbf{v}_{\mathsf{d},{g_{1},g_{2}}}\coloneqq\mathbf{v}_{\mathsf{d},{g_{1},0}}$,
$\mathbf{R}_{g_{1},g_{2}}\coloneqq\mathbf{R}_{g_{1},0}$, and

$\displaystyle\mathbf{g}_{\mathsf{n},g_{1},g_{2}}\coloneqq{g_{2}-1}$

Moreover, let
$\mathfrak{D}\coloneqq\\{\mathscr{D}^{(h_{1},0)}=\langle\mathscr{D}^{(h_{1},0)}_{i}\rangle_{i\in\mathbb{N}},\mathscr{D}^{(h_{2},c_{2})}=\langle\mathscr{D}^{(h_{2},c_{2})}_{i}\rangle_{i\in\mathbb{N}}\\}.$
Then, by Theorem 5.1, the local structure theorem
$\mathfrak{S}_{(g_{1},g_{2})}(\mathfrak{D}_{g_{1},g_{2}},\mathbf{a}_{g_{1},g_{2}},\mathbf{g}_{\mathsf{o},g_{1},g_{2}},\mathbf{g}_{\mathsf{n},g_{1},g_{2}},\mathbf{v}_{\mathsf{b},{g_{1},g_{2}}},\mathbf{v}_{\mathsf{d},{g_{1},g_{2}}},\mathbf{R}_{g_{1},g_{2}})$
is valid.

Our claim now follows immediately from Theorem 4.2. ∎

##  6 Bounding annotated treewidth

Recall that Theorem 5.2 provides a tree-decomposition $(T,\beta)$ where for
each $t\in V(T)$ there exists a set $A\subseteq\beta(t)$ such that the torso
$G_{t}$ of $G$ at $t$ has a $\Sigma$-decomposition $d$ of width at most $f(k)$
and breadth at most $f(k)$ after deleting $A$. In the statement of the same
lemma we also considered the set $X_{t}$ containing all vertices of
$G_{t}-A_{t}$ which are drawn in some vortex of $\delta$ together with the
vertices of $A_{t}.$ The purpose of this section is to prove that $X_{t}$ is a
low-treewidth modulator of the torso $G_{d}$ whose annotated treewidth is
bounded by a function the width and the breath of $\delta$ as well as the
Euler-genus of $\Sigma.$ This will permit us to substitute the use of the apex
vertices $A_{d}$ and the vortices of $\delta$ by a single low-treewidth
modulator.

In this section we present several results on the biggest grid parameter ${\sf
bg}$ and its annotated version. Some of these results will also be useful for
the proofs of the lower bounds in Section 7. We start with the formal
definitions of annotated extension and ${\sf bg}.$

#### Annotated extensions of parameters.

We use $\mathcal{A}_{\text{all}}$ in order to denote the set of all annotated
graphs. Given a minor-monotone graph parameter ${\sf p}:\mathcal{G}_{\rm
all}\to\mathbb{N},$ we define its annotated extension ${\sf
p}:\mathcal{A}_{\rm all}\to\mathbb{N}$ so that

${\sf p}(G,X)\coloneqq\max\\{{\sf p}(H)\mid\mbox{$H$ is an $X$-minor of
$G$}\\}.$

Notice that $0={\sf p}(G,\emptyset)\leq{\sf p}(G,X)\leq{\sf p}(G,V(G))={\sf
p}(G).$

In this paper we apply the above definition for ${\sf tw}$ and ${\sf bg}$ as
defined below.

#### The ${\sf bg}$ parameter.

The _biggest grid_ parameter ${\sf bg}$ outputs the maximum $k$ for which $G$
contains a $(k\times k)$-grid as a minor. Recall that
$\\{\Sigma^{0,0}\\}\mbox{-}\mathsf{bg}$ is the maximum $k$ for which $G$
contains the annulus grid $\mathscr{A}_{k}$ as a minor, therefore ${\sf
bg}\sim_{\mathsf{L}}\\{\Sigma^{0,0}\\}\mbox{-}\mathsf{bg}.$

Notice that the treewidth and the biggest grid parameters are asymptotically
equivalent, in fact it holds that ${\sf tw}\sim_{{\mathsf{P}}}{\sf bg}$ (by
Subsection 3.1 and the asymptotic equivalence between grids and walls). In
this section we study the annotated extension of ${\sf bg}$: for every
annotated graph $(G,X),$ ${\sf bg}(G,X)$ is the biggest $k$ such that $G$
contains a $(k\times k)$-grid as an $X$-minor.

Notice that ${\sf bg}(G,X)\geq k$ if and only if there is a collection
$\mathcal{S}=\\{S_{1},\ldots,S_{k^{2}}\\}$ of connected and pairwise-disjoint
vertex sets of $G,$ each containing at least one vertex in $X$ and such that
the contraction, in $G[\boldsymbol{\boldsymbol{\bigcup}}\mathcal{S}],$ of all
edges with both endpoints in the same $S_{i}$ results in a graph containing a
$(k\times k)$-grid as a spanning subgraph.

###  6.1 Walls in surfaces and their radii

An _annotated $r$-wall_ is a pair $(W,S)$ where

  * •

$W$ is an $r$-wall,

  * •

every path of $W$ between two vertices of degree three in $W$ contains exactly
one vertex from $S.$

  * •

all vertices of $S$ have degree two in $W.$

A _hairy annotated $r$-wall_ is a pair $(\hat{W},X)$ such that
$\hat{W}=W\cup\boldsymbol{\boldsymbol{\bigcup}}\mathcal{P}$ and $X\subseteq
V(\hat{W})$ where

  * •

$W$ is an $r$-wall that contains a vertex set $S\subseteq V(W)$ where
$|S|=|X|$ and such that $(W,S)$ is an annotated $r$-wall,

  * •

$\mathcal{P}$ is a collection of $|X|$ vertex-disjoint paths each with one
endpoint in $S$ and with the other in $X$ and such that
$V(W)\cap\bigcup\mathcal{P}=S.$

The _branch vertices_ of $\hat{W}$ are the branch vertices of the $r$-wall
$W.$

The following observation follows easily by the fact that every $r$-wall is a
subdivision of a subgraph of a $(2k\times 2k)$-grid.

######  Observation .

There is a universal constant $c$ such that for every graph $G$ and every set
$X\subseteq V(G),$ if ${\sf bg}(G,X)\geq c{k},$ then $G$ contains a hairy
annotated $k$-wall $(W,X)$ as a subgraph.

Figure 13: A hairy annotated $5$-wall $(\hat{W},X).$ The edges and the
internal nodes of the paths in $\mathcal{P}$ are orangle. The set $S$ is
depicted by the magenta vertices and the set $X$ is depicted by the blue
circles. The branch vertices are the square vertices.

We say that a vertex of a graph is a _branch vertex_ if it has degree at least
3. Given two vertices $x,y,$ we define their _branch distance_ , denoted by
$\mathsf{bdist}_{G}(x,y)$ as the minimum number of branch vertices of a path
between $x$ and $y.$ The _branch radius_ of $G$ is at most $r$ if there is an
$x\in V(G)$ such that for every $y\in V(G),$ $\mathsf{bdist}_{G}(x,y)\leq r.$

######  Observation .

Let $(\hat{W},X)$ be a hairy annotated $r$-wall and let $Q$ be the graph
obtained by adding a new vertex $v_{\text{new}}$ and making it adjacent to all
vertices of $X.$ Then $Q$ has branch radius at most two.

Let $\Sigma$ be a surface without boundary and let $G$ be a graph drawn in
$\Sigma$ without crossings. Towards simplifying notation, we do not
distinguish the graph and its particular embedding, and we use $F(G)$ to
denote the set of faces of $G,$ i.e., the set of connected components of the
set $\Sigma\setminus G.$ Given $x,y\in V(G)\cup F(G),$ a _radial $(x,y)$-path_
in $G$ of length at most $r$ is a sequence of vertices and faces of length
$r+1,$ where faces and vertices alternate, which starts from $x$ and finishes
in $y,$ and such that if $f\in F(G)$ and $v\in V(G)$ are consecutive in the
sequence, then $v$ is a point of the boundary of $f.$ The _radial distance_
between $x$ and $y,$ denoted by $\mathsf{rdist}_{G,\Sigma}(x,y)$ is the
minimum length of a radial $(x,y)$-path in the embedding of $G$ in $\Sigma.$
The _radial radius_ of $G$ is at most $r$ if there is an $x\in V(G)\cup F(G)$
such that for every $y\in V(G)\cup F(G),$ $\mathsf{rdist}_{G,\Sigma}(x,y)\leq
r.$

The following has been proven in different forms, see eg, [10, 18, 24].

######  Proposition  ([10, 18, 24]).

Let $G$ be a graph drawn in a surface $\Sigma$ of Euler-genus $g.$ There is a
universal constant $c$ such that if the treewidth of G is more than $cr(g+1),$
then $G$ contains an $r$-wall $W$ as a subgraph which is a subset of a
contractible closed disk of $\Sigma$ whose boundary is the perimeter of $W.$

######  Lemma .

Let $G$ be a graph drawn in a surface $\Sigma$ of Euler-genus at most $k$ with
radial radius at most $r.$ Then ${\sf tw}(G)\in\mathcal{O}(g\cdot r)$

###### Proof.

Let $q$ be the maximum integer such that $G$ contains a $2(q+1)$-wall $W$ as a
subgraph that is a subset of a closed disk of $\Sigma$ whose boundary is the
perimeter of $W.$ Notice that the radial radius of $W$ is more than $q,$ which
in turn implies that also the radial radius of $G$ is at least $q.$ As $G$ has
radial radius at most $r,$ we have that $q\leq r.$ This, combined with
Subsection 6.1 implies that ${\sf tw}(G)\in\mathcal{O}(g\cdot r).$ ∎

###  6.2 Bounding the biggest grid

Let us denote the $(k\times k)$-grid by $\Gamma_{k}.$ The _perimeter_ of
$\Gamma_{k},k\geq 3,$ is defined in the same way as it is defined for walls.
We say that the _$1$ st layer_ of $\Gamma_{k}$ is its perimeter. Given some
$s\leq\lfloor k/2\rfloor$ we define the _$s$ -th layer_ of $\Gamma_{k}$ as the
perimeter of the $(k-2s+2\times k-2s+2)$-grid remaining if we remove the first
$s-1$ layers of $\Gamma_{k}.$ We refer to the first $s$ layers of $\Gamma_{k}$
as its $s$ _outermost layers_.

Given an $(m\times m)$-grid $\Gamma_{m},m\geq 3,$ and some $k$ where $3\leq
k\leq m$ and such that $m-k$ is even, we define the _central $(k,k)$-subgrid_
of $\Gamma_{m}$ as the unique subgraph of $\Gamma_{m}$ obtained by removing
its ${\frac{m-k}{2}}$ outermost layers.

Let $G$ and $H$ be graphs, $X\subseteq V(G)$, and assume that $H$ is an
$X$-minor of $G,$ certified by the collection $\mathcal{S}=\\{S_{v}\mid v\in
V(H)\\}$ of pairwise-disjoint connected subsets of $V(G).$ If $x\in S_{v},$
then we say that $x$ is a _precursor_ of $v$ in $G$ and that $v$ is the _heir_
of $x$ in $H.$

######  Observation .

Let $(H,Y)$ and $(G,X)$ be annotated graphs where $H$ is an $X$-minor of $G$.
Then ${\sf bg}(G,X)\geq{\sf bg}(H,Y).$

An important tool for the study of ${\sf bg}$ is the following.

######  Proposition  ([7]).

Let $\Gamma_{m}$ be the $(m\times m)$-grid and let $S$ be a subset of the
vertices in the central $(m-2\ell)\times(m-2\ell)$-subgrid of $\Gamma_{m},$
where $\ell=\lfloor\sqrt[4]{|S|}\rfloor.$ $G$ contains the
$(\ell\times\ell)$-grid as an $S$-minor.

######  Lemma .

Let $G$ be a graph and let $X_{1},\ldots,X_{r}\subseteq V(G)$ such that, for
$i\in[r],$ ${\sf bg}(G,X_{i})\leq\ell.$ Then ${\sf bg}(G,X_{1}\cup\cdots\cup
X_{r})\in\mathcal{O}(r^{4}\ell^{2}).$

###### Proof.

Let $X=X_{1}\cup\cdots\cup X_{r}$ and let $q={\sf bg}(G,X).$ Let also
$\Gamma_{q}$ be a $(q\times q)$-grid $X$-minor in $G,$ certified by a
collection $\mathcal{S}=\\{S_{v}\mid v\in V(\Gamma_{q})\\}$ of pairwise-
disjoint connected subsets of $V(G).$ We choose $i$ so that the cardinality of
the set $Z_{i}\coloneqq\\{u\in V(\Gamma_{q})\mid X_{i}\cap
S_{u}\neq\emptyset\\}$ is maximized, i.e., $X_{i}$ has the majority of
intersections with the sets of $\mathcal{S}.$ As we fix $i,$ for simplicity we
use $Z=Z_{i}.$

Clearly $Z$ is a subset of $V(\Gamma_{q})$ where $|Z|\geq q^{2}/r.$ For each
(positive) margin $b,$ we define the set $B_{b}$ as the union of the $b$
outermost layers of $\Gamma_{q}.$ We now fix some $b\in[\lfloor q/2\rfloor],$
and observe that at most $4b(q-b)$ of the vertices of $\Gamma_{q}$ are in the
outermost $b$ layers. This means that at least
$f(q,b,r)\coloneqq\frac{q^{2}}{r}-4b(q-b)$ vertices of $Ζ$ are in the central
$(q-2b)\times(q-2b)$-subgrid of $\Gamma_{m}.$

We choose the margin $b_{q,r}$ as the maximum integer $b$ such that
$\lfloor\sqrt[4]{f(q,b,r)}\rfloor\geq 2b.$

This implies that there are at least $f(q,b_{q,r},r)$ vertices from $Z$ in the
$(q-2b_{q,r})\times(q-2b_{q,r})$-subgrid of $\Gamma_{q}.$ By Subsection 6.2 we
obtain, ${\sf bg}(G,X_{i})\geq{\sf
bg}(\Gamma_{q},Z_{i})\geq\lfloor\sqrt[4]{f(q,b_{q,r},r)}\rfloor\geq
2b_{q,r}\in\Omega(\frac{q^{1/2}}{{r}^{1/4}}).$ Therefore, ${\sf
bg}(G,X_{1}\cup\cdots\cup X_{r})\in\mathcal{O}(r^{4}\ell^{2}).$ ∎

The next observation follows directly from the definition of ${\sf bg}.$

######  Observation .

Let $G$ be a graph, $A\subseteq V(G),$ and $X\subseteq V(G)\setminus A,$ where
${\sf bg}(G-A,X)\leq k.$ Then ${\sf bg}(G,X\cup A)\leq k+|A|.$

######  Lemma .

For every graph $G,$ every $k\in\mathbb{N},$ and every surface $\Sigma$ with
Euler-genus at most $g,$ if $A\subseteq V(G),$ $\delta$ is a
$\Sigma$-decomposition of $G-A$ of width at most $w$ and breadth at most $b$,
and ${\displaystyle X\coloneqq A\cup\bigcup\\{\Sigma(c)\mid\mbox{\small$c$ is
a vortex of $\delta$}\\}},$ then ${\sf
bg}(G,X)\in\mathcal{O}(b^{4}\cdot(b\cdot g\cdot w)^{2}+|A|).$

###### Proof.

Let $c_{1},\ldots,c_{b}$ be the vortices of $\delta.$ Also, let
${(\Sigma(c_{i}),\Omega_{i})}$ be the vortex society of $c_{i},$ $i\in[b].$
Because of Subsection 6.2, we may assume that $A=\emptyset$ and prove that
${\sf bg}(G,X)\in\mathcal{O}(b^{4}\cdot(b\cdot g\cdot w)^{2}).$ Because of
Subsection 6.2, it is enough to prove that for every
$\hat{c}\in\\{c_{1},\ldots,c_{b}\\},$ if $S=V(\Sigma(\hat{c})),$ then ${\sf
bg}(G,S)\in\mathcal{O}(bgw).$

Let $z=\lfloor{\sf bg}(G,S)/{c^{\prime}}\rfloor$ where $c^{\prime}$ is the
constant of Subsection 6.1.

According to Subsection 6.1 $G$ contains a hairy annotated $z$-wall
$(\hat{W},S).$ Moreover, ${\sf tw}(\hat{W})\geq z.$

As a first step, we enhance $G$ by adding, for each vortex
$c_{i}\in\\{c_{1},\ldots,c_{b}\\},$ a cycle $C_{i}$ joining every pair of
consecutive vertices in $\Omega_{i}.$ We further enhance $G$ by adding a new
vertex $a,$ called _apex_ vertex, and make it adjacent to all the vertices of
$S.$ We also update $\delta$ by setting
$\Sigma(c_{i})\coloneqq\Sigma(c_{i})\cup C_{i},$ for every $i\in[b],$ and we
further enhance $\Sigma(\hat{c})$ by adding $a$ and making it adjacent to all
vertices of $S.$

Notice that the above enhancements cannot increase the width of the vortices
of $\delta$ by more than three. We now define the pair $(W^{+},S)$ where
$W^{+}$ is obtained if we first consider the graph
${W}\cup\boldsymbol{\boldsymbol{\bigcup}}\\{C_{i}\mid i\in[b]\\}$ and then add
the vertex $a$ and all the edges between $a$ and $S.$ Clearly, $W^{+}$ may
have vertices outside $\hat{c},$ however all vertices in $\\{a\\}\cup S$ are
vertices of $\Sigma(\hat{c}).$ We now consider the graphs

  * •

$H_{1}=W^{+}\setminus\bigcup\\{\Sigma(c_{i})\setminus V(C_{i})\mid
i\in[b]\\},$ and

  * •

$H_{2}=H_{1}\cup\bigcup\\{\Sigma(c_{i})\mid i\in[b]\\}.$

Observe that $H_{1}$ is a subgraph of $W^{+}$ and $W^{+}$ is a subgraph of
$H_{2}.$ By construction, $H_{1}$ is a graph that is embedded in $\Sigma$
without crossings. Also keep in mind that ${\sf tw}(W^{+})\geq{\sf tw}(W)\geq
z.$

Recall that every branch vertex of $W$ is at branch distance at most three
from $a$. This fact combined with the construction of $H_{1}$ implies that
every face or vertex of $H_{1}$ is at radial distance $\mathcal{O}(b)$ from
the face of $H_{1}$ whose boundary of $C_{\hat{c}}.$ We obtain that the radius
of $H_{1}$ is $\mathcal{O}(b)$ and this, combined with Subsection 6.1 implies
that ${\sf tw}(H_{1})\in\mathcal{O}(bg).$

Our next step is to use the fact that ${\sf tw}(H_{1})\in\mathcal{O}(bg)$ in
order to prove that ${\sf tw}(H_{2})\in\mathcal{O}(bgw).$ For this, let
$(T,\beta)$ be a tree-decomposition of $H_{1}$ and let $L^{i}=\langle
X_{1}^{i},X_{2}^{i},\dots,X_{n_{i}}^{i},x_{1}^{i},x_{2}^{i},\dots,x_{n_{i}}^{i}\rangle$
be a linear decomposition of $\Sigma(c_{i}),$ assuming that
$x_{1}^{i},x_{2}^{i},\dots,x_{n_{i}}^{i}$ are the vertices of $\Omega_{i}$
ordered according to $\Omega_{i}.$ We now build a tree-decomposition
$(T,\beta^{\prime})$ of $H_{2}$ where for each $t\in V(T),$ we define
$\beta^{\prime}(t)$ to be the union of the set $\beta(t)$ and every set
$X_{j}^{i},$ for which $x_{j}^{i}$ is a vertex of
$\beta(t)\cap\boldsymbol{\boldsymbol{\bigcup}}\\{\\{x_{1}^{i},x_{2}^{i},\dots,x_{n_{i}}^{i}\\}\mid
i\in[b]\\}.$ As each $X_{j}^{i}$ has $\mathcal{O}(w)$ vertices, it follows
that $(T,\beta^{\prime})$ has width $\mathcal{O}(bgw),$ as required. We
conclude that ${\sf tw}(H_{2})\in\mathcal{O}(bgw).$

Finally, recall that $W^{+}$ is a subgraph of $H_{2},$ therefore $z\leq{\sf
tw}(W^{+})\leq{\sf tw}(H_{2})\in\mathcal{O}(bgw).$ In other words, ${\sf
bg}(G,S)=c^{\prime}z^{2}\in\mathcal{O}(bgw)$ as required. ∎

Let $α$ be an integer such that for every graph $G,$ ${\sf
tw}(G)\in\mathcal{O}({\sf bg}(G))^{\alpha}.$ Such a constant $α$ exists by
Subsection 3.1. Then Subsection 6.2 implies the following.

######  Lemma .

For every graph $G,$ every $k\in\mathbb{N},$ and every surface $\Sigma$ with
Euler-genus at most $g,$ if $A\subseteq V(G),$ $\delta$ is a
$\Sigma$-decomposition of $G-A$ with width $\leq w$ and breadth $\leq b$ and
${\displaystyle X=A\cup\bigcup\\{\Sigma(c)\mid\mbox{\small$c$ is a vortex of
$\delta$}\\}},$ then ${\sf tw}(G,X)\in\mathcal{O}((b^{4}\cdot(b\cdot g\cdot
w)^{2}+|A|)^{α}),$ where $α$ is the constant of Subsection 3.1.

##  7 The lower bound

Using the concept of clique-sum closures, we can easily generate new graph
parameters. For this, given a graph parameter ${\sf
p}\colon\mathcal{G}_{\text{all}}\to\mathbb{N}$ we define the graph parameter
${\sf p}^{*}$ where for every graph $G,$ ${\sf p}^{*}(G)$ is the minimum $k$
such that $G$ is in the clique-sum closure of the class of graphs where the
value of ${\sf p}$ is at most $k.$ Notice that ${\sf p}^{*}=({\sf
p}^{*})^{*}.$ It is easy to see that if size is the parameter returning the
number of vertices of a graph minus one, then ${\sf tw}=\textsf{size}^{*}.$

######  Observation .

If ${\sf p}$ is a minor-monotone graph parameter, then ${\sf p}^{*}$ is also
minor-monotone.

Given a graph parameter ${\sf p}\colon\mathcal{G}_{\text{all}}\to\mathbb{N}$
and a minor-closed graph class $\mathcal{G}$ we define the _modulator
composition_ of ${\sf p}$ and $\mathcal{G}$, as the parameter ${\sf
p}_{\mathcal{G}}:\mathcal{G}_{\text{all}}\to\mathbb{N}$, so that

$\displaystyle{\sf p}_{\mathcal{G}}(G)$ $\displaystyle\coloneqq$
$\displaystyle\min\\{k\mid\mbox{$\mbox{there exists an $X\subseteq V(G)$ such
that\leavevmode\nobreak\ }{\sf p}(G,X)\leq k\mbox{\leavevmode\nobreak\
and\leavevmode\nobreak\ }G-X\in\mathcal{G}$}\\}.$ (12)

Notice that, given that ${\sf p}$ is minor-monotone and $\mathcal{G}$ is minor
closed, we have that ${\sf p}_{\mathcal{G}}$ is minor-monotone as well. Using
(12), we define the “annotated modulation to a surface”-version of ${\sf p}$
as the graph parameter ${\sf p}_{\Sigma}$ where ${\sf p}_{\Sigma}\coloneqq{\sf
p}_{\mathcal{E}_{\Sigma}}$. Notice that, because of Subsection 3.1, ${\sf
tw}\sim_{\mathsf{P}}{\sf bg}.$ By the above definitions, one can easily deduce
that ${\sf tw}_{\Sigma}\sim_{\mathsf{P}}{\sf bg}_{\Sigma}$ and moreover that

$\displaystyle{\sf tw}_{\Sigma}^{*}$ $\displaystyle\sim_{\mathsf{P}}$
$\displaystyle{\sf bg}_{\Sigma}^{*}$ (13)

In (13), we agree that ${\sf tw}_{\Sigma}^{*}$ is a shortcut of $({\sf
tw}_{\Sigma})^{*}$ and that ${\sf bg}_{\Sigma}^{*}$ is a shortcut of $({\sf
bg}_{\Sigma})^{*}$. The equivalence in (13) will permit us to use ${\sf
bg}_{\Sigma}$ instead of ${\sf tw}_{\Sigma},$ to prove our lower bounds.

In this section we consider for fixed values of $h$ and $c,$ the Dyck-grid
$\mathscr{D}_{k}^{(h,c)}$ and a surface $\Sigma$ where
$\mathscr{D}_{k}^{(h,c)}$ cannot be embedded (that is a surface $\Sigma$ not
containing $\Sigma^{(h,c)}$). Our target is to prove that
$\mathscr{D}_{k}^{(h,c)}$ cannot be the clique-sum closure of graphs with low-
treewidth modulators to $\Sigma.$ In other words, we prove a (polynomial)
lower bound to ${\sf tw}_{\Sigma}^{*}(\mathscr{D}_{k}^{(h,c)})$ or,
alternatively, because of (13), a lower bound to ${\sf
bg}_{\Sigma}^{*}(\mathscr{D}_{k}^{(h,c)})$ (in terms of $k$).

Our proof has two steps. In Subsection 7.1 we prove that ${\sf
bg}_{\Sigma}(\mathscr{D}_{k}^{(h,c)})\in\Omega(k^{1/5}).$ Based on this
result, in Subsection 7.2 we prove that ${\sf
bg}_{\Sigma}^{*}(\mathscr{D}_{k}^{(h,c)})\in\Omega(k^{1/480}).$ In our proofs
we do not make any particular effort to optimize the parametric dependences.
While we keep them being polynomial, it seems that much better polynomial
bounds might be achieved with a more fine-grained analysis.

###  7.1 Modulators of Dyck-grids

In our proof we work with a simpler version of $\mathscr{D}^{(h,c)},$ where
the annulus grid is suppressed. The new parametric graph is denoted by
$\tilde{\mathscr{D}}^{(h,c)}=\langle\tilde{\mathscr{D}}_{k}^{(h,c)}\rangle_{k\in\mathbb{N}},$
where the graph $\tilde{\mathscr{D}}_{k}^{(h,c)}$ is obtained from
$\mathscr{D}_{k}^{(h,c)}$ by removing the set $S$ of $4k^{2}$ vertices
corresponding to the annulus grid $\mathscr{A}_{k}$ and, in the resulting
graph, among the $2k$ neighbors of the vertices that have been removed, we
join by edges the $k$ pairs that belong to the same cycle of
$\mathscr{D}_{k}^{(h,c)}$ (see Figure 2 for an example). Clearly
$\tilde{\mathscr{D}}_{k}^{(h,c)}\leq\mathscr{D}_{k}^{(h,c)}$ and it is easy to
see that ${\mathscr{D}}_{k}^{(h,c)}\leq\tilde{\mathscr{D}}_{2k}^{(h,c)}.$ This
implies the following observation.

######  Observation .

For every $(h,c)\in\mathbb{N}\times[0,2]\setminus\\{(0,0)\\},$
$\mathscr{D}^{(h,c)}\sim_{{\mathsf{L}}}\tilde{\mathscr{D}}^{(h,c)}.$

Notice that $\tilde{\mathscr{D}}^{(h,c)}$ contains $h$ spanning $(2k\times
2k)$-grids and $2h$ spanning $(2k\times k)$-grids

Figure 14: The graph $\tilde{\mathscr{D}}_{8}^{1,2}$ and a half-integral
packing of four subdivisions of $\tilde{\mathscr{D}}_{2}^{1,2},$ colored by
different colors.

Let $G$ and $H$ be two graphs. A _half-integral packing of $H$ in $G$_ is a
set $\mathcal{P}=\\{H_{1},\ldots,H_{r}\\}$ of subgraphs of $G$ such that

  * •

for every $i\in[r],$ $H\leq H_{i}$ and

  * •

no vertex of $G$ belongs to more than two graphs in $\mathcal{P}.$

We will use the following observation (we omit the tedious proof that becomes
apparent when considering the half-integral packing of $4$ copies of
$\mathscr{D}_{2}^{(h,c)}$ in $\mathscr{D}_{8}^{(h,c)}$ depicted in Figure 14).

######  Observation .

Let $(h,c)\in\mathbb{N}\times[0,2]$ and let $x,y\in\mathbb{N}_{\geq 1}.$ Then
$\tilde{\mathscr{D}}_{xy}^{(h,c)}$ contains a half-integral packing of $x$
copies of $\tilde{\mathscr{D}}_{y}^{(h,c)}.$

Let $h\in\mathbb{N}$ and $c\in[0,2]$ be integers where $(h,c)$ is different
from $(0,0).$ We define $\mathbb{S}_{h,c}$ as the set containing every surface
where it is not possible to embed all graphs in $\mathscr{D}^{(h,c)}.$ Notice
that $\mathbb{S}_{h,c}$ contains every surface that does not contain
$\Sigma^{(h,c)}.$ Due to Subsection 1.2, if $(h,c)\neq(0,0),$ then
$\mathbb{S}_{h,c}$ is non-empty.

######  Lemma .

Let $(h,c)\in\mathbb{N}\times[0,2]\setminus\\{(0,0)\\}$ and let
$\Sigma\in\mathbb{S}_{h,c}.$ Then ${\sf
bg}_{\Sigma}(\mathscr{D}_{k}^{(h,c)})\in\Omega_{h,c}(k^{1/5}).$

###### Proof.

Notice that by Subsection 7.1 and the minor-monotonicity of ${\sf
bg}_{\Sigma}$, it is enough to prove that
$\mathsf{bg}_{\Sigma}(\tilde{\mathscr{D}}_{k}^{(h,c)})\in\Omega_{h,c}(k^{1/5}).$
Again by Subsection 7.1 we know that there is no surface in $\mathbb{S}_{h,c}$
where all graphs in $\tilde{\mathscr{D}}^{(h,c)}$ can be embedded. Let $k_{0}$
be minimum such that $\tilde{\mathscr{D}}^{(h,c)}_{k_{0}}$ is not embeddable
in any of the (finitely many) surfaces in $\mathbb{S}_{h,c}.$ Clearly, $k_{0}$
depends exclusively on the choice of $h,c.$ Let $X$ be an modulator of
$\mathscr{D}_{k}^{(h,c)}$ to the embeddability in $\Sigma.$

Our target is to prove that ${\sf
bg}(\tilde{\mathscr{D}}^{(h,c)}_{k},X)\in\Omega_{h,c}(k^{1/5}).$

For each $b\in[0,k],$ we define $\mathcal{C}_{b}$ as the set of the $b$
outermost cycles of $\tilde{\mathscr{D}}_{k}^{(h,c)}$, and we define
$B_{b}=V(\boldsymbol{\boldsymbol{\bigcup}}\mathcal{C}_{b})$ and
$X_{b}=X\setminus B_{b}.$ The value of $b$ will be determined later.

Figure 15: A visualization of the first subcase of Case 1 in the proof of
Subsection 7.1, where $k^{\prime}=10,$ $b=2,$ $m=12,$ and $r=5.$ The $b$
outermost cycles are colored green. We depict the partition of $G^{*}$ to four
pairwise disjoint $(2k^{\prime}\times k^{\prime})$-grids, and the $(m\times
m)$-grid $\Gamma_{m}$ as a minor in it. The perimeter of the central
$(m-2b)\times(m-2b)$-subgrid is depicted red.

By Subsection 7.1, there is a set $\mathcal{P}_{b}$ of
$\lfloor\frac{k-b}{k_{0}}\rfloor$ subgraphs of
$\tilde{\mathscr{D}}^{(h,c)}_{k}$ that is a half-integral packing of
$\tilde{\mathscr{D}}^{(h,c)}_{k_{0}}$ in $\tilde{\mathscr{D}}^{(h,c)}_{k}$ and
such that the graphs in $\mathcal{P}_{b}$ do not contain vertices in $B_{b}.$
Notice that $X_{b}$ should contain at least one vertex from every graph in
$\mathcal{P}_{b}$ and no vertex of $X_{b}$ can belong to more than two graphs
in $\mathcal{P}_{b}.$ This implies that
$|X_{b}|\geq\lfloor\frac{k-b}{2k_{0}}\rfloor.$ Observe now that the vertex set
of $\tilde{\mathscr{D}}^{(h,c)}_{k}$ can be partitioned into $h+c$ vertex sets
$V_{1},\ldots,V_{h+c}$ such that, for each $i\in[h+c],$
$\tilde{\mathscr{D}}^{(h,c)}_{k}$ contains an annotated graph $(G_{i},V_{i})$
as a $V_{i}$-minor where ${G}_{i}$ is the copy of either $\mathscr{H}_{k}$ or
$\mathscr{C}_{k}$ and $V_{i}=V({G}_{i})$ (this partition is indicated in
Figure 2). As before, we define $\mathcal{C}_{b}^{i}$ to be the set of the $b$
outermost cycles of $G_{i}$, and we define $B_{b}^{i}\coloneqq
V(\boldsymbol{\boldsymbol{\bigcup}}\mathcal{C}_{b}^{i})$ and
$X_{b}^{i}=X\setminus B_{b}^{i}.$ We now choose $i$ such that $|X_{b}^{i}|$ is
maximized and this means that
$|X_{b}^{i}|\geq\lfloor\frac{k-b}{2k_{0}(h+c)}\rfloor.$ We distinguish two
cases, depending on whether ${G}_{i}=\mathscr{H}_{k}$ or
${G}_{i}=\mathscr{C}_{k}.$

_Case 1_. ${G}_{i}=\mathscr{H}_{k}.$ Let $k^{\prime}=\lfloor k/2\rfloor.$ Let
$\overline{\mathcal{C}}_{b}^{i}$ be the cycles of $\mathscr{H}_{k}$ that are
not in $\mathcal{C}_{b}^{i}$. As a first step, among the $k-b$ cycles of
$\overline{\mathcal{C}}_{b}^{i}$ we consider the set $\mathcal{C}$ of
$k^{\prime}-b$ such cycles whose union meets the biggest possible number of
vertices in $X_{b}^{i}.$ Observe that the cycles of $\mathcal{C}$ meet at
least $|X_{b}^{i}|(\frac{1}{2}-\frac{b}{2k-2b})$ vertices of $X_{b}^{i}.$ Let
$X_{b}^{*i}=X_{b}^{i}\cap V(\boldsymbol{\boldsymbol{\bigcup}}\mathcal{C})$ and
keep in mind that
$|X_{b}^{*i}|\geq\lfloor(\frac{1}{2}-\frac{b}{2k-2b})\frac{k-b}{2k_{0}(h+c)}\rfloor\geq\lfloor\frac{k-2b}{4k_{0}(h+c)}-\frac{b}{4k_{0}(h+c)}\rfloor=\lfloor\frac{k-3b}{4k_{0}(h+c)}\rfloor.$

We now consider the minor $G^{*}_{i}$ of ${G}_{i}$ that is obtained if we
contract every edge that is not in a handle or crosscap path, has endpoints in
different cycles of $\overline{\mathcal{C}}_{b}^{i}$ and does do not have both
endpoints in $V(\boldsymbol{\boldsymbol{\bigcup}}\mathcal{C})$ (we assume
that, during contractions, vertices in $X^{*i}_{b}$ prevail). Notice that
$G_{i}^{*}$ is a minor of $G$ containing the vertices of $X_{b}^{*i}$ (that
are also vertices of $G_{i}$).

Notice now that $G^{*}_{i}$ contains a $(8k^{\prime}\times
k^{\prime})$-cylindrical grid as a spanning subgraph that contains
$k^{\prime}$ cycles and $8k^{\prime}$ paths that we call _rails_. Anti-
diametrical pairs of rails can be seen as subpaths of paths of length
$2k^{\prime}-1,$ we call them _crossing paths_ , whose endpoints are in the
outer cycle of $G^{*}.$ Notice that, the vertex set of $G^{*}$ is the union of
two disjoint $2k^{\prime}\times 2k^{\prime}$-grids, say $\Gamma^{1}$ and
$\Gamma^{2}.$ We call a crossing path of $G^{*}$ _vertical_ if it belongs to
$\Gamma^{1}$ and _horizontal_ if it belongs to $\Gamma^{2}.$

Also, $G^{*}$ contains four pairwise disjoint $(2k^{\prime}\times
k^{\prime})$-grids. We call them _north, south, west_ , and _east grid_. (In
Figures 15 and 16 each these grids is bicolored by red/blue frames.)

We now assume that the south grid has the majority of the vertices of
$X_{b}^{*}.$ Let this vertex set be $\hat{X}_{b}^{*}$ and observe that
$|\hat{X}_{b}^{*}|\geq\lfloor|{X}_{b}^{*}|/4\rfloor\geq\lfloor\frac{k-3b}{16k_{0}(h+c)}\rfloor.$
Next we observe that there is a subset $S_{b}$ of $\hat{X}_{b}^{*}$ and a set
$\mathcal{Q}$ of $2b$ consecutive vertical crossing paths such that
$|S_{b}|\geq\lfloor\frac{|\hat{X}_{b}^{*}|}{2b}\rfloor-1$ and
$S_{b}\cap\boldsymbol{\boldsymbol{\bigcup}}\mathcal{Q}=\emptyset.$ W.l.o.g. we
assume that the majority of the vertices of $S_{b}$ is “on the right” of the
vertical crossing paths in $\mathcal{Q}$, and we denote these vertices by
$S_{b}^{\prime}.$ Clearly
$|S_{b}^{\prime}|\geq\lfloor|S_{b}|/2\rfloor\geq\lfloor\frac{k-3b}{64bk_{0}(h+c)}\rfloor-1.$

Figure 16:  A visualization of the second subcase of Case 1 in the proof of
Subsection 7.1, where $k^{\prime}=10,$ $b=2,$ $m=12,$ and $r=13.$ The $b$
outermost cycles are colored green. We depict the partition of $G^{*}$ to four
pairwise disjoint $(2k^{\prime}\times k^{\prime})$-grids, and the $(m\times
m)$-grid $\Gamma_{m}$ as a minor in it. The perimeter of the central
$(m-2b)\times(m-2b)$-subgrid is depicted red.

Let $r$ be the number of consecutive rails in the south grid starting from the
second half of the paths in $\mathcal{Q}$ (notice that $r\geq b+1$ as at least
one rail should be intersected by $S_{b}^{\prime}$). In Figure 15 and Figure
16 we have that $r=5$ and $r=13$ respectively. Let $m=k^{\prime}+b.$ We will
consider a subdivision of a $(m\times m)$-grid $\Gamma_{m}$ by considering
rails of the south grid and, possibly, some of the east one. For this, we
distinguish two subcases as follows:

  * •

If $r<k^{\prime}$ then we complete the $r$ rails with the $k^{\prime}-r+b$
lower rails in the east grid and construct an $(m\times m)$-grid $\Gamma_{m}$
(see Figure 15). Set $S_{b}^{\prime\prime}\coloneqq S_{b}^{\prime}.$

  * •

If $r\geq k,$ then among all $((k^{\prime}-b)\times k)$-grids that can be made
using $k^{\prime}-b$ rails of the south grid and on the right of
$\mathcal{Q},$ consider those that intersect the biggest number of vertices in
$S_{b}^{\prime}.$ Also complete the $(m\times m)$-grid $\Gamma_{m}$ by adding
$b$ rails from the rightmost grid (see Figure 16). Let $S_{b}^{\prime\prime}$
be the vertices of $S_{b}^{\prime}$ that belong to the $k^{\prime}-b$ chosen
rails and observe that
$|S_{b}^{\prime\prime}|\geq\lfloor|S_{b}^{\prime}|/2\rfloor.$

Notice that, in any case
$|S_{b}^{\prime\prime}|\geq\lfloor|S_{b}^{\prime}|/2\rfloor\geq
f(b,k)\coloneqq\lfloor\frac{k-3b}{128bk_{0}(h+c)}\rfloor-1$. In other words,
the central $(m-2b)\times(m-2b)$-subgrid of this $(m\times m)$-grid contains
at least $f(b,k)$ vertices whose precursors contain vertices from $X_{b}.$

_Case 2_. ${G}_{i}=\mathscr{C}_{k}.$ As we did before, we refer to the $4k$
paths of $\mathscr{C}_{k}$ as _rails_. Also, anti-diametrical pairs of rails
are seen as subpaths of $2k$ paths of length $2k-1$ and, as before, we call
them _crossing paths_ (see Figure 17). Notice that the vertex set of
$\mathscr{C}_{k}$ is the union of two disjoint $(2k\times k)$-grids, say
$\Gamma^{1}$ and $\Gamma^{2}.$ We call a crossing path of $\mathscr{C}_{k}$
_vertical_ if it belongs to $\Gamma^{1}$ and _horizontal_ if it belongs to
$\Gamma^{2}.$

Observe that there is a subset $S_{b}$ of $X_{b}^{i}$ and a set $\mathcal{Q}$
of $2b$ consecutive crossing paths such that
$|S_{b}|\geq\lfloor\frac{|X_{b}^{i}|}{2b}\rfloor-1$ and
$S_{b}\cap\boldsymbol{\boldsymbol{\bigcup}}\mathcal{Q}=\emptyset.$ We have
that $|S_{b}|\geq f(b,k)\coloneqq\lfloor\frac{k-3b}{4bk_{0}(h+c)}\rfloor-1.$

Let $m=2k.$ Observe that $\mathscr{C}_{k}$ contain as a spanning subgraph an
$(m\times m)$-grid $\Gamma_{m}.$ To see this, it is enough to remove all the
edges between the vertices of the $b$-th and the vertices of the $(b+1)$-th
path of $\mathcal{Q}$ from $\mathscr{C}_{k}$.

Figure 17:  A visualization of Case 2 in the proof of Subsection 7.1, where
$k=9,$ $b=2,$ and $m=18.$ The $b$ outermost cycles are colored green. We
depict the partition of ${G}_{i}=\mathscr{C}_{k}$ to four pairwise disjoint
$(k\times k)$-grids and the $(m\times m)$-grid as a spanning subgraph of
$\mathscr{C}_{k}.$ The perimeter of the central $(m-2b)\times(m-2b)$-subgrid
is depicted red.

Notice that the subgraph of $\Gamma_{m}$ induced by its $b$ outermost vertices
is exactly
$\Gamma_{m}\setminus(B_{b}\cup\boldsymbol{\boldsymbol{\bigcup}}\mathcal{Q}).$
Moreover, the central $(m-2b)\times(m-2b)$ subgrid of $\Gamma_{m}$ contains at
least $f(b,k)$ vertices from $X_{b}.$

In both of the two cases above, we choose the margin $b_{k}$ as the maximum
integer $b$ such that $\lfloor\sqrt[4]{f(b,k)}\rfloor\geq 2b.$ This implies
that $\lfloor\sqrt[4]{|S_{b_{k}}|}\rfloor\geq 2b_{k},$ therefore, by
Subsection 6.2, ${\sf
bg}({\tilde{\mathscr{D}}^{(h,c)}_{k}},X)\geq\lfloor\sqrt[4]{|S_{b_{k}}|}\rfloor\geq
2b_{k}.$ Observe now that in both cases $b_{k}\in Θ_{h,c}(k^{1/5}),$
therefore, by Subsection 6.2 ${\sf
bg}({\tilde{\mathscr{D}}^{(h,c)}_{k}},X)\in\Omega_{h,c}(k^{1/5}).$ ∎

###  7.2 Lower bounds under the presence of clique-sums

It now remains to prove that, given that ${\sf
bg}_{\Sigma}(\hat{\mathscr{D}}_{k}^{(h,c)})$ is big, then also ${\sf
bg}_{\Sigma}^{*}(\hat{\mathscr{D}}_{k}^{(h,c)})$ is also big.

A _partially triangulated $(k\times k)$-grid_ is any graph that can be
obtained from a $(k\times r)$-grid (we call it the underlying grid) by adding
edges in a way that the resulting graph remains planar. A _dusted partially
triangulated $(k\times k)$-grid_ is the disjoint union of a partially
triangulated $(k\times k)$-grid and a set of isolated vertices.

The following lemma follows easily from the results of [31] (see also [18]).

######  Proposition .

There is a universal constant $c$ such that every graph $G$ were ${\sf
bg}(G)\geq c\cdot\big{(}\big{(}{\sf hw}(G)\big{)}^{48}+r\big{)}$ contains a
vertex set $A$ of size $c\cdot\big{(}{\sf hw}(G)\big{)}^{24}$ such that $G-A$
can be contracted to a dusted partially triangulated $(r\times r)$-grid.

For $k\in\mathbb{N}_{{\geq 1}},$ a graph is a _crossed $k$-grid_ if it can be
obtained as follows: first take a $(k+2)\times(k+2)$ grid, then remove all
outermost layer edges (edges with both endpoints of degree $<4$), subdivide
each of the remaining edges at least once and then take the line graph.

######  Observation .

If $G$ has a tree-decomposition where all torsos have Hadwiger number at most
$h,$ then also $G$ has Hadwiger number at most $h.$ In short, ${\sf hw}={\sf
hw}^{*}.$

######  Lemma .

There is some universal constant $c$ such that if a graph $G$ contains a
crossed $t$-grid, for some $t\in\mathbb{N}_{\geq 1},$ then $t\leq c\cdot({\sf
hw}(H))^{2}.$

###### Proof.

If, in a crossed $2t(t-1)$-grid, we contract all edges that do not belong to
$4$-cliques we obtain a graph that contains the grid-like graph
$H^{1}_{t(t-1)}$ defined by Kawarabayashi, Thomas, and Wollan in [31] as a
subgraph. According to [31, Lemma 3.2.], $H^{1}_{t(t-1)}$ contains $K_{t}$ as
a minor. ∎

######  Lemma .

Let ${\cal G}$ be a graph class of Hadwiger number at most $η$. Then, for
every graph $G$, ${\sf hw}(G)\leq({\sf bg}_{\mathcal{G}}(G))^{2}+η+1$.

Figure 18: A crossed $6$-grid. Subdivision vertices are depicted in yellow.

###### Proof.

Suppose that ${\sf hw}(G)=t.$

Let $X$ be a modulator of $G$ to $\mathcal{G}$. Notice that $G$ can be
identified, via contractions, to the clique $K_{t}.$ Let $X^{\prime}$ be the
heir of $X$ during these contractions. Notice that $X^{\prime}$ remains an
modulator of $K_{t}$ to $\mathcal{G},$ therefore $|X^{\prime}|\geq t-η.$
Notice that ${\sf bg}(G,X)\geq{\sf bg}(K_{k},X^{\prime})$ and that ${\sf
bg}(K_{t},X^{\prime})\geq{\sf
bg}(K_{t}[X^{\prime}])\geq\lfloor|X^{\prime}|^{1/2}\rfloor\geq\lfloor(t-η)^{1/2}\rfloor\geq(t-η-1)^{1/2}.$
This implies that ${\sf bg}_{\mathcal{G}}(G)\geq(t-η-1)^{1/2}$, and the lemma
follows. ∎

#### A new variant of the Dyck-grid.

For the purposes of our proofs, we will consider an “enhanced version” of
$\tilde{\mathscr{D}}_{k}^{(h,c)},$ namely
$\hat{\mathscr{D}}^{(h,c)}=\langle\hat{\mathscr{D}}_{k}^{(h,c)}\rangle$ which
is obtained from $\tilde{\mathscr{D}}_{k}^{(h,c)}$ as follows: Consider a set
of $k(h+c)$ pairwise disjoint paths on $4$ vertices of the outermost cycle. We
take them so that the paths are parts of the the perimeters of the (pairwise
disjoint) $2h$ $(2k\times k)$-grids and $c$ $(2k\times 2k)$-grids
corresponding to the handles and the crosscaps of
$\tilde{\mathscr{D}}_{k}^{(h,c)}$ (there is a unique way these paths can be
considered). Then, for each of these paths, introduce a new vertex and make it
adjacent with its four vertices. We call the $k(h+c)$ new vertices in this
construction satellite vertices (see Figure 19).

We say that a parametric graph
$\mathscr{H}=\langle\mathscr{H}_{k}\rangle_{k\in\mathbb{N}}$ has the _$f$
-tightly connected_ for some non-decreasing function
$f:\mathbb{N}\to\mathbb{N}$, if for every separation $(B_{1},B_{2})$ of
$\mathscr{H}_{k}$ of order $q<k$ such that both $G[B_{1}\setminus B_{2}]$ and
$G[B_{2}\setminus B_{1}]$ are connected, it holds that one of $B_{1},$ $B_{2}$
has at most $f(q)$ vertices.

######  Lemma .

Let ${\sf p}$ be some minor-monotone graph parameter and let
$h:\mathbb{N}\to\mathbb{N}$ such that for every graph $G$, ${\sf hw}(G)\leq
h({\sf p}(G))$. Let also
$\mathscr{H}=\langle\mathscr{H}_{k}\rangle_{k\in\mathbb{N}}$ be a parametric
graph that is $g$-tightly connected, for some $g:\mathbb{N}\to\mathbb{N}$. Let
$r\in\mathbb{N}$ and let ${(T,\beta)}$ be a tree decomposition of $G$ where,
for each torso $G_{\bar{t}}$, it holds that ${\sf p}(G_{\bar{t}})\leq r$. If
$2(g(h(r)))<|V(\mathscr{H}_{k})|$ and $h(r)<k$, then $\mathscr{H}_{k}$ admits
a tree decomposition $(\hat{T},\hat{\beta})$ where $\hat{T}$ is a star with
center $t$, where ${\sf p}(G_{t})\leq r$ ($G_{t}$ is the torso of
$(\hat{T},\hat{\beta})$ on $t$) and where for every $e=tt^{\prime}\in
E(\hat{T})$, $\mathscr{H}_{k}[\hat{β}(t^{\prime})\setminus\hat{β}(t)]$ is a
connected graph and $|\hat{β}(t^{\prime})|\leq g(h(r))$.

###### Proof.

For simplicity we set $G=\mathscr{H}_{k}$. Let $e=tt^{\prime}\in E(T)$ and let
$T_{t}$ and $T_{t^{\prime}}$ be the two connected components of $T-e,$ where
$t\in V(T_{t})$ and $t^{\prime}\in V(T_{t^{\prime}}).$ We define
$B_{t}\coloneqq\bigcup_{s\in V(T_{t})}β(s)$,
$B_{t^{\prime}}\coloneqq\bigcup_{s\in V(T_{t^{\prime}})}β(s)$, and
$A_{t,t^{\prime}}\coloneqq B_{t}\cap B_{t^{\prime}},$ i.e., $A_{t,t^{\prime}}$
is the common adhesion of $t$ and $t^{\prime}.$ We next modify $(T,β)$ as
follows.

_Claim._ We can assume that, for every $e=tt^{\prime},$ every graph in
$\\{G[B_{t}\setminus B_{t^{\prime}}],G[B_{t^{\prime}}\setminus B_{t}]\\}$ is
void or connected.

_Proof of Claim_ : Suppose that this is not the case and assume that for some
edge $e=tt^{\prime}\in E(T),$ $G^{\prime}=G[B_{t}\setminus B_{t^{\prime}}]$ is
not connected and has $r$ components $H_{1},\ldots,H_{r}.$ Let $Y$ be the
component of $T-tt^{\prime}$ containing $t.$ We replace this component in $T$
with $r$ copies of $Y,$ say $Y_{1},\ldots,Y_{r},$ and for each one of them
make the leaf $t^{i}$ corresponding to $t$ adjacent to $t^{\prime}.$ The new
tree is denoted by $\hat{T}.$ We define $\hat{β}\colon V(\hat{T})\to 2^{V(G)}$
such that, if $s\not\in V(Y),$ then $\hat{β}(s)\coloneqq β(s),$ and if $s$
belongs to $Y_{i},i\in[r],$ then we set $\hat{β}(s)\coloneqq β(s)\cap
V(H_{i}).$ It is easy to see that $(\hat{T},\hat{β})$ is a tree-decomposition
of $G.$ Notice that each torso $G_{\hat{T}}^{*}$ of $(\hat{T},\hat{β})$ is the
subgraph of some torso $G_{t}$ of $(T,β).$ This means that if ${\sf
p}(G_{t})\leq r$ holds for each torso $G_{t}$ of $(T,β),$ then the same holds
for the torsos of $(\hat{T},\hat{β})$. By repeating the above improvements as
long as there are edges violating the statement of the claim, we finally have
the required tree-decomposition.

Let $t\in V(T)$ and $t^{\prime}\in N_{T}(t)$. The set $A_{t,t^{\prime}}$
induces a clique in $G_{t}$, therefore, $|A_{t,t^{\prime}}|\leq{\sf
hw}(G_{t})\leq h({\sf p}(G_{t}))\leq h(r)<k$. As $G$ is $g$-tightly connected,
it holds hat $\min\\{|B_{t}|,|B_{t^{\prime}}|\\}\leq g(|A_{t,t^{\prime}}|)\leq
g(h(r)),$ therefore
$\max\\{|B_{t}|,|B_{t^{\prime}}|\\}\geq|G|-g(h(r))>g(h(r))\geq\min\\{|B_{t}|,|B_{t^{\prime}}|\\}.$
This permits us to orient every edge $tt^{\prime}$ towards $t,$ if
$|B_{t}|>|B_{t^{\prime}}|$ and towards $t^{\prime},$ if
$|B_{t^{\prime}}|>|B_{t}|.$ This orientation of $T$ implies that there is a
unique node $t$ where all incident edges are oriented towards it. This means
that, for every $t^{\prime}\in N_{T}(t)$, we have that $|B_{t^{\prime}}|\leq
g(h(r)).$

We now build the claimed tree decomposition $(\hat{T},\hat{\beta})$ where
$\hat{T}$ is the subtree of $T$ that is induced by $t$ an its neighbors
$t^{\prime}$ in $T$ where $B_{t^{\prime}}\setminus A_{t,t}\neq\emptyset$.
Finally, for each $t^{\prime}\in V(\hat{T}\setminus\\{t\\})$, we set
$\hat{β}(t^{\prime})=B_{t^{\prime}}$. ∎

Figure 19: The graph $\hat{\mathscr{D}}_{8}^{1,2}$. The satellite vertices are
depicted as squares. The magenta and the blue vertices correspond to the
vertices in $A$ and $Y$ respectively, in the proof of Subsection 7.2.

######  Lemma .

Let $(h,c)\in\mathbb{N}\times[0,2]\setminus\\{(0,0)\\}$. Then
$\hat{\mathscr{D}}^{(h,c)}$ is $f_{\ref{@vegetables}}$-tightly connected for
$f_{\ref{@vegetables}}(q)=(2q+1)^{2}$.

###### Proof.

Let $G\coloneqq\hat{\mathscr{D}}_{k}^{(h,c)}.$ Let $(B_{1},B_{2})$ be a
separation of $G$ of order $q<k.$ Let $A=B_{1}\cap B_{2},$
$D_{1}=B_{1}\setminus A,$ and $D_{2}=B_{2}\setminus A.$ Also we know that both
$G[D_{1}]$ and $G[D_{2}]$ are connected. Let $Q$ be the spanning
$(4k(h+c)\times k)$-annulus grid of $G.$ Clearly $Q$ contains $k$ cycles. Also
it contains $4k(h+c)$ paths, each on $k$ vertices, which we call _tracks_. We
also use $R$ for the set of the satellites of $\hat{\mathscr{D}}_{k}^{(h,c)}$.
We enhance the tracks by extending each of them to the unique satellite vertex
that is adjacent to one of its endpoints. Let $Y$ be the union of all the
$\geq k-q$ cycles that are not met by $A$ and of all $\geq 4k(h+c)-4q$ tracks
that are not met by $A$ (observe that if a vertex of $A$ belongs to $R$, then
it meets four tracks). See Figure 19 for a visualization of $A$ and $Y$ in the
graph $\hat{\mathscr{D}}_{8}^{1,2}$.

As every track in $Y$ has a common endpoint to every cycle in $Y,$ we obtain
that $Y$ is connected, therefore $V(Y)$ is either a subset of $D_{1}$ or a
subset of $D_{2}.$ W.l.o.g., we assume that $V(Y)\subseteq D_{1}.$ We next
prove that $|B_{2}|\leq(2q+1)^{2}.$

Let $x$ be a vertex of $D_{2}$ and let $P_{x}$ be some path of $G[B_{2}]$
starting from $x$ and finishing to some vertex of $A$ and with all internal
vertices in $D_{2}.$ This path cannot meet more than $q=|A|$ cycles of $Q$
because each such cycle contains some vertex of $S\subseteq D_{1}.$ Similarly,
$P_{x}$ cannot meet more than $q=|A|$ tracks as each such track contains some
vertex of $Y\subseteq D_{1}.$ This implies that every vertex of $G[B_{2}]$
should be at distance at most $q$ from $x.$ It is now easy to verify that, in
$G,$ the vertices at distance at most $q$ from some $x\in A$ is upper bounded
by $(2q+1)^{2}.$ As all vertices of $B_{2}$ are accessible from $x$ at this
distance in $G[B_{2}],$ we conclude that $|B_{2}|\leq(2q+1)^{2}.$ ∎

######  Lemma .

Let $G$ be a 4-connected graph of maximum degree $\Delta$. Let
$r\in\mathbb{N}$ and let $(T,\beta)$ be a tree decomposition of $G$ where $T$
is a star with center $t$ and such that for every $e=tt^{\prime}\in E(T)$,
$G[β(t^{\prime})]$ is a connected graph on at most $l$ vertices. Let $G_{t}$
be the torso of $(T,\beta)$ at $t$ and we denote $G^{c}=(V(G),E(G)\cup
E(G_{t}))$, $m={\sf hw}(G^{c})$, and $B=\bigcup_{t^{\prime}\in
V(T)\setminus\\{t\\}}β(t^{\prime})$. There is a function
$f_{\ref{blackbox}}:\mathbb{N}^{4}\to\mathbb{N}$ such that if $X$ is a subset
of $V(G_{t})$ where ${\sf bg}(G_{t},X)\leq r$, then ${\sf bg}(G^{c},X\cup
B)\leq f_{\ref{blackbox}}(r,m,l,\Delta)$. Moreover,
$f_{\ref{blackbox}}(r,m,l,\Delta)\in\mathcal{O}(m^{48}+r^{1/2}\cdot(m^{8}l^{4}+\Delta
m^{24}l^{2}))\subseteq\text{$\mathsf{poly}$}(m+l+r+\Delta)$.

###### Proof.

We need to introduce some constants (all depending on $\Delta$, $m$, $l$, and
$r$). From now on, $c$ and $c^{\prime}$ are the universal constants of
Subsection 7.2 and Subsection 7.2 respectively. We set

$\displaystyle\hat{h}$
$\displaystyle\coloneqq\max\\{2l+1,c^{\prime}m^{2}+3\\}\in\mathcal{O}(m^{2}),$
$\displaystyle d$
$\displaystyle\coloneqq(c^{\prime}m^{2}+3)^{4}\cdot(1+2l)^{2}+c\cdot
m^{24}\in\mathcal{O}(m^{8}l^{2}+m^{24}),$ $\displaystyle t$
$\displaystyle\coloneqq d\cdot(1+4l)^{2}+\Delta c\cdot
m^{24}\in\mathcal{O}(m^{8}l^{4}+\Delta m^{24}l^{2}),$ $\displaystyle a$
$\displaystyle\coloneqq\lceil{(t+1)^{1/2}}\rceil\cdot(r+1)+2l+2\hat{h}\in\mathcal{O}(r^{1/2}\cdot(m^{8}l^{4}+\Delta
m^{24}l^{2})),\mbox{\leavevmode\nobreak\ and}$ $\displaystyle a^{\prime}$
$\displaystyle\coloneqq
c\cdot(m^{48}+a)\in\mathcal{O}(m^{48}+r^{1/2}\cdot(m^{8}l^{4}+\Delta
m^{24}l^{2}))\subseteq\text{$\mathsf{poly}$}(m+l+r+\Delta).$

Let $H$ be an $(X\cup B)$-minor of $G^{\mathsf{c}}$ such that ${\sf
bg}(H)={\sf bg}(G^{\mathsf{c}},X\cup B)>a^{\prime}.$ We claim that it is
enough to prove that ${\sf bg}(H-B)>r$. Indeed, as $H-B$ is an $X\setminus
B$-minor of $G_{t}$, this implies ${\sf bg}(G_{t},X\setminus B)>r$ which
implies ${\sf bg}(G_{t},X)\geq r$. We next prove that ${\sf bg}(H-B)>r$.

By Subsection 7.2, we have that $H$ contains a vertex set $\hat{A}$ where
$|\hat{A}|\leq c\cdot m^{24}$ and such that $H-\hat{A}$ can be contracted to a
dusted partially triangulated $(a\times a)$-grid $D_{a}.$ Keep in mind that
the fact that $D_{a}$ is a contraction of $H-\hat{A}$ means that if two
vertices of $D_{a}$ are at distance $\geq\delta$ in $D_{a}$, then their
precursors in $H-\hat{A}$ are also at distance $\geq\delta$.

The fact that $H$ is an $X\cup B$-minor of $G^{\mathsf{c}}$ implies that the
set of precursors of a vertex $v$ of $D_{a}$ in $H,$ and also in
$G^{\mathsf{c}},$ contains some vertex of $X\cup B.$

Let $q=a-2\hat{h}$ and consider the central $(q\times q)$-grid $D_{q}$ of
$D_{a}$ We say that a vertex $v$ of $D_{q}$ is _marked_ by some vertex
$t^{\prime}\in N\coloneqq V(T)\setminus\\{t\\},$ if its precursor in $H$, and
also in $G^{\mathsf{c}}$, contains some vertex of $C\coloneqq B\setminus
β(t)$, Notice that $v$ may be marked by more than one vertex $t^{\prime}$ of
$N.$ We also define, for each $t^{\prime}\in N,$ we set
$A_{t^{\prime}}=β(t)\cap β(t^{\prime})$.

As an important ingredient of the proof, we prove that there cannot be many
marked vertices.

######  Claim .

$D_{q}$ has at most $d$ marked vertices.

###### Proof of claim.

Let $\hat{M}$ be the set of marked vertices of $D_{q}$ and suppose to the
contrary that

$|\hat{M}|>d=(c^{\prime}m^{2}+3)^{4}\cdot(1+4l)^{2}+c\cdot m^{24}.$

Notice that for at least $|\hat{M}|-c\cdot m^{24}$ of the vertices in
$\hat{M},$ the set $C_{t^{\prime}}\coloneqq β(t^{\prime})\setminus β(t)$ that
contains their precursor can be chosen so that it does not intersect $\hat{A}$
and we call them _strongly marked_. Let $M$ be the set of strongly marked
vertices of $D_{q}$ and keep in mind that
$|{M}|>(c^{\prime}m^{2}+3)^{4}\cdot(1+4l)^{2}.$ We say that two strongly
marked vertices $v_{1}$ and $v_{2}$ are _independent_ if there is no
$t^{\prime}\in N$ such that both $v_{1}$ and $v_{2}$ are marked by
$t^{\prime}.$ We know that each $C_{t^{\prime}}$ has at most
$|β(t^{\prime})|\leq l$ vertices. Therefore, if $v_{1}$ (resp. $v_{2}$) is
strongly marked by $t^{\prime}_{1}$ (resp. $t^{\prime}_{2}$) and
$\mathsf{dist}_{D_{a}}(v_{1},v_{2})\geq 2l+1$ then $C_{t_{1}^{\prime}}\cap
C_{t_{2}^{\prime}}=\emptyset$ which, in turn, implies that $v_{1}$ and $v_{2}$
are independent.

We now construct a set $M^{\prime}\subseteq M$ of pairwise-independent
strongly marked vertices of $D_{q}$ by greedily picking from $M$ a strongly
marked vertex $x$ and then excluding as possible choices all vertices of $M$
that are at distance $<2l+1$ from $x$ in $D_{a}$.

Recall that $2l+1\leq\hat{h},$ therefore, a vertex in the partially
triangulated grid $D_{q}$ has at most $(1+4l)^{2}$ vertices at distance $\leq
2l$ in $D_{a}.$ We obtain that
$|M^{\prime}|\geq|M|/(1+4l)^{2}\geq(c^{\prime}m^{2}+3)^{4}.$ Let
$\ell\coloneqq c^{\prime}m^{2}+3$ and recall that $\ell\leq\hat{h}.$

We have just found a set of $\ell^{4}$ vertices of $M^{\prime}$ that belong to
the central $(a-2\ell)\times(a-2\ell)$-grid of $D_{a}.$ By Subsection 6.2,
$D_{a}$ contains an $(\ell\times\ell)$-grid $\Gamma_{\ell}$ as an
$M^{\prime}$-minor. This also implies that $H,$ and also $G^{\mathsf{c}},$
contains $\Gamma_{\ell}$ as a minor. For every vertex $u$ of $\Gamma_{\ell}$
we know that the set of its precursors in $H$, and also in $G^{\mathsf{c}}$,
contains some vertex $z_{u}$ of some set $C_{t^{\prime}_{u}}$ that does not
intersect $\hat{A}.$ As there may be many possible choices of $z_{u},$ from
now on, we arbitrarily fix one so to uniquely determine $t^{\prime}_{u}$ and
$C_{t^{\prime}_{u}}$ as well.

By the way we defined $M^{\prime},$ it holds that, for distinct $u$’s in
$\Gamma_{\ell},$ the corresponding $C_{t^{\prime}_{u}}$’s are pairwise
disjoint and moreover, the corresponding $t^{\prime}_{u}$’s as well as the
corresponding $z_{u}$’s are also pairwise distinct. Let $u\in
V(\Gamma_{\ell}).$ As $G$, and therefore also $G^{\mathsf{c}}$, is
4-connected, we have that $|A_{t^{\prime}_{u}}|\geq 4$. Moreover, in
$G^{\mathsf{c}}$, there are four internally disjoint paths in
$G[β(t^{\prime}_{u})]$ starting from $z_{u}\in C_{t^{\prime}_{u}},$ finishing
at any possible choice of four distinct vertices of $A_{t^{\prime}_{u}}$ and
such that the internal vertices of these paths all belong to
$C_{t^{\prime}_{u}}.$

Figure 20: A visualization of the grids $D_{a}$ and $D_{q}$ in the proof of
Subsection 7.2. In red we depict the vertices $z_{t^{\prime}_{u}}$ of the of
the $(\ell\times\ell)$-grid $\Gamma_{\ell}$ (the corners are squares). In blue
we depict the subdivided paths of $\Gamma_{\ell}$ that are also paths of
$G^{\mathsf{c}}.$ The corresponding $C_{t^{\prime}_{u}}$’s (resp.
$A_{t^{\prime}}$’s) are in yellow (resp. green).

The above imply that the $4$-connected graph $G^{\mathsf{c}}$ contains as a
subgraph a subdivision $L$ of the $(\ell\times\ell)$-grid where the vertices
of degree four are all vertices of $Z\coloneqq\\{z_{t^{\prime}_{u}}\mid u\in
V(\Gamma_{\ell})\\}$ (see Figure 20). Let $x\coloneqq z_{t^{\prime}_{u}}\in Z$
and assume that, in the subdivided grid $L,$ $x$ is the intersection of the
“horizontal” path $H_{x}$ and the “vertical” path $V_{x}.$

We traverse $H_{x}$ from left to right and we define $x^{\textrm{left}}$ to be
the first vertex of $A_{t^{\prime}_{u}}$ appearing on $H_{x}$ and
$x^{\textrm{right}}$ to be the last vertex of $A_{t^{\prime}_{u}}$ appearing
on $H_{x}.$ Similarly, we traverse $V_{x}$ from up to down and we define
$x^{\textrm{up}}$ to be the first vertex of $A_{t^{\prime}_{u}}$ appearing on
$V_{x}$ and $x^{\textrm{down}}$ to be the last vertex of $A_{t^{\prime}_{u}}$
appearing on $V_{x}.$ We now construct a subgraph $L^{\prime}$ of $L$ by
removing, for each $x=z_{t^{\prime}_{u}}\in Z,$ all internal vertices of the
path between $x^{\textrm{left}}$ and $x^{\textrm{right}}$ and all internal
vertices of path between $x^{\textrm{up}}$ and $x^{\textrm{down}}.$

Notice, that by the choice of the quadruples
$\\{x^{\textrm{left}},x^{\textrm{right}},x^{\textrm{up}},x^{\textrm{down}}\\},$
the remaining graph $L^{\prime}$ is a subgraph of $G^{\mathsf{c}}.$ Moreover,
if, for every $x=z_{t^{\prime}_{u}}\in Z,$ we add all six pairs from
$\\{x^{\textrm{left}},x^{\textrm{right}},x^{\textrm{up}},x^{\textrm{down}}\\}$
as edges to $L^{\prime}$ then we have an $(\ell-2)$-crossed grid (depicted in
Figure 18) as a subgraph of $G^{\mathsf{c}}$ (these six edges exist in
$G^{\mathsf{c}}$ as they are edges of the clique induced by
$A_{t^{\prime}_{u}}$). Recall that $\ell=c^{\prime}m^{2}+3.$ From Subsection
7.2 we obtain that $c^{\prime}m^{2}+1=\ell-2\leq c^{\prime}\cdot({\sf
hw}(G^{\mathsf{c}}))^{2}\leq^{\eqref{@precensored}}c^{\prime}m^{2},$ a
contradiction and the claim follows. ∎

Figure 21: A visualization of the last part of the proof of Subsection 7.2.
The blue lines indicate the packing of the $t+1$ pairwise vertex-disjoint
$(r+1,r+1)$-grids in $D_{q^{\prime}}$

We set $q^{\prime}\coloneqq q-2l\geq
a-2\hat{h}-2l=\lceil{(r+1)^{1/2}}\rceil\cdot(t+1)$, and we denote by
$D_{q^{\prime}}$ the central $(q^{\prime}\times q^{\prime})$-grid
$D_{q^{\prime}}$ of $D_{q}.$ Let ${B}^{(q^{\prime})}$ be the vertices of
$V(D_{q^{\prime}})$ whose set of precursors in $G^{\mathsf{c}}$ contains a
vertex of some $β(t^{\prime}),t^{\prime}\in N$ where
$β(t^{\prime})\cap\hat{A}=\emptyset$.

Observe that, because $|β(t^{\prime})|\leq l$ and $G[B_{t^{\prime}}]$ is
connected, every vertex $u\in B^{(q^{\prime})}$ should be at distance at most
$l$ from some of the $\leq d$ marked vertices of $D_{q}.$ As a consequence,
$|B^{(q^{\prime})}|\leq d\cdot(1+2l)^{2}.$ Let now $\tilde{B}^{(q^{\prime})}$
be the vertices of $V(D_{q^{\prime}})$ whose precursors in $H$ contain a
vertex of some $B_{t^{\prime}}$ that, moreover, contains some vertex of
$\hat{A}.$ As all vertices in $\hat{A}$ have degree at most $\Delta$, each of
them may be adjacent with at most $\Delta$ vertices of some of the
$B_{t^{\prime}}$’s. This means that
$|\tilde{B}^{(q^{\prime})}|\leq\Delta\cdot|\hat{A}|\leq\Delta c\cdot m^{24}.$
We stress that ${B}^{(q^{\prime})}$ and $\tilde{B}^{(q^{\prime})}$ are not
necessarily disjoint, however we just proved that
$|{B}^{(q^{\prime})}\cup\tilde{B}^{(q^{\prime})}|\leq d\cdot(1+2l)^{2}+\Delta
c\cdot m^{24}=t.$

Notice that, by their definition, the vertices in
$V(D_{q^{\prime}})\setminus({B}^{(q^{\prime})}\cup\tilde{B}^{(q^{\prime})})$
have precursors in $H$ that are all vertices of $H-B.$

As $q^{\prime}\geq\lceil{(t+1)^{1/2}}\rceil\cdot(r+1),$ we may consider a
packing of $t+1$ pairwise vertex-disjoint $((r+1)\times(r+1))$-grids of
$D_{q^{\prime}}$. Clearly, for some, say $\Gamma_{r},$ of these
$((r+1)\times(r+1))$-grids, it holds that the precursors in $H$ of its
vertices are all vertices outside $B$ (see Figure 21). This implies that ${\sf
bg}(H-B)\geq r+1$, as required. ∎

We are now ready to prove the main result of this section, that is the
following.

######  Lemma .

Let $(h,c)\in\mathbb{N}\times[0,2]\setminus\\{(0,0)\\}$ and let
$\Sigma\in\mathbb{S}_{h,c}.$ Then ${\sf
bg}_{\Sigma}^{*}(\mathscr{D}_{k}^{(h,c)})\in\Omega_{h,c}(k^{1/480}).$

###### Proof.

Let $η=\max\\{{\sf hw}(G)\mid G\in\mathcal{E}_{\Sigma}\\}.$ Notice that
$\tilde{\mathscr{D}}_{k}^{(h,c)}\leq\hat{\mathscr{D}}_{k}^{(h,c)}\leq\tilde{\mathscr{D}}_{k+1}^{(h,c)},$
therefore
$\tilde{\mathscr{D}}_{k}^{(h,c)}\sim_{{\mathsf{L}}}\hat{\mathscr{D}}_{k}^{(h,c)}.$
By Subsection 7.1, we obtain that
${\mathscr{D}}_{k}^{(h,c)}\sim_{{\mathsf{L}}}\hat{\mathscr{D}}_{k}^{(h,c)}.$
By Subsection 7.1 and the fact that
${\mathscr{D}}_{k}^{(h,c)}\sim_{{\mathsf{L}}}\hat{\mathscr{D}}_{k}^{(h,c)},$
it is enough to prove that

$\displaystyle{\sf
bg}_{\Sigma}(\hat{\mathscr{D}}_{k}^{(h,c)})\in\mathcal{O}_{h,c}\big{(}{\sf
bg}_{\Sigma}^{*}(\hat{\mathscr{D}}_{k}^{(h,c)})^{96}\big{)}.$ (14)

We prefer to work with $\hat{\mathscr{D}}_{k}^{(h,c)}$ (depicted in Figure
19), instead of $\tilde{\mathscr{D}}_{k+1}^{(h,c)}$ or
${\mathscr{D}}_{k+1}^{(h,c)}$, because it is $4$-connected.

For simplicity, we set $G\coloneqq\hat{\mathscr{D}}_{k}^{(h,c)}$, and we
assume that ${\sf bg}_{\Sigma}^{*}(\hat{\mathscr{D}}_{k}^{(h,c)})\leq r,$
therefore there exists a tree-decomposition ${(T,\beta)}$ of $G$ such that,
for every $t\in V(T)$,

$\displaystyle\max\\{{{\sf bg}_{\Sigma}(G_{t})\mid t\in V(T)}\\}$
$\displaystyle\leq$ $\displaystyle r.$ (15)

Our objective is to prove that ${\sf
bg}_{\Sigma}(G)\in\mathcal{O}_{h,c}(r^{96})$. We set

$\displaystyle m$ $\displaystyle=$ $\displaystyle r^{2}+η+1$ (16)

and we may assume that $2(2m+1)^{2}<4k^{2}$, otherwise ${\sf
bg}_{\Sigma}(G)\leq|V(G)|=4k^{2}(h+c)\leq
2(2m+1)^{2}(h+c)$$\in\mathcal{O}_{h,c}(r^{4})\subseteq\mathcal{O}_{h,c}(r^{96})$,
and we are done. This in turn implies that

$\displaystyle 2(2m+1)^{2}$ $\displaystyle<$ $\displaystyle
4k^{2}({h}+c),\mbox{\leavevmode\nobreak\ and}$ (17) $\displaystyle m$
$\displaystyle<$ $\displaystyle k$ (18)

Notice that the assumptions of Subsection 7.2 hold for ${\sf p}={\sf
bg}_{\Sigma}$ (for the function $h(x)=x^{2}+η+1$, because of Subsection 7.2)
and for $\mathscr{H}=\hat{\mathscr{D}}^{(h,c)}$ for the function
$g(x)=(2x+1)^{2}$ (because of Subsection 7.2). Moreover, given (15) and (16),
the conditions $2(g(h(r)))<|V(\mathscr{H}_{k})|$ and $h(r)<k$ are satisfied,
because of (17) and (18) respectively. Therefore, $G$ has a tree decomposition
$(\hat{T},\hat{\beta})$ where $\hat{T}$ is a star with center $t$. Let $G_{t}$
be the torso of $(\hat{T},\hat{\beta})$ on $t$. From Subsection 7.2, it holds
that ${\sf bg}_{\Sigma}(G_{t})\leq r$, therefore there is some $X\subseteq
V(G_{t})$, such that

$\displaystyle{\sf bg}_{\Sigma}(G_{t},X)\leq r\mbox{\leavevmode\nobreak\
and\leavevmode\nobreak\ }$ (19) $\displaystyle G_{t}-X\in\mathcal{E}_{\Sigma}$
(20)

Moreover, for every $e=tt^{\prime}\in E(\hat{T})$,
$\mathscr{H}_{k}[\hat{β}(t^{\prime})\setminus\hat{β}(t)]$ is a connected graph
and $|\hat{β}(t^{\prime})|\leq g(h(r))=(2m+1)^{2}$.

For all $t^{\prime}\in N\coloneqq N_{\hat{T}}(t),$ we define
$A_{t^{\prime}}=\hat{β}(t)\cap\hat{β}(t^{\prime})$,
$B_{t^{\prime}}=\hat{β}(t^{\prime})$, and
$C_{t^{\prime}}=B_{t^{\prime}}\setminus A_{t^{\prime}}$ and keep in mind that
each $C_{t^{\prime}}$ induces in $G$ a connected graph where

$\displaystyle|C_{t^{\prime}}|\leq|B_{t^{\prime}}|\leq(2m+1)^{2}.$ (21)

Let $G^{\mathsf{c}}\coloneqq\bigcup_{t\in V(T)}G_{t},$
$B\coloneqq\bigcup_{t^{\prime}\in N}B_{t^{\prime}},$ and
$C\coloneqq\bigcup_{t^{\prime}\in N}C_{t^{\prime}}.$ By Subsection 7.2 and
Subsection 7.2, we have

$\displaystyle{\sf hw}(G^{\mathsf{c}})$ $\displaystyle\leq$ $\displaystyle m.$
(22)

Clearly $G$ is a (spanning) subgraph of $G^{\mathsf{c}}.$ Instead of proving
${\sf bg}_{\Sigma}(G)\in\mathcal{O}_{h,c}(r^{96}),$ we will prove the stronger
statement ${\sf bg}_{\Sigma}(G^{\mathsf{c}})\in\mathcal{O}_{h,c}(r^{96}).$ For
this, we observe that $G^{\mathsf{c}}-(X\cup B)$ is a subgraph of
$G_{t}-X\in^{\eqref{ofkol_t89io}}\mathcal{E}_{\Sigma},$ therefore the stronger
statement will follow if we prove that ${\sf bg}(G^{\mathsf{c}},X\cup
B)\in\mathcal{O}_{h,c}(r^{96}).$

For this notice that Subsection 7.2 applies for $\Delta=4$,
$(T,\beta)=(\hat{T},\hat{\beta})$, and $l=(2m+1)^{2}\in\mathcal{O}(m^{2})$. As
$m\in\mathcal{O}_{h,c}(r^{2})$, Subsection 7.2 implies that ${\sf
bg}(G^{c},X\cup B)\in\mathcal{O}_{h,c}(r^{96})$. As we proved (14), this
completes the proof of the lemma. ∎

We are now in position to prove the lower bound in Theorem 1.2.

######  Corollary .

For every non-empty finite and closed set of surfaces $\mathbb{S},$
$\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf
bg}\preceq\mathbb{S}\mbox{-}\mathsf{{\sf tw}}.$

###### Proof.

Recall that, $\mathsf{sobs}(\\{\Sigma^{\varnothing}\\})=\\{\Sigma^{(0,0)}\\}$
and, by definition, $\\{\Sigma^{\varnothing}\\}\mbox{-}{\sf tw}\sim{\sf tw}$
and $\\{\Sigma^{(0,0)}\\}\mbox{-}{\sf bg}\sim{\sf bg}.$ Therefore, we may
examine the case where $\mathsf{sobs}(\mathbb{S})$ contains two surfaces
$\Sigma^{(h_{i},c_{i})},i\in[2],$ different from the sphere: one orientable
(assuming $h_{1}>0$ and $c_{1}=0$) and one non-orientable (assuming
$h_{1}>h_{2}\geq 0$ and $c_{2}>0$). Recall also that, by the definition of
$\mathbb{S}\mbox{-}\mathsf{{\sf tw}}$ in (6) and ${\sf tw}_{\Sigma}^{*}$ in
(12), it holds that for every graph $G,$

$\displaystyle\mathbb{S}\mbox{-}\mathsf{{\sf tw}}(G)$ $\displaystyle=$
$\displaystyle\min\\{{\sf tw}_{\Sigma}^{*}\mid\Sigma\in\mathbb{S}\\}.$ (23)

Let $G$ be a graph where $\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf bg}(G)\geq k.$
From the definition of $\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf bg}$ in (7),
this means that $G$ contains the graph
$\mathscr{D}_{k}^{\Sigma^{(h_{i},c_{i}})}$ as a minor for some $i\in[2].$
Notice that the fact that $\Sigma^{(h_{i},c_{i})}\in\mathsf{sobs}(\mathbb{S})$
implies that $\mathbb{S}\subseteq\mathbb{S}_{h_{i},c_{i}}$. Indeed,
$\mathbb{S}\subseteq\mathbb{S}_{h_{i},c_{i}}$ follows by Subsection 1.2 and
the definition of $\mathbb{S}_{h,c}$ (that is the set containing every surface
where it is not possible to embed all graphs in $\mathscr{D}^{(h,c)}$).

By Subsection 7.2, for every $\Sigma\in\mathbb{S}_{h,c}$ it holds that ${\sf
tw}_{\Sigma}^{*}(\mathscr{D}_{k}^{(h,c)})\in\Omega(k^{1/480}),$ therefore for
every $\Sigma\in\mathbb{S}$ it holds that ${\sf
tw}_{\Sigma}^{*}(\mathscr{D}_{k}^{(h,c)})\in\Omega_{c,h}(k^{1/480}),$ which,
by (23) and Section 7, implies that $\mathbb{S}\mbox{-}\mathsf{{\sf
tw}}(G)\in\Omega(k^{1/480})$ and we are done.∎

##  8 Putting everything together

We define a more refined version of ${\mathbb{S}}\mbox{-}\mathsf{{\sf hw}},$
namely ${\mathbb{S}}\mbox{-}\mathsf{\mathsf{rhw}},$ where:

> ${\mathbb{S}}\mbox{-}\mathsf{\mathsf{rhw}}(G)$ is the minimum $k$ for which
> $G$ has a tree-decomposition $(T,\beta)$ of adhesion at most $k$ such that
> for every $d\in V(T),$
>
>   * •
>
> either $|\beta(d)|\leq k,$ or
>
>   * •
>
> there exist a set $A_{d}\subseteq\beta(d)$ of size at most $k$ and a surface
> $\Sigma\in\mathbb{S}$ such that $\mathsf{Torso}_{G}(d)-A_{d}$ has a
> $\Sigma$-decomposition $\delta$ of width at most $k$ and breadth at most
> $k,$ and
>
> ${\blacktriangleright}$ given that $X_{d}$ is the collection of all
> vertices of $\mathsf{Torso}_{G}(d)-A_{d}$ which are drawn in a vortex of
> $\delta$ along with the vertices of $A_{d},$ then for every neighbor
> $d^{\prime}$ of $d$ in $T$ it holds that
>
>     * i.
>
> $|(\beta(d)\cap\beta(d^{\prime}))\setminus X_{d}|\leq 3$ and
>
>     * ii.
>
> $\mathsf{Torso}_{G}(d)-X_{d}$ is a minor of $G.$
>
>

Notice that the main difference of the above definition with the one of
$\mathbb{S}\mbox{-}{\sf hw}$ in (10) are the extra conditions i. and ii.
Condition i. says that the “surface part” of each adhesion should not have
more than 3 vertices and Condition ii. says that the “surface part” part of
each torso is a minor of the graph. We stress that these two conditions are
important for algorithmic applications of the MGST. Our next result implies
that no matter if we include or remove these two conditions, we define
asymptotically equivalent parameters.

We now give the following most extended version of Theorem 1.5.

######  Theorem 8.1.

For every finite and closed set of surfaces $\mathbb{S},$ it holds that the
parameters ${\mathbb{S}}\mbox{-}\mathsf{{\sf tw}},$
${\mathbb{S}}\mbox{-}\mathsf{{\sf hw}},$
${\mathbb{S}}\mbox{-}\mathsf{\mathsf{rhw}},$ and
${\mathsf{sobs}(\mathbb{S})}\mbox{-}{\sf bg}$ are asymptotically equivalent,
i.e., $\mathbb{S}\mbox{-}\mathsf{{\sf tw}}\sim{\mathbb{S}\mbox{-}\mathsf{{\sf
hw}}}\sim{\mathbb{S}}\mbox{-}\mathsf{\mathsf{rhw}}\sim{\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf
bg}}.$

###### Proof.

Recall that $\mathsf{sobs}(\emptyset)=\\{\Sigma^{\varnothing}\\}$ and, by
definition, all values of $\emptyset\mbox{-}\mathsf{{\sf tw}},$
$\emptyset\mbox{-}\mathsf{{\sf hw}},$
$\emptyset\mbox{-}\mathsf{\mathsf{rhw}},$ and
$\\{\Sigma^{\varnothing}\\}\mbox{-}{\sf bg}$ are equal to $\infty.$ Therefore,
we may assume that $\mathbb{S}$ is non-empty.

We prove (in order) ${\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf
bg}}\preceq\mathbb{S}\mbox{-}\mathsf{{\sf
tw}}\preceq\mathbb{S}\mbox{-}\mathsf{{\sf
hw}}\preceq\mathbb{S}\mbox{-}\mathsf{\mathsf{rhw}}\preceq{\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf
bg}}.$

_Proof of_ ${\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf
bg}}\preceq\mathbb{S}\mbox{-}\mathsf{{\sf tw}}.$ This is Subsection 7.2.

_Proof of_ $\mathbb{S}\mbox{-}\mathsf{{\sf
tw}}\preceq\mathbb{S}\mbox{-}\mathsf{\text{${\sf hw}$}}.$ This follows from
Subsection 6.2, the definition of ${\mathbb{S}}\mbox{-}{\sf tw}$ in (6), and
the definition of ${\mathbb{S}}\mbox{-}{\sf hw}$ in (10).

_Proof of_ $\mathbb{S}\mbox{-}\mathsf{{\sf
hw}}\preceq\mathbb{S}\mbox{-}\mathsf{\mathsf{rhw}}.$ This follows directly
because the definition of $\mathbb{S}\mbox{-}\mathsf{{\sf hw}}$ is the
definition of $\mathbb{S}\mbox{-}\mathsf{\mathsf{rhw}}$ without the additional
conditions i. and ii.

_Proof of_
$\mathbb{S}\mbox{-}\mathsf{\mathsf{rhw}}\preceq{\mathsf{sobs}(\mathbb{S})\mbox{-}{\sf
bg}}.$ This is Theorem 5.2. ∎

Let us now present the general statement of the main structural result of the
Graph Minors Series.

######  Proposition  (Graph Minors Structure Theorem [42, 32]).

There exists a function $f:\mathbb{N}\to\mathbb{N}$ such that for every graph
$G,$ if ${\sf hw}(G)\leq k,$ then $G$ has a tree-decomposition ${(T,\beta)}$
such that for all ${t\in V(T)},$ there exist a set $A_{t}\subseteq\beta(t)$ of
size at most $f(k)$ such that there exists a surface of Euler-genus at most
$f(k)$ and a $\Sigma$-decomposition $\delta$ of $\mathsf{Torso}_{G}(d)-A_{d}$
with breadth at most $f(k)$ and width at most $f(k).$

A more direct way to state the above theorem is to say that ${\sf
hw}^{\prime\prime}\preceq{\sf hw},$ where ${\sf hw}^{\prime\prime}$ is as
defined in (9) (Subsection 1.3).

Let us now finish this section by going back in the parameter ${\sf
hw}^{\prime}$ defined in the introduction ((2) in Subsection 1.1). Given
Section 8, it appears that Subsection 6.2 is the only essential ingredient for
proving the asymptotic equivalence of ${\sf hw}^{\prime}$ with the Hadwiger
number ${\sf hw}.$

######  Theorem 8.2.

${\sf hw}\sim{\sf hw}^{\prime}\sim{\sf hw}^{\prime\prime}.$

###### Proof.

As we already mentioned, ${\sf hw}^{\prime\prime}\preceq{\sf hw}$ is a
restatement of Section 8. The inequality ${\sf hw}^{\prime}\preceq{\sf
hw}^{\prime\prime}$ follows by seeing (using Subsection 6.2) the set $A_{d}$
along with the vertices of the vortices of $\delta$ as a low treewidth
modulator. Finally, ${\sf hw}\preceq{\sf hw}^{\prime}$ follows because, for
every $X\subseteq V(K_{k}),$ it holds that ${\sf
bg}(G,X)\geq\lfloor\sqrt{|X|}\rfloor\in\Omega(\sqrt{k})$ and that ${\sf
eg}(K_{k-|X|})\in\Omega(\sqrt{k-|X|}).$ ∎

##  9 Discussion and open problems

In this paper we defined a hierarchy of parameters that bijectively reflects
the containment-relation hierarchy of all two-dimensional surfaces without
boundaries. This permitted us to reveal the (asymptotic) structure of graphs
excluding graphs of bounded Euler-genus. Also, we introduced a compact way to
describe this structure using low-treewidth modulators.

Recall that the parameters we consider in this paper are defined via low-
treewidth modulators. What if we do not have any modulation at all? Such a
parameter would quantify the clique-sum closures of graphs that have either
bounded size or fixed Euler-genus. To derive a finite set of universal
obstructions for this is a interesting, however highly non-trivial, challenge.

#### Acknowledgements:

We are thankful to Laure Morelle, Christophe Paul, Evangelos Protopapas, and
Giannos Stamoulis, for their helpful comments on the containments and the
presentation of this paper.

## References

  * [1] Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos.  Faster parameterized algorithms for minor containment.  Theoretical Computer Science, 412(50):7018–7028, 2011.  doi:10.1016/j.tcs.2011.09.015.
  * [2] Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi.  Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1976–2004. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022.  doi:10.1137/1.9781611977073.79.
  * [3] Noga Alon, Paul Seymour, and Robin Thomas.  A separator theorem for nonplanar graphs.  J. Amer. Math. Soc., 3(4):801–808, 1990.  doi:10.2307/1990903.
  * [4] Hans L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.  doi:10.1137/S0097539793251219.
  * [5] Sergio Cabello and Bojan Mohar.  Finding shortest non-separating and non-contractible cycles for topologically embedded graphs.  Discrete Comput. Geom., 37(2):213–235, 2007.  doi:10.1007/s00454-006-1292-5.
  * [6] Julia Chuzhoy and Zihan Tan.  Towards tight(er) bounds for the excluded grid theorem.  J. Combin. Theory Ser. B, 146:219–265, 2021.  doi:10.1016/j.jctb.2020.09.010.
  * [7] Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos.  Bidimensional parameters and local treewidth.  SIAM J. Discrete Math., 18(3):501–511, 2004/05.  doi:10.1137/S0895480103433410.
  * [8] Erik D Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi.  Algorithmic graph minor theory: Decomposition, approximation, and coloring.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 637–646. IEEE, 2005.
  * [9] Erik D. Demaine and Mohammadtaghi Hajiaghayi.  Linearity of grid minors in treewidth with applications through bidimensionality.  Combinatorica, 28(1):19–36, 2008.  doi:10.1007/s00493-008-2140-4.
  * [10] Erik D. Demaine, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos.  The bidimensional theory of bounded-genus graphs.  SIAM J. Discrete Math., 20(2):357–371, 2006.  doi:10.1137/040616929.
  * [11] Reinhard Diestel.  Graph theory, volume 173 of Graduate Texts in Mathematics.  Springer, Berlin, fifth edition, 2017.  doi:10.1007/978-3-662-53622-3.
  * [12] Reinhard Diestel.  Abstract separation systems.  Order, 35(1):157–170, 2018.  doi:10.1007/s11083-017-9424-5.
  * [13] Reinhard Diestel, Joshua Erde, and Daniel Weiß auer.  Structural submodularity and tangles in abstract separation systems.  J. Combin. Theory Ser. A, 167:155–180, 2019.  doi:10.1016/j.jcta.2019.05.001.
  * [14] Reinhard Diestel and Jakob Kneip.  Profinite separation systems.  Order, 37(1):179–205, 2020.  doi:10.1007/s11083-019-09499-y.
  * [15] Reinhard Diestel and Sang-il Oum.  Tangle-tree duality: in graphs, matroids and beyond.  Combinatorica, 39(4):879–910, 2019.  doi:10.1007/s00493-019-3798-5.
  * [16] Walther Dyck.  Beiträge zur Analysis situs.  Math. Ann., 32(4):457–512, 1888.  doi:10.1007/BF01443580.
  * [17] Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon.  Measuring what matters: a hybrid approach to dynamic programming with treewidth.  J. Comput. System Sci., 121:57–75, 2021.  doi:10.1016/j.jcss.2021.04.005.
  * [18] Fedor V. Fomin, Petr Golovach, and Dimitrios M. Thilikos.  Contraction obstructions for treewidth.  J. Combin. Theory Ser. B, 101(5):302–314, 2011.  doi:10.1016/j.jctb.2011.02.008.
  * [19] Fedor V Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Hitting topological minors is FPT.  In ACM SIGACT Symposium on Theory of Computing (STOC), pages 1317–1326, 2020.  doi:10.1145/3357713.3384318.
  * [20] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi.  Hitting topological minors is FPT, 2020.  arXiv:1904.02944.
  * [21] George K. Francis and Jeffrey R. Weeks.  Conway’s ZIP proof.  Amer. Math. Monthly, 106(5):393–399, 1999.  doi:10.2307/2589143.
  * [22] Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch.  Finding a maximum-genus graph imbedding.  J. Assoc. Comput. Mach., 35(3):523–534, 1988.  doi:10.1145/44483.44485.
  * [23] Cyril Gavoille and Claire Hilaire.  Minor-universal graph for graphs on surfaces.  arXiv preprint arXiv:2305.06673, 2023.
  * [24] J. F. Geelen, R. B. Richter, and G. Salazar.  Embedding grids in surfaces.  European J. Combin., 25(6):785–792, 2004.  doi:10.1016/j.ejc.2003.07.007.
  * [25] Martin Grohe.  Quasi-4-connected components.  In 43rd International Colloquium on Automata, Languages, and Programming, volume 55 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 8, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016.
  * [26] Martin Grohe.  Tangled up in blue (A survey on connectivity, decompositions, and tangles).  CoRR, abs/1605.06704, 2016.  URL: http://arxiv.org/abs/1605.06704, arXiv:1605.06704.
  * [27] Bart M. P. Jansen, Jari J. H. de Kroon, and MichałWł odarczyk.  Vertex deletion parameterized by elimination distance and even less.  In STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1757–1769. ACM, New York, [2021] ©2021.  doi:10.1145/3406325.3451068.
  * [28] H. A. Jung.  Eine Verallgemeinerung des $n$-fachen Zusammenhangs für Graphen.  Math. Ann., 187:95–103, 1970.  doi:10.1007/BF01350174.