# Powers of planar graphs,
product structure, and blocking partitions111A preliminary version of this
paper appeared in the _Proceedings of the 12th European Conference on
Combinatorics, Graph Theory and Applications_ (EUROCOMB’23),
doi:10.5817/CZ.MUNI.EUROCOMB23-049.

Marc Distel 222School of Mathematics, Monash University, Melbourne, Australia
({marc.distel,robert.hickingbotham, david.wood}@monash.edu). Research of M.D.
and R.H. supported by Australian Government Research Training Program
Scholarships. Research of D.W. supported by the Australian Research Council.
Robert Hickingbotham 22footnotemark: 2
Michał T. Seweryn333 Computer Science Department, Université libre de
Bruxelles, Brussels, Belgium (michal.seweryn@ulb.be). Research of M.T.S.
supported by a PDR grant from the Belgian National Fund for Scientific
Research (FNRS). David R. Wood 22footnotemark: 2

###### Abstract

We prove that the $k$-power of any planar graph $G$ is contained in
$H\boxtimes P\boxtimes K_{\\_}{f(\Delta(G),k)}$ for some graph $H$ with
treewidth $15\,288\,899$, some path $P$, and some function $f$. This resolves
an open problem of Ossona de Mendez. In fact, we prove a more general result
in terms of shallow minors that implies similar results for many ‘beyond
planar’ graph classes, without dependence on $\Delta(G)$. For example, we
prove that every $k$-planar graph is contained in $H\boxtimes P\boxtimes
K_{\\_}{f(k)}$ for some graph $H$ with treewidth $15\,288\,899$ and some path
$P$, and some function $f$. This resolves an open problem of Dujmović, Morin
and Wood. We generalise all these results for graphs of bounded Euler genus,
still with an absolute bound on the treewidth.

At the heart of our proof is the following new concept of independent
interest. An _$\ell$ -blocking partition_ of a graph $G$ is a partition of
$V(G)$ into connected sets such that every path of length greater than $\ell$
in $G$ contains at least two vertices in one part. We prove that every graph
of Euler genus $g$ has a $894$-blocking partition with parts of size bounded
by a function of $\Delta(G)$ and $g$. Motivated by this result, we study
blocking partitions in their own right. We show that every graph has a
$2$-blocking partition with parts of size bounded by a function of $\Delta(G)$
and $\operatorname{tw}(G)$. On the other hand, we show that 4-regular graphs
do not have $\ell$-blocking partitions with bounded size parts.

##  1 Introduction

Graph product structure theory describes complicated graphs as subgraphs of
strong products111The _strong product_ of graphs $A$ and $B$, denoted by
_${A\boxtimes B}$_ , is the graph with vertex-set ${V(A)\times V(B)}$, where
distinct vertices ${(v,x),(w,y)\in V(A)\times V(B)}$ are adjacent if ${v=w}$
and ${xy\in E(B)}$, or ${x=y}$ and ${vw\in E(A)}$, or ${vw\in E(A)}$ and
${xy\in E(B)}$.  of simpler building blocks, which typically have bounded
treewidth222Let _$\operatorname{tw}(H)$_ denote the treewidth of a graph $H$
(defined in Section 2).. For example, Dujmović et al. [15] proved the
following product structure theorem for planar graphs, where a graph $H$ is
_contained_ in a graph $G$ if $H$ is isomorphic to a subgraph of $G$.

######  Theorem 1 ([15]).

Every planar graph is contained in $H\boxtimes P\boxtimes K_{\\_}3$ for some
planar graph $H$ with $\operatorname{tw}(H)\leqslant 3$ and for some path $P$.

This result has been the key to solving several long-standing open problems
about queue layouts [15], nonrepetitive colourings [13], centred colourings
[10], adjacency labelling [21, 12], twin-width [2, 29, 28], vertex ranking
[3], and box dimension [19]. Theorem 1 has been extended in various ways for
graphs of bounded Euler genus [15, 8, 29], graphs excluding an apex minor [15,
27, 14], graphs excluding an arbitrary minor [15, 27, 4], graphs of bounded
tree-width [4, 14], graphs of bounded path-width [18], and for various non-
minor-closed classes [17, 25].

Many of these results show that for a particular graph class $\mathcal{G}$
there are integers $t,c$ such that every graph in $\mathcal{G}$ is contained
in $H\boxtimes P\boxtimes K_{\\_}c$ for some graph $H$ with treewidth $t$ and
for some path $P$. Here the primary goal is to minimise $t$, where minimising
$c$ is a secondary goal. This paper proves product structure theorems of this
form for powers of planar graphs and for various beyond planar graph classes.
The distinguishing feature of our results is that $\operatorname{tw}(H)$ is
bounded by an absolute constant, instead of depending on a parameter defining
$\mathcal{G}$. This is important because in several applications of such
product structure theorems, the main dependency is on $\operatorname{tw}(H)$;
see Section 1.3 for an example.

First consider powers of planar graphs. For $k\in\mathbb{N}$, the _$k$ -power_
of a graph $G$, denoted _$G^{k}$_ , is the graph with vertex-set $V(G)$, where
$vw\in E(G^{k})$ if and only if
$\operatorname{dist}_{\\_}G(v,w)\in\\{1,\dots,k\\}$. Dujmović et al. [17]
proved that for every planar graph $G$ of maximum degree $\Delta$, the
$k$-power $G^{k}$ is contained in $H\boxtimes P\boxtimes
K_{\\_}{6\Delta^{k}(k^{4}+3k^{2})}$ for some graph $H$ with
$\operatorname{tw}(H)\leqslant\binom{k+3}{3}-1$ and some path $P$. Dependence
on $\Delta$ is unavoidable since, for example, if $G$ is the complete
$(\Delta-1)$-ary tree of height $k$, then $G^{2k}$ is a complete graph on
roughly $(\Delta-1)^{k}$ vertices. Ossona de Mendez [33] asked whether this
bound on $\operatorname{tw}(H)$ could be made independent of $k$. In
particular:

######  Question 2 ([33]).

Is there a constant $t$ and a function $f$ such that for every planar graph
$G$ and $k\in\mathbb{N}$, the $k$-power $G^{k}$ is contained in $H\boxtimes
P\boxtimes K_{\\_}{f(k,\Delta(G))}$ for some graph $H$ with
$\operatorname{tw}(H)\leqslant t$ and for some path $P$?

We resolve this question, in the following strong sense. For integers
$k,d\geqslant 1$ and a graph $G$, let _$G^{k}_{\\_}d$_ be the graph with
vertex-set $V(G)$ where $vw\in E(G^{k}_{\\_}d)$ whenever there is a $vw$-path
$P$ in $G$ of length at most $k$ such that every internal vertex of $P$ has
degree at most $d$ in $G$. The following theorem answers 2 in the affirmative
since $G^{k}=G^{k}_{\\_}{\Delta(G)}$.

######  Theorem 3.

There is a function $f$ such that for every planar graph $G$ and for any
integers $k,d\geqslant 1$, the graph $G^{k}_{\\_}d$ is contained in
$H\boxtimes P\boxtimes K_{\\_}{f(k,d)}$ for some graph $H$ with
$\operatorname{tw}(H)\leqslant 15\,288\,899$ and for some path $P$.

We chose to simplify the proof instead of optimising the constant upper bound
on $\operatorname{tw}(H)$ in Theorem 3 and in our other results.

Theorem 3 is in fact a corollary of a more general result expressed in terms
of shallow minors.

###  1.1 Shallow Minors and Beyond Planar Graphs

Let $G$ and $H$ be graphs and let $r,s\geqslant 0$ be integers. $H$ is a
_minor_ of $G$ if a graph isomorphic to $H$ can be obtained from $G$ by vertex
deletion, edge deletion, and edge contraction. A class $\mathcal{G}$ of graphs
is _minor-closed_ if for every $G\in\mathcal{G}$ every minor of $G$ is in
$\mathcal{G}$. A _model_ $(B_{\\_}x\colon x\in V(H))$ of $H$ in $G$ is a
collection of vertex-disjoint connected subgraphs in $G$ such that $B_{\\_}x$
and $B_{\\_}y$ are adjacent in $G$ for every edge $xy\in E(H)$. Clearly $H$ is
a minor of $G$ if and only if $G$ contains a model of $H$. If there exists a
model of $H$ in $G$ such that $B_{\\_}x$ has radius at most $r$ for all $x\in
V(H)$, then $H$ is an _$r$ -shallow minor_ of $G$. A _rooted model_
$((B_{\\_}x,v_{\\_}x)\colon x\in V(H))$ of $H$ is a model of $H$ where each
$B_{\\_}x$ has a corresponding root $v_{\\_}x\in V(B_{\\_}x)$. If for every
$x\in V(H)$ and for every $u\in V(B_{\\_}x)\setminus\\{v_{\\_}x\\}$, we have
$\operatorname{dist}_{\\_}{B_{\\_}x}(v_{\\_}x,u)\leqslant r$ and
$\deg_{\\_}{B_{\\_}x}(u)\leqslant s$, then $((B_{\\_}x,v_{\\_}x)\colon x\in
V(H))$ is an _$(r,s)$ -shallow model_ and $H$ is an _$(r,s)$ -shallow minor_
of $G$. Clearly, if $H$ is an $r$-shallow minor of $G$, then $H$ is an
$(r,\Delta(G))$-shallow minor of $G$. However, these definitions do not assume
$\Delta(G)$ is bounded, since each vertex $v_{\\_}x$ may have unbounded degree
in $B_{\\_}x$ and each vertex $u\in V(B_{\\_}x)$ may have unbounded degree in
$G$.

Building on the work of Dujmović et al. [17], Hickingbotham and Wood [25]
showed that shallow minors inherit product structure.

######  Theorem 4 ([25]).

If a graph $G$ is an $r$-shallow minor of $H\boxtimes P\boxtimes K_{\\_}c$
where $\operatorname{tw}(H)\leqslant t$, then $G$ is contained in $J\boxtimes
P\boxtimes K_{\\_}{c(2r+1)^{2}}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant\binom{2r+1+t}{t}-1$.

Our main contribution is the following product structure theorem for
$(r,s)$-shallow minors of planar graphs, where $J$ has treewidth bounded by an
absolute constant.

######  Theorem 5.

There is a function $f$ such that for every planar graph $G$ and for every
$(r,s)$-shallow minor $H$ of $G\boxtimes K_{\\_}{d}$, $H$ is contained in
$J\boxtimes P\boxtimes K_{\\_}{f(d,r,s)}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant 15\,288\,899$ and for some path $P$.

Theorem 5 is useful since, as observed by Hickingbotham and Wood [25], many
non-minor-closed graph classes can be described as shallow minors of a strong
product of a planar graph with a small complete graph. For example, for any
graph $G$ with maximum degree $\Delta$, Hickingbotham and Wood [25] observed
that $G^{k}$ is a $\lfloor\tfrac{k}{2}\rfloor$-shallow minor of $G\boxtimes
K_{\\_}{\Delta^{\lfloor k/2\rfloor+1}}$. The proof is readily adapted333Let
$D$ be the set of vertices with degree at most $d$ in $G$. For each vertex
$v\in V(G)$, let $B_{\\_}v^{\prime}$ be the subgraph of $G$ induced by the set
of vertices $x\in V(G)$ for which there is a $vx$-path $P$ in $G$ of length at
most $\lfloor\frac{k}{2}\rfloor$ such that $V(P-v)\subseteq D$. So the radius
of $B_{\\_}v^{\prime}$ is at most $\lfloor\frac{k}{2}\rfloor$ and there is an
edge between $V(B_{\\_}u^{\prime})$ and $V(B_{\\_}v^{\prime})$ in $G$ for each
$uv\in E(G^{k})$. Furthermore, $|\\{v\in V(G)\colon x\in
V(B_{\\_}v^{\prime})\\}|\leqslant d^{0}+\cdots+d^{\lfloor k/2\rfloor}\leqslant
d^{\lfloor k/2\rfloor+1}$ for each $x\in V(G)$. So an arbitrary injective map
from $\\{v\in V(G)\colon x\in V(B_{\\_}v^{\prime})\\}$ to
$V(K_{\\_}{d^{\lfloor k/2\rfloor+1}})$ for each vertex $x\in V(G)$ defines a
subgraph $B_{\\_}v$ of $G\boxtimes K_{\\_}{d^{\lfloor k/2\rfloor+1}}$ such
that the projection of $B_{\\_}v$ onto $G$ is $B_{\\_}v^{\prime}$ and
$V(B_{\\_}v)\cap V(B_{\\_}u)=\varnothing$ for all distinct $u,v\in V(G)$. So
$(B_{\\_}v\colon v\in V(G^{k}_{\\_}d))$ defines a model of $G^{k}_{\\_}d$ in
$G\boxtimes K_{\\_}{d^{\lfloor k/2\rfloor}+1}$ where each $B_{\\_}v$ has
radius at most $\lfloor\frac{k}{2}\rfloor$, as required. By construction,
$G^{k}_{\\_}d$ is in fact a $(\lfloor\frac{k}{2}\rfloor,d)$-shallow minor of
$G\boxtimes K_{\\_}{d^{\lfloor k/2\rfloor+1}}$. to show that $G^{k}_{\\_}d$ is
a $(\lfloor\tfrac{k}{2}\rfloor,d)$-shallow minor of $G\boxtimes
K_{\\_}{d^{\lfloor k/2\rfloor+1}}$. Thus Theorem 5 implies Theorem 3.

Theorem 5 can also be applied to several well-studied beyond planar graph
classes, which we now introduce. See [5, 26] for surveys on beyond planarity.

A graph $G$ is _$k$ -planar_ if $G$ has a drawing in the plane in which each
edge is involved in at most $k$ crossings, where no three edges cross at a
single point; such graphs are widely studied, see [34, 17, 11, 16] for
example. Dujmović et al. [17] proved that every $k$-planar graph is contained
in $H\boxtimes P\boxtimes K_{\\_}{18k^{2}+48k+30}$ for some graph $H$ of
treewidth $\binom{k+4}{3}-1$ and for some path $P$. Dujmović et al. [17] asked
whether this bound on $\operatorname{tw}(H)$ could be made independent of $k$.
In particular:

######  Question 6 ([17]).

Is there a constant $t$ and a function $f$ such that every $k$-planar graph
$G$ is contained in $H\boxtimes P\boxtimes K_{\\_}{f(k)}$ for some graph $H$
with $\operatorname{tw}(H)\leqslant t$?

Theorem 5 resolves this question.

######  Corollary 7.

There is a function $f$ such that every $k$-planar graph $G$ is contained in
$H\boxtimes P\boxtimes K_{\\_}{f(k)}$ for some graph $H$ with
$\operatorname{tw}(H)\leqslant 15\,288\,899$.

###### Proof.

Hickingbotham and Wood [25] observed that $G$ is a
$\lceil\tfrac{k}{2}\rceil$-shallow minor of $H\boxtimes K_{\\_}2$, where $H$
is the planar graph obtained from $G$ by adding a dummy vertex at each
crossing point. A close inspection of their proof reveals that each branch set
in the model of $G$ in $H\boxtimes K_{\\_}2$ is a subdivided star rooted at
the high degree vertex. So $G$ is a $(\lceil\tfrac{k}{2}\rceil,2)$-shallow
minor of $H\boxtimes K_{\\_}2$. The claim then follows from Theorem 5. ∎

A _string graph_ is the intersection graph of a set of curves in the plane
with no three curves meeting at a single point. Such graphs are widely
studied; see [22, 30, 35, 38, 23] for example. For an integer $\delta\geqslant
1$, if each curve is involved in at most $\delta$ intersections with other
curves, then the corresponding string graph is called a _$\delta$ -string
graph_.

######  Corollary 8.

There is a function $f$ such that every $\delta$-string graph $G$ is contained
in $J\boxtimes P\boxtimes K_{\\_}{f(\delta)}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant 15\,288\,899$ and for some path $P$.

###### Proof.

Hickingbotham and Wood [25] observed that $G$ is a
$\lfloor\frac{\delta}{2}\rfloor$-shallow minor of $H\boxtimes K_{\\_}2$, where
$H$ is the planar graph obtained by adding a dummy vertex at each intersection
point of two curves (and possibly adding isolated vertices). A close
inspection of their proof reveals that each branch set of the model of $G$ in
$H\boxtimes K_{\\_}2$ is a path. So $G$ is a
$(\lfloor\frac{\delta}{2}\rfloor,2)$-shallow minor of $H\boxtimes K_{\\_}2$.
The claim then follows from Theorem 5. ∎

The following graph class was introduced by Angelini et al. [1]. A _fan-
bundling_ of a graph $G$ is an indexed set
$\mathcal{E}=(\mathcal{E}_{\\_}v:v\in V(G))$ where $\mathcal{E}_{\\_}v$ is a
partition of the set of edges in $G$ incident to $v$. Each element of
$\mathcal{E}_{\\_}v$ is called a _fan-bundle_. For a fan-bundling
$\mathcal{E}$ of $G$, let $G_{\\_}\mathcal{E}$ be the graph whose vertices are
the vertices of $G$ and the bundles of $\mathcal{E}$, where $vB$ is an edge of
$G_{\\_}\mathcal{E}$ whenever $v\in V(G)$ and $B\in\mathcal{E}_{\\_}v$, and
$B_{\\_}1B_{\\_}2$ is an edge of $G_{\\_}\mathcal{E}$ whenever $vw\in E(G)$
and $vw\in B_{\\_}1\in\mathcal{E}_{\\_}v$ and $vw\in
B_{\\_}2\in\mathcal{E}_{\\_}w$. A graph $G$ is _$k$ -fan-bundle planar_ if for
some fan-bundling $\mathcal{E}$ of $G$, the graph $G_{\\_}\mathcal{E}$ has a
drawing in the plane such that each edge $B_{\\_}1B_{\\_}2\in
E(G_{\\_}\mathcal{E})$ is in no crossings, and each edge $vB\in
E(G_{\\_}\mathcal{E})$ is in at most $k$ crossings.

######  Corollary 9.

There is a function $f$ such that every $k$-fan-bundle planar graph $G$ is
contained in $J\boxtimes P\boxtimes K_{\\_}{f(k)}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant 15\,288\,899$ and for some path $P$.

###### Proof.

Hickingbotham and Wood [25] showed that $G$ is a $(k+1)$-shallow minor of
$H\boxtimes K_{\\_}2$ for some planar graph $H$. A close inspection of their
proof reveals that each branch set of the model of $G$ in $H\boxtimes
K_{\\_}2$ is a rooted subdivided star. So $G$ is a $(k+1,2)$-shallow minor of
$H\boxtimes K_{\\_}2$. The claim then follows from Theorem 5. ∎

###  1.2 Other Surfaces

We generalise all of the above results for graphs embeddable on any fixed
surface as follows. The _Euler genus_ of a surface with $h$ handles and $c$
cross-caps is ${2h+c}$. The _Euler genus_ of a graph $G$ is the minimum
integer $g\geqslant 0$ such that there is an embedding of $G$ in a surface of
Euler genus $g$; see [31] for background about graph embeddings in surfaces.
Theorem 5 generalises as follows.

######  Theorem 10.

There is a function $f$ such that for every graph $G$ of Euler genus $g$,
every $(r,s)$-shallow minor $H$ of $G\boxtimes K_{\\_}{d}$ is contained in
$J\boxtimes P\boxtimes K_{\\_}{f(d,r,s,g)}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant 963\,922\,179$.

Theorem 3 generalises as follows. The proof is directly analogous to the proof
of Theorem 3, using Theorem 10 instead of Theorem 5.

######  Corollary 11.

There is a function $f$ such that for every graph $G$ of Euler genus $g$ and
for any integers $k,d\geqslant 1$, the graph $G^{k}_{\\_}d$ is contained in
$H\boxtimes P\boxtimes K_{\\_}{f(d,g,k)}$ for some graph $H$ with
$\operatorname{tw}(H)\leqslant 963\,922\,179$ and for some path $P$.

We generalise Corollary 7 as follows, where a graph $G$ is _$(g,k)$ -planar_
if $G$ has a drawing in a surface of Euler genus $g$ in which each edge is
involved in at most $k$ crossings, where no three edges cross at a single
point. Such graphs are widely studied [24, 11, 16, 17]. Dujmović et al. [17]
proved that every $(g,k)$-planar graph is contained in $H\boxtimes P\boxtimes
K_{\\_}{\max\\{2g,3\\}(6k^{2}+16k+10)}$, for some graph $H$ of treewidth
$\binom{k+4}{3}-1$ and for some path $P$. We improve the treewidth bound to an
absolute constant. The proof is directly analogous to the proof of Corollary
7.

######  Corollary 12.

There is a function $f$ such that every $(g,k)$-planar graph $G$ is contained
in $H\boxtimes P\boxtimes K_{\\_}{f(g,k)}$ for some graph $H$ with
$\operatorname{tw}(H)\leqslant 963\,922\,179$.

We generalise Corollary 8 as follows, where a _( $g,\delta)$-string graph_ is
the intersection graph of a set of curves in a surface of Euler genus $g$,
such that no three curves meet at a single point, and each curve is involved
in at most $\delta$ intersections with other curves. The proof of Corollary 13
is directly analogous to the proof of Corollary 8.

######  Corollary 13.

There is a function $f$ such that every $(g,\delta)$-string graph $G$ is
contained in $J\boxtimes P\boxtimes K_{\\_}{f(\delta)}$ for some graph $J$
with $\operatorname{tw}(J)\leqslant 963\,922\,179$ and for some path $P$.

We generalise Corollary 9 as follows, where a graph $G$ is _$(g,k)$ -fan-
bundle planar_ if for some fan-bundling $\mathcal{E}$ of $G$, the graph
$G_{\\_}\mathcal{E}$ has a drawing in a surface of Euler genus $g$ such that
each edge $B_{\\_}1B_{\\_}2\in E(G_{\\_}\mathcal{E})$ is in no crossings, and
each edge $vB\in E(G_{\\_}\mathcal{E})$ is in at most $k$ crossings. The proof
of Corollary 14 is directly analogous to the proof of Corollary 9.

######  Corollary 14.

There is a function $f$ such that every $(g,k)$-fan-bundle planar graph $G$ is
contained in $J\boxtimes P\boxtimes K_{\\_}{f(k)}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant 963\,922\,179$ and for some path $P$.

###  1.3 Application: Centred Colourings

Nešetřil and Ossona De Mendez [32] introduced the following definition. For an
integer $p\geqslant 1$, a vertex colouring $\phi$ of a graph $G$ is _$p$
-centred _if, for every connected subgraph $X\subseteq G$, $|\\{\phi(v):v\in
V(X)\\}|>p$ or there exists some $v\in V(X)$ such that $\phi(v)\neq\phi(w)$
for every $w\in V(X)\setminus\\{v\\}$. For an integer $p\geqslant 1$, the _$p$
-centred chromatic number_ of a graph $G$, denoted by $\chi_{\\_}p(G)$, is the
minimum integer $c\geqslant 0$ such that $G$ has a $p$-centred $c$-colouring.
Centred colourings are important within graph sparsity theory as they
characterise graph classes with bounded expansion [32].

Dębski et al. [10] established that $\chi_{\\_}p(G\boxtimes
H)\leqslant\chi_{\\_}p(G)\chi(H^{p})$ for all graphs $G$ and $H$. Pilipczuk
and Siebertz [36, Lemma 15] showed that
$\chi_{\\_}p(G)\leqslant\binom{p+t}{t}$ for every graph $G$ with treewidth at
most $t$. It follows that if $G\subseteq H\boxtimes P\boxtimes K_{\\_}{\ell}$
and $\operatorname{tw}(H)\leqslant t$, then

$\chi_{\\_}p(G)\leqslant\ell(p+1)\chi_{\\_}p(H)\leqslant\ell(p+1)\tbinom{p+t}{t}\in
O_{\\_}\ell(p^{t+1}).$ (1)

Thus, Theorems 3, 7 and 9 imply:

  * •

for every planar graph $G$ and any integers $k,d\geqslant 1$,
$\chi_{\\_}p(G^{k}_{\\_}d)\in O_{\\_}{k,d}(p^{15\,288\,900})$;

  * •

for every $k$-planar graph $G$, $\chi_{\\_}p(G)\in
O_{\\_}k(p^{15\,288\,900})$;

  * •

for every $k$-fan-bundle graph $G$, $\chi_{\\_}p(G)\in
O_{\\_}k(p^{15\,288\,900})$.

Similarly, Corollaries 11, 12 and 14 imply:

  * •

for every graph $G$ of Euler genus $g$ and for any integers $k,d\geqslant 1$,
$\chi_{\\_}p(G^{k}_{\\_}d)\in O_{\\_}{g,k,d}(p^{963\,922\,180})$;

  * •

for every $(g,k)$-planar graph $G$, $\chi_{\\_}p(G)\in
O_{\\_}{g,k}(p^{963\,922\,180})$;

  * •

for every $(g,k)$-fan-bundle graph $G$, $\chi_{\\_}p(G)\in
O_{\\_}{g,k}(p^{963\,922\,180})$.

For $k$-planar or $(g,k)$-planar graphs $G$, the best previously known bound
was $\chi_{\\_}p(G)\in O_{\\_}{g,k}(p^{\binom{k+4}{3}})$, due to Dujmović et
al. [17]. The above results significantly improve this bound (for large $k$).

###  1.4 Paper Outline

It remains to prove Theorems 5 and 10. The proofs of these results depend on
the notion of a ‘blocking partition’, which we believe is of independent
interest. Following a section of preliminary definitions, Section 3 introduces
and states our main results about blocking partitions: Theorem 16 for planar
graphs and Theorem 17 for graphs of Euler genus $g$. We then show how Theorems
16 and 17 imply Theorems 5 and 10. Theorem 16 is the heart of the paper, and
is proved in Sections 4, 5 and 6. Theorem 17 is then proved in Section 7 as a
corollary of Theorem 16. Section 8 considers which graph classes admit
blocking partitions of bounded width. We show that bounded maximum degree is
necessary but not sufficient, and that bounded maximum degree and bounded
treewidth are sufficient. Section 9 concludes by introducing some natural open
problems that arise from this work.

##  2 Preliminaries

We consider simple, finite, undirected graphs $G$ with vertex-set ${V(G)}$ and
edge-set ${E(G)}$. See [6] for graph-theoretic definitions not given here. Let
${\mathbb{N}\coloneqq\\{1,2,\dots\\}}$ and
${\mathbb{N}_{\\_}0\coloneqq\\{0,1,\dots\\}}$. A _graph class_ is a collection
of graphs closed under isomorphism.

We use the following notation for a graph $G$. For $v\in V(G)$, let
${\color[rgb]{.5,0,0}N_{\\_}G(v)}:=\\{w\in V(G):vw\in E(G)\\}$ and
${\color[rgb]{.5,0,0}N_{\\_}G[v]}:=N_{\\_}G(v)\cup\\{v\\}$. For $S\subseteq
V(G)$, let ${\color[rgb]{.5,0,0}N_{\\_}G(S)}:=\bigcup_{\\_}{v\in
S}N_{\\_}G(v)\setminus S$.

The _length_ of a path $P$ is the number of edges in $P$. Given a graph $G$
and two subsets $A,B\subseteq V(G)$, a path $P$ in $G$ is an _$A$ –$B$ path_
if either $P$ consists of only one vertex $x\in A\cap B$, or $P$ has length at
least $1$, one end of $P$ belongs to $A$, the other belongs to $B$, and no
inner vertex belongs to $A\cup B$. For vertices $x,y\in V(G)$, an _$x$ –$y$
path_ is an $\\{x\\}$–$\\{y\\}$ path. For a tree $T$ and $x,y\in V(T)$, we
denote the unique $x$–$y$ path in $T$ by $xTy$.

For two subsets $U_{\\_}1,U_{\\_}2\subseteq V(G)$, let
_$\operatorname{dist}_{\\_}G(U_{\\_}1,U_{\\_}2)$_ denote the _distance_
between $U_{\\_}1$ and $U_{\\_}2$ in $G$; that is, the length of a shortest
$U_{\\_}1$–$U_{\\_}2$ path in $G$ (or $+\infty$ if no such path exists). In
this notation, the role of $U_{\\_}i$ can be played by a vertex $x$, which is
then interpreted as the singleton $\\{x\\}$; for example, we write
$\operatorname{dist}_{\\_}G(x,U)$ rather than
$\operatorname{dist}_{\\_}G(\\{x\\},U)$. Similarly, the role of $U_{\\_}i$ can
be played by an edge $x_{\\_}1x_{\\_}2\in E(G)$, which is then interpreted as
the set $\\{x_{\\_}1,x_{\\_}2\\}$, or by a set of edges $M\subseteq E(G)$
which is interpreted as $\bigcup_{\\_}{xy\in M}\\{x,y\\}$. A path $P$ in a
graph $G$ is _geodesic_ if it is a shortest path between its ends in $G$,
which implies
$\operatorname{dist}_{\\_}P(x,y)=\operatorname{dist}_{\\_}G(x,y)$ for any
$x,y\in V(P)$.

In a plane embedding of a graph $G$, a _face_ is a connected component of
$\mathbb{R}^{2}-G$. We use _closure_ and _boundary_ in the topological sense.
So the closure of a face $f$ is the union of $f$ and the boundary of $f$.

A _tree-decomposition_ of a graph $G$ is a collection
${\mathcal{W}=(W_{\\_}x\colon x\in V(T))}$ of subsets of ${V(G)}$ indexed by
the nodes of a tree $T$ such that (a) for every edge ${vw\in E(G)}$, there
exists a node ${x\in V(T)}$ with ${v,w\in W_{\\_}x}$; and (b) for every vertex
${v\in V(G)}$, the set ${\\{x\in V(T)\colon v\in W_{\\_}x\\}}$ induces a non-
empty (connected) subtree of $T$. Each set $W_{\\_}x$ in $\mathcal{W}$ is
called a _bag_. The _width_ of $\mathcal{W}$ is ${\max\\{\lvert
W_{\\_}x\rvert\colon x\in V(T)\\}-1}$. The _treewidth $\operatorname{tw}(G)$_
of a graph $G$ is the minimum width of a tree-decomposition of $G$. Treewidth
is the standard measure of how similar a graph is to a tree. Indeed, a
connected graph has treewidth at most 1 if and only if it is a tree.

Let $G$ and $H$ be graphs. A _partition_ of $G$ is a collection $\mathcal{P}$
of sets of vertices in $G$ such that each vertex of $G$ is in exactly one
element of $\mathcal{P}$. Each element of $\mathcal{P}$ is called a _part_.
Empty parts are allowed. The _width_ of $\mathcal{P}$ is the maximum number of
vertices in a part. The _quotient_ of $\mathcal{P}$ (with respect to $G$) is
the graph, denoted by _$G/\mathcal{P}$_ , whose vertices are the non-empty
parts of $\mathcal{P}$, where distinct non-empty parts $A,B\in\mathcal{P}$ are
adjacent in $G/\mathcal{P}$ if and only if some vertex in $A$ is adjacent in
$G$ to some vertex in $B$. The quotient is defined analogously when
$\mathcal{P}$ is a set of vertex-disjoint subgraphs of $G$ whose vertex-sets
partition $G$. Then the vertices of $G/\mathcal{P}$ are subgraphs of $G$
instead of sets of vertices. An _$H$ -partition_ of $G$ is a partition
$\mathcal{P}$ of $G$ such that $G/\mathcal{P}$ is contained in $H$. The
following observation connects partitions and products.

######  Observation 15 ([15]).

For all graphs $G$ and $H$ and any integer $p\geqslant 1$, $G$ is contained in
$H\boxtimes K_{\\_}p$ if and only if $G$ has an $H$-partition with width at
most $p$.

A partition of a graph $G$ is _connected_ if the subgraph induced by each part
is connected. In this case, the quotient is the minor of $G$ obtained by
contracting each part into a single vertex.

A partition $\mathcal{P}$ of $G$ is _chordal_ if $\mathcal{P}$ is connected
and $G/\mathcal{P}$ is _chordal_.

A _tree-partition_ is a $T$-partition for some tree $T$. Such a $T$-partition
is _rooted_ if $T$ is rooted.

Let $G$ and $H$ be graphs and let $Z$ be a subgraph of $G\boxtimes H$. The
_projection_ of $Z$ onto $G$ is the subgraph $Z^{\prime}$ of $G$ where
$V(Z^{\prime}):=\\{v\in V(G)\colon\text{$(v,x)\in V(Z)$ for some $x\in
V(H)$}\\}$ and $E(Z^{\prime}):=\\{uv\in E(G)\colon\text{$(u,x)(v,y)\in E(Z)$
for some $x,y\in V(H)$}\\}$.

A _bfs -layering_ of a connected graph $G$ is an ordered partition
$(V_{\\_}0,V_{\\_}1,\dots)$ of $V(G)$ where $V_{\\_}0=\\{r\\}$ for some vertex
$r\in V(G)$ and $V_{\\_}i=\\{v\in V(G):\operatorname{dist}_{\\_}G(v,r)=i\\}$
for each $i\geqslant 1$. A path $P$ is _vertical_ with respect to
$(V_{\\_}0,V_{\\_}1,\dots)$ if $|V(P)\cap V_{\\_}i|\leqslant 1$ for all
$i\geqslant 0$. Let $T$ be a spanning tree of $G$, where for each non-root
vertex $v\in V_{\\_}i$ there is a unique edge $vw$ in $T$ for some $w\in
V_{\\_}{i-1}$. Then $T$ is called a _bfs -spanning tree_ of $G$.

##  3 Blocking Partitions

Let $G$ be a graph and $\mathcal{R}$ be a connected partition of $V(G)$. A
path $P$ in $G$ is _$\mathcal{R}$ -clean_ if $|V(P)\cap V|\leqslant 1$ for
each part $V\in\mathcal{R}$. We say that $\mathcal{R}$ is _$\ell$ -blocking_
if every $\mathcal{R}$-clean path in $G$ has length at most $\ell$, as
illustrated in Figure 1.

Figure 1: A $3$-blocking partition $\mathcal{R}$ of width $9$. The red path is
a longest $\mathcal{R}$-clean path.

The following result is the heart of this paper.

######  Theorem 16.

Every planar graph $G$ with maximum degree $\Delta$ has a $222$-blocking
partition $\mathcal{R}$ with width at most
$f(\Delta):=10\Delta^{80}(3612\,\Delta^{452}+900)$.

Theorem 16 is proved in Sections 4, 5 and 6. Section 7 proves the following
extension of Theorem 16.

######  Theorem 17.

Every graph $G$ with Euler genus $g$ and maximum degree $\Delta$ has a
$894$-blocking partition with width at most
$f(\Delta,g):=\max\\{10\Delta^{80}(3612\Delta^{452}+900),8950g^{2}+1796g\\}$.

To show that Theorems 16 and 17 imply our main results (Theorems 5 and 10), we
use the following lemma.

######  Lemma 18.

Let $\mathcal{G}$ be a minor-closed class such that for some function $f$ and
integers $\ell,t,c\geqslant 1$,

  * •

every graph $G\in\mathcal{G}$ has an $\ell$-blocking partition $\mathcal{R}$
with width at most $f(\Delta(G))$;

  * •

every graph $G\in\mathcal{G}$ is contained in $H\boxtimes P\boxtimes K_{\\_}c$
for some graph $H$ with $\operatorname{tw}(H)\leqslant t$ and for some path
$P$.

Then there is a function $g$ such that for any integers $r\geqslant 0$ and
$d,s\geqslant 1$, for every graph $G\in\mathcal{G}$, every $(r,s)$-shallow
minor of $G\boxtimes K_{\\_}{d}$ is contained in $J\boxtimes P\boxtimes
K_{\\_}{g(d,r,s,\ell,c)}$ for some graph $J$ with
$\operatorname{tw}(J)\leqslant\binom{2\ell+5+t}{t}-1$ and for some path $P$.

For planar graphs, Lemma 18 is applicable with $\ell=222$ by Theorem 16 and
with $t=c=3$ by Theorem 1. Lemma 18 thus proves Theorem 5 since
$\operatorname{tw}(J)\leqslant\binom{2\ell+5+t}{t}-1=\binom{2\cdot
222+5+3}{3}-1=15\,288\,899$. For graphs of Euler genus $g$, Lemma 18 is
applicable with $\ell=894$ by Theorem 17 and with $t=3$ and $c=\max\\{2g,3\\}$
by a result of Distel et al. [8]. Lemma 18 thus proves Theorem 10 since
$\operatorname{tw}(J)\leqslant\binom{2\ell+5+t}{t}-1=\binom{2\cdot
894+5+3}{3}-1=963\,922\,179$.

We now work towards proving Lemma 18.

######  Lemma 19.

Let $\mathcal{G}$ be a minor-closed class such that, for some function $f$ and
integer $\ell\geqslant 1$, every graph $G\in\mathcal{G}$ has an
$\ell$-blocking partition $\mathcal{R}$ with width at most $f(\Delta(G))$.
Then for any integers $r>\ell+2$ and $s,d\geqslant 1$, for every graph
$G\in\mathcal{G}$, every $(r,s)$-shallow minor $H$ of $G\boxtimes K_{\\_}d$ is
an $(r-1,s^{\prime})$-shallow minor of $G^{\prime}\boxtimes
K_{\\_}{d^{\prime}}$, where $G^{\prime}$ is a minor of $G$ and is thus in
$\mathcal{G}$, and $s^{\prime}=(ds)^{r}$ and $d^{\prime}=d\cdot f(ds)$.

###### Proof.

Let $((B_{\\_}x,v_{\\_}x)\colon x\in V(H))$ be an $(r,s)$-shallow model of $H$
in $G\boxtimes K_{\\_}d$. For each $x\in V(H)$, let $B_{\\_}x^{\prime}$ and
$v_{\\_}x^{\prime}$ be the projections of $B_{\\_}x$ and $v_{\\_}x$,
respectively, onto $G$. Observe that for each $x\in V(H)$, the maximum degree
of each $B_{\\_}x-v_{\\_}x$ is at most $s$ and each vertex in
$B_{\\_}x^{\prime}$ is at distance at most $r$ from $v_{\\_}x^{\prime}$. Let
$G_{\\_}0:=\bigcup(B_{\\_}x^{\prime}-v_{\\_}x^{\prime}:x\in V(H))$, which is a
subgraph of $G$ and therefore in $\mathcal{G}$. Since every vertex in
$G_{\\_}0$ has at most $d$ vertices mapped to it, the maximum degree of
$G_{\\_}0$ (and each $B_{\\_}x^{\prime}-v_{\\_}x^{\prime}$) is at most $ds$.
By assumption, there is an $\ell$-blocking partition $\mathcal{R}$ of
$G_{\\_}0$ with width at most $f(ds)$.

Let $\mathcal{R}^{\prime}:=\mathcal{R}\cup\\{\\{v\\}\colon v\in V(G)\setminus
V(G_{\\_}0)\\}$, which is a partition of $G$. Define
$G^{\prime}:=G/\mathcal{R}^{\prime}$. Since $\mathcal{R}^{\prime}$ is a
connected partition, $G^{\prime}$ is a minor of $G$ and is therefore in
$\mathcal{G}$. The width of $\mathcal{R}^{\prime}$ is at most $f(ds)$, so $G$
is contained in $G^{\prime}\boxtimes K_{\\_}{f(ds)}$ by Observation 15. By
slightly abusing the notation, we identify the graph $G$ with the isomorphic
subgraph of $G^{\prime}\boxtimes K_{\\_}{f(ds)}$. So the graphs
$B_{\\_}x^{\prime}$ are subgraphs of $G^{\prime}\boxtimes K_{\\_}{f(ds)}$, and
each vertex of $G^{\prime}\boxtimes K_{\\_}{f(ds)}$ belongs to at most $d$
graphs $B_{\\_}x^{\prime}$.

For each $x\in V(H)$, let $T_{\\_}x^{\prime}$ be a bfs-spanning tree of
$B_{\\_}x^{\prime}$ rooted at $v_{\\_}x^{\prime}$. Hence, the maximum degree
of $T_{\\_}x^{\prime}-v_{\\_}x^{\prime}$ is at most $ds$ and each vertex is at
distance at most $r$ from the root $v_{\\_}x^{\prime}$ in $T_{\\_}x^{\prime}$.
So each component of $T_{\\_}x^{\prime}-v_{\\_}x^{\prime}$ has at most
$(ds)^{0}+\ldots+(ds)^{r-1}<(ds)^{r}$ vertices’. Let
$\overline{T_{\\_}x^{\prime}}$ denote the graph obtained from
$T_{\\_}x^{\prime}$ by adding each edge of $G^{\prime}\boxtimes
K_{\\_}{f(ds)}$ that joins a vertex of $T_{\\_}x^{\prime}$ to one of its
descendants. Then $\overline{T_{\\_}x^{\prime}}-v_{\\_}x^{\prime}$ has maximum
degree at most $(ds)^{r}$.

Below we show that the maximum degree of
$\overline{T_{\\_}x^{\prime}}-v_{\\_}x^{\prime}$ is at most $s^{\prime}$ and
each vertex in $\overline{T_{\\_}x^{\prime}}$ is at distance at most $r-1$
from $v_{\\_}x^{\prime}$. This implies that $H$ is an
$(r-1,s^{\prime})$-shallow minor of $G^{\prime}\boxtimes
K_{\\_}{f(ds)}\boxtimes K_{\\_}d$, where an appropriate model can be defined
by choosing for each $v\in V(G^{\prime}\boxtimes K_{\\_}{f(ds)})$ an injective
map from $\\{x\in V(H):v\in V(B_{\\_}x^{\prime})\\}$ to $V(K_{\\_}d)$. Since
$G^{\prime}\boxtimes K_{\\_}{f(ds)}\boxtimes K_{\\_}d$ is isomorphic to
$G^{\prime}\boxtimes K_{\\_}{d^{\prime}}$, the lemma will follow.

First we estimate the maximum degree of
$\overline{T_{\\_}x^{\prime}}-v_{\\_}x^{\prime}$. Consider a vertex $v\in
V(T_{\\_}x^{\prime})$ at distance $i\geqslant 1$ from the root
$v_{\\_}x^{\prime}$ in $T_{\\_}x^{\prime}$. Then, for each
$j\in\\{1,\ldots,i-1\\}$, the vertex $v$ has only one ancestor at distance $j$
from $v_{\\_}x^{\prime}$ in $T_{\\_}x^{\prime}$. Since the maximum degree of
$T_{\\_}x^{\prime}-v_{\\_}x^{\prime}$ is at most $ds$, for each
$j\in\\{i+1,\ldots,r\\}$, there are at most $(ds)^{j-i}$ descendants of $v$ at
distance $j$ from $v_{\\_}x^{\prime}$. Therefore, $v$ has at most $(ds)^{j-1}$
neighbours in $\overline{T_{\\_}x^{\prime}}-v_{\\_}x^{\prime}$ which are at
distance $j$ from $v_{\\_}x^{\prime}$ in $T_{\\_}x^{\prime}$. Hence, the
degree of $v$ in $\overline{T_{\\_}x^{\prime}}-v_{\\_}x^{\prime}$ is at most
$(ds)^{0}+\ldots+(ds)^{r-1}<(ds)^{r}$, so the maximum degree of
$\overline{T_{\\_}x^{\prime}}-v_{\\_}x^{\prime}$ is at most $(ds)^{r}$.

It remains to show that in each $\overline{T_{\\_}x^{\prime}}$, every vertex
is at distance at most $r-1$ from $v_{\\_}x^{\prime}$. Suppose to the contrary
that some vertex $u$ is at distance at least $r$ from $v_{\\_}x^{\prime}$ in
$\overline{T_{\\_}x^{\prime}}$. Since
$T_{\\_}x^{\prime}\subseteq\overline{T_{\\_}x^{\prime}}$, and in
$T_{\\_}x^{\prime}$ every vertex is at distance at most $r$ from
$v_{\\_}x^{\prime}$, the vertex $u$ must be at distance exactly $r$ from
$v_{\\_}x^{\prime}$ in $T_{\\_}x^{\prime}$ and $\overline{T_{\\_}x^{\prime}}$.
Let $P=(u_{\\_}0,\ldots,u_{\\_}r)$ be the unique path between
$v_{\\_}x^{\prime}$ and $u$ in $T_{\\_}x^{\prime}$ where
$u_{\\_}0=v_{\\_}x^{\prime}$ and $u_{\\_}r=u$. Let
$P^{\prime}=(x_{\\_}1,\ldots,x_{\\_}r)$ be the projection of $P$ onto
$G_{\\_}0$. Then $P^{\prime}$ is a path in $G_{\\_}0$ with length
$r-1\geqslant\ell+1$, so it contains two vertices $x_{\\_}\alpha$ and
$x_{\\_}\beta$ with $1\leqslant\alpha<\beta$ that belong to the same part in
$\mathcal{R}$. Thus the projection of $u_{\\_}\alpha$ and $u_{\\_}\beta$ (in
$G^{\prime}\boxtimes K_{\\_}{f(ds)}$) are the same vertex in $G^{\prime}$ and
so, by the definition of the strong product, $u_{\\_}\beta
u_{\\_}{\alpha-1}\in E(G^{\prime}\boxtimes K_{\\_}{f(ds)})$. Hence the
distance between $v_{\\_}x^{\prime}$ and $u$ in $\overline{T_{\\_}x^{\prime}}$
is less than $r$, a contradiction. ∎

We prove the next lemma by iteratively applying Lemma 19.

######  Lemma 20.

Let $\mathcal{G}$ be a minor-closed class such that, for some function $f$ and
integer $\ell\geqslant 1$, every graph $G\in\mathcal{G}$ has an
$\ell$-blocking partition with width at most $f(\Delta(G))$. Then there is a
function $h$ such that for any integers $r\geqslant 0$ and $s,d\geqslant 1$,
for every graph $G\in\mathcal{G}$, every $(r,s)$-shallow minor $H$ of
$G\boxtimes K_{\\_}d$ is an $(\ell+2)$-shallow minor of $Q\boxtimes
K_{\\_}{h(d,r,s,\ell)}$ for some minor $Q$ of $G$.

###### Proof.

If $r\leqslant\ell+2$ then $H$ is an $(\ell+2)$-shallow minor of $Q\boxtimes
K_{\\_}{h(d,r,s,\ell)}$, where $Q=G$ and $h(d,r,s,\ell)=d$, and we are done.
Now assume that $r>\ell+2$. Thus $r-\ell-2\geqslant 1$. Let $d_{\\_}0:=d$ and
$s_{\\_}0:=s$ Iteratively applying Lemma 19, we obtain a sequence
$G_{\\_}1,G_{\\_}2,\dots,G_{\\_}{r-\ell-2}$ of minors of $G$, such that for
each $i\in\\{1,\dots,r-\ell-2\\}$, $H$ is an $(r-i,s_{\\_}i)$-shallow minor of
$G_{\\_}i\boxtimes K_{\\_}{d_{\\_}i}$, where
$s_{\\_}i=(d_{\\_}{i-1}s_{\\_}{i-1})^{r-i+1}$ and $d_{\\_}i=d_{\\_}{i-1}\cdot
f(d_{\\_}{i-1}s_{\\_}{i-1})$. In particular (with $i=r-\ell-2$), $H$ is an
$(\ell+2)$-shallow minor of $G_{\\_}{r-\ell-2}\boxtimes
K_{\\_}{d_{\\_}{r+\ell-2}}$. The result follows with $Q:=G_{\\_}{r-\ell-2}$
and $h(d,r,s,\ell):=d_{\\_}{r-\ell-2}$. ∎

###### Proof of Lemma 18.

Let $G\in\mathcal{G}$ and let $G^{\prime}$ be an $(r,s)$-shallow minor of
$G\boxtimes K_{\\_}{d}$. By Lemma 20, $G^{\prime}$ is an $(\ell+2)$-shallow
minor of $Q\boxtimes K_{\\_}{h(d,r,s,\ell)}$ for some minor $Q$ of $G$. Thus
$Q\in\mathcal{G}$. By assumption, $Q$ is contained in $H\boxtimes P\boxtimes
K_{\\_}c$ for some graph $H$ with $\operatorname{tw}(H)\leqslant t$. Hence
$G^{\prime}$ is an $(\ell+2)$-shallow minor of $H\boxtimes P\boxtimes
K_{\\_}{c\,h(d,r,s,\ell)}$. By Theorem 4, $G^{\prime}$ is contained in
$J\boxtimes P\boxtimes K_{\\_}{c(2(\ell+2)+1)^{2}\cdot g(d,r,s,\ell)}$ for
some graph $J$ with $\operatorname{tw}(J)\leqslant\binom{2(\ell+2)+1+t}{t}-1$.
The result follows with $g(d,r,s,\ell,c):=c(2(\ell+2)+1)^{2}\cdot
h(d,r,s,\ell)$. ∎

##  4 The Chordal Partition

Our focus now is the proof of Theorem 16, which is inspired by the
construction of a chordal partition of a planar triangulation by van den
Heuvel et al. [39]. They showed that every planar triangulation $G$ has a
partition $\mathcal{P}$ into paths $P_{\\_}1,\ldots,P_{\\_}n$, such that for
each $i\in\\{1,\ldots,n-1\\}$, the path $P_{\\_}{i+1}$ is geodesic in
$G-(V(P_{\\_}1)\cup\cdots\cup V(P_{\\_}i))$, $P_{\\_}{i+1}$ is adjacent to at
most two of the paths $P_{\\_}1,\ldots,P_{\\_}i$, and if $P_{\\_}{i+1}$ is
adjacent to $P_{\\_}a$ and $P_{\\_}b$ with $1\leqslant a<b\leqslant i$, then
$P_{\\_}a$ is adjacent to $P_{\\_}b$. Then the quotient $G/\mathcal{P}$ is
chordal with treewidth 2.

Our $\ell$-blocking partition of a planar graph $G$ will be obtained from a
partition of $G$ into subtrees $T_{\\_}1,\ldots,T_{\\_}n$ with similar
properties: for each $i\in\\{1,\ldots,n-1\\}$, the tree $T_{\\_}{i+1}$ is
adjacent to at most two of the trees $T_{\\_}1,\ldots,T_{\\_}i$, and if
$T_{\\_}{i+1}$ is adjacent to two of those trees, then they are adjacent to
each other. The final partition is then obtained by appropriately breaking
each $V(T_{\\_}i)$ into connected parts of bounded size.

Fix a planar graph $G$ of maximum degree $\Delta$ and any planar embedding of
$G$. This section constructs a $6$-blocking444Actually, the partition is
$4$-blocking, but for simplicity we prove a weaker bound. chordal partition
$\mathcal{T}$ of $G$. Later sections refine this partition into a connected
(non-chordal) partition $\mathcal{R}$ with width bounded in terms of $\Delta$,
and show that $\mathcal{R}$ is $222$-blocking, which will prove Theorem 16.
Since Theorem 16 is trivial when $\Delta\leqslant 2$, we assume that
$\Delta\geqslant 3$.

Our construction of the $6$-blocking chordal partition is parameterised by a
positive integer $\tau$. Ultimately, we will fix $\tau=37$, but it will be
easier to visualise the construction for smaller values of $\tau$.

We use the notion of $F$-bridges, as illustrated in Figure 2. For a subgraph
$F$ of $G$, an _$F$ -bridge_ is either a length-$1$ path in $G$ that is edge-
disjoint from $F$ and is between two vertices in $V(F)$ (such an $F$-bridge is
_trivial_), or a graph obtained from a component $C$ of $G-V(F)$ by adding all
vertices in $N_{\\_}G(V(C))$ and all edges of $G$ between $V(C)$ and
$N_{\\_}G(V(C))$ (such an $F$-bridge is _non-trivial_). Observe that each edge
of $G$ outside $F$ belongs to exactly one $F$-bridge. In an $F$-bridge $B$,
the set $V(B)\cap V(F)$ is the _attachment-set_ , and its elements are the
_attachment-vertices_ of $B$. Hence, if $B$ is non-trivial with attachment-set
$A$, then $B-A$ is a component of $G-V(F)$.

Figure 2: A graph $G$ with a distinguished sub-forest $F$ with two components
(black). There are four trivial $F$-bridges (green) and four non-trivial
$F$-bridges (each of them is obtained from a component $C$ of $G-V(F)$ (gray)
by adding all blue edges incident with a vertex of $C$ (and their ends outside
$C$))

We will inductively define a sequence of vertex-disjoint trees
$T_{\\_}1,\ldots,T_{\\_}m$ whose vertex-sets will form the chordal partition
of $G$. For each $j\in\\{0,\ldots,m\\}$, we denote the forest
$\bigcup_{\\_}{i<j}T_{\\_}i$ by $F_{\\_}j$ (in particular, $F_{\\_}0$ is
empty). For each $j\in\\{0,\ldots,m\\}$, we maintain the following invariant.

######  Invariant.

For every non-trivial $F_{\\_}j$-bridge $B$, the following hold:

  1. ()

$B$ has attachment-vertices on at most two components of $F_{\\_}j$;

  2. ()

for every component $T_{\\_}i$ of $F_{\\_}j$ that contains an attachment-
vertex of $B$, the tree $T_{\\_}i$ is contained in the closure of the outer-
face of $B$, and the attachment-vertices of $B$ in $V(T_{\\_}i)$ are leaves of
$T_{\\_}i$;

  3. ()

if $B$ has attachment-vertices on two distinct components $T_{\\_}i$ and
$T_{\\_}{i^{\prime}}$ of $F_{\\_}j$, then $T_{\\_}i$ is contained in the
closure of the outer-face of $T_{\\_}{i^{\prime}}\cup B$, and
$T_{\\_}{i^{\prime}}$ is contained in the closure of the outer-face of
$T_{\\_}i\cup B$.

Our invariant implies the following.

######  Claim 1.

Suppose that the invariant is satisfied for some $j\in\\{0,\ldots,m\\}$, and
let $B$ be a nontrivial $F_{\\_}j$-bridge with at least one attachment-vertex.
Let $J$ be the union of $B$ and all components $T_{\\_}i$ of $F_{\\_}j$ that
contain an attachment-vertex of $B$. Then, for each component $T_{\\_}i$
contained in $J$, at least one and at most two attachment-vertices of $B$ on
$T_{\\_}i$ are on the boundary of the outer-face of $J$.

###### Proof.

By invariant (i), $B$ has attachment-vertices on at most one component of
$F_{\\_}j$ distinct from $T_{\\_}i$. By invariant (ii), $T_{\\_}i$ is
contained in the closure of the outer-face of $B$. Moreover, by invariant
(iii), if $B$ has an attachment-vertex on a tree $T_{\\_}{i^{\prime}}$
distinct from $T_{\\_}i$, then $T_{\\_}i$ is contained in the closure of the
outer-face of $B\cup T_{\\_}{i^{\prime}}$. Therefore, in the facial walk along
the outer-face of $J$, the vertices and edges that belong to $T_{\\_}i$ appear
consecutively, forming a (possibly closed) sub-walk $W$. By invariant (ii),
the attachment-vertices of $B$ in $V(T_{\\_}i)$ are leaves of $T_{\\_}i$, so
only the terminal vertices of $W$ are attachments of $B$ in $V(T_{\\_}i)$
which lie on the boundary of the outer-face of $J$. At most two vertices are
terminal vertices of $W$, so the claim holds. ∎

For $j=0$, the invariant is satisfied because $F_{\\_}0$ is empty, so the
$F_{\\_}0$-bridges have no attachment-vertices.

Together with each tree $T_{\\_}j$ we will define a tuple
$(B_{\\_}j,A_{\\_}j,X_{\\_}j,A_{\\_}j^{\operatorname{\text{out}}},D_{\\_}j,T_{\\_}j^{0})$,
where $T_{\\_}j^{0}\subseteq T_{\\_}j\subseteq B_{\\_}j\subseteq G$,
$A_{\\_}j^{\operatorname{\text{out}}}\subseteq A_{\\_}j\subseteq
V(F_{\\_}{j-1})$, $X_{\\_}j\subseteq\\{1,\ldots,j-1\\}$, and
$D_{\\_}j\subseteq V(T_{\\_}j^{0})$.

Let $j\geqslant 1$ be an integer, and suppose that we have already defined the
trees $T_{\\_}1,\dots,T_{\\_}{j-1}$, and thus the forest $F_{\\_}{j-1}$ is
defined. If $V(F_{\\_}{j-1})=V(G)$, then terminate the construction with a
sequence of length $j-1$. Otherwise, let $B_{\\_}j$ be any non-trivial
$F_{\\_}{j-1}$-bridge. Let $A_{\\_}j$ denote the attachment-set of $B_{\\_}j$,
and let $X_{\\_}j$ denote the set of all $i\in\\{1,\ldots,j-1\\}$ such that
$B_{\\_}j$ has an attachment-vertex in $V(T_{\\_}i)$. By invariant (i), we
have $|X_{\\_}j|\leqslant 2$.

Let $J:=B_{\\_}j\cup\bigcup_{\\_}{i\in X_{\\_}j}T_{\\_}i$ Define
$A_{\\_}j^{\operatorname{\text{out}}}$ to be the set of attachment-vertices
$x\in A_{\\_}j$ that lie on the boundary of the outer-face of $J$. By Claim 1,
the set $A_{\\_}j^{\operatorname{\text{out}}}$ contains one or two vertices of
each $T_{\\_}i$ with $i\in X_{\\_}j$, so
$|A_{\\_}j^{\operatorname{\text{out}}}|\leqslant 4$ and if
$A_{\\_}j\neq\varnothing$, then
$A_{\\_}j^{\operatorname{\text{out}}}\neq\varnothing$.

Define a non-empty subset $D_{\\_}j\subseteq V(B_{\\_}j-A_{\\_}j)$ as follows.
If $A_{\\_}j=\varnothing$, then let $D_{\\_}j$ be a set consisting of one
arbitrary vertex on the boundary of the outer-face of $B_{\\_}j$. If
$A_{\\_}j\neq\varnothing$ (and thus
$A_{\\_}j^{\operatorname{\text{out}}}\neq\varnothing$), then let $D_{\\_}j$
denote the set of all vertices $x\in V(B_{\\_}j-A_{\\_}j)$ such that
$\operatorname{dist}_{\\_}G(x,A_{\\_}j^{\operatorname{\text{out}}})\leqslant\tau$.
In $B_{\\_}j$, every vertex from $A_{\\_}j^{\operatorname{\text{out}}}$ has a
neighbour in $V(B_{\\_}j-A_{\\_}j)$ and such a neighbour belongs to $D_{\\_}j$
(recall that $\tau\geqslant 1$). Hence, $D_{\\_}j$ is non-empty.

Let $T_{\\_}j^{0}$ be a tree in $B_{\\_}j-A_{\\_}j$ that contains all vertices
in $D_{\\_}j$ and has the smallest possible number of edges, and let
$T_{\\_}j$ be a tree obtained from $T_{\\_}j^{0}$ by attaching each vertex
$x\in N_{\\_}{B_{\\_}j-A_{\\_}j}(V(T_{\\_}j^{0}))$ with any edge of $G$
between $x$ and $V(T_{\\_}j^{0})$. See Figure 3.

Figure 3: A possible situation in the construction of the tree $T_{\\_}j$ for
$\tau=3$, where $B_{\\_}j$ has attachment-vertices on the trees $T_{\\_}i$ and
$T_{\\_}{i^{\prime}}$. Here,
$A_{\\_}j^{\operatorname{\text{out}}}=\\{u,v,u^{\prime},v^{\prime}\\}$, the
vertices from $D_{\\_}j$ are red, and the tree $T_{\\_}j$ consists of the red
and black edges .

We now verify that for such $T_{\\_}j$, the invariant is satisfied. Let $B$ be
a non-trivial $F_{\\_}j$-bridge. If $B$ has no attachment-vertex on
$T_{\\_}j$, then $B$ is an $F_{\\_}{j-1}$-bridge distinct from $B_{\\_}j$, and
the invariant is satisfied by induction. Hence, we assume that $B$ has an
attachment-vertex on $T_{\\_}j$. Since every component of $G-V(F_{\\_}j)$
which is adjacent in $G$ to $T_{\\_}j$ is a component of
$(B_{\\_}j-A_{\\_}j)-V(T_{\\_}j)$, the $F_{\\_}j$-bridge $B$ is contained in
$B_{\\_}j$. Note that every attachment-vertex of $B$ that is not on $T_{\\_}j$
lies on a tree $T_{\\_}i$ with $i<j$, and thus, is an attachment-vertex of
$B_{\\_}j$.

Suppose first that $X_{\\_}j=\varnothing$. Then $B$ has all its attachment-
vertices on $T_{\\_}j$. The only vertex $x$ of $D_{\\_}j$ is on the boundary
of the outer-face of $B_{\\_}j$. The tree $T_{\\_}j$ is a star with a centre
at $x$ and whose leaves are the neighbours of $x$ in $G$. Therefore $B$ can
intersect $T_{\\_}j$ only in its leaves, and $T_{\\_}j$ is in the closure of
the outer-face of $B$, so the invariant holds.

Now suppose that $X_{\\_}j\neq\varnothing$, and let $i\in X_{\\_}j$. By
induction, the tree $T_{\\_}i$ intersects the boundary of the outer-face of
$J$, and we can write the facial walk along the outer-face of $J$ as
$W=v_{\\_}0e_{\\_}0v_{\\_}1e_{\\_}1\cdots e_{\\_}{n-1}v_{\\_}n$ where
$v_{\\_}0=v_{\\_}n$ and for some $s\in\\{0,\ldots,n-1\\}$ we have $V(W)\cap
V(T_{\\_}i)=\\{v_{\\_}0,\ldots,v_{\\_}s\\}$ and $E(W)\cap
E(T_{\\_}i)=\\{e_{\\_}0,\ldots,e_{\\_}{s-1}\\}$. We have
$A_{\\_}j^{\operatorname{\text{out}}}\cap V(T_{\\_}i)=\\{v_{\\_}0,v_{\\_}s\\}$
(possibly $v_{\\_}0=v_{\\_}s$). Each of the edges
$e_{\\_}{n-1}=v_{\\_}0v_{\\_}{n-1}$ and $e_{\\_}s=v_{\\_}sv_{\\_}{s+1}$ has an
end in $V(T_{\\_}i)$ but does not belong to $T_{\\_}i$. Hence both of these
edges are edges of $B_{\\_}j$, so $\\{v_{\\_}{n-1},v_{\\_}{s+1}\\}\subseteq
V(B_{\\_}j-A_{\\_}j)$. Since $\\{v_{\\_}0,v_{\\_}s\\}\subseteq
A_{\\_}j^{\operatorname{\text{out}}}$, we have
$\\{v_{\\_}{n-1},v_{\\_}{s+1}\\}\subseteq D_{\\_}j\subseteq V(T_{\\_}j^{0})$.

We now show that $B$ has attachment-vertices on at most two components of
$F_{\\_}j$. Every attachment-vertex of $B$ that is not in $V(T_{\\_}j)$, is an
attachment-vertex of $B_{\\_}j$. Hence, if $X_{\\_}j=\\{i\\}$, then $B$ can
only have attachment-vertices on $T_{\\_}j$ and $T_{\\_}i$. Therefore, suppose
that $X_{\\_}j=\\{i,i^{\prime}\\}$ with $i^{\prime}\neq i$. We need to show
that $B$ has an attachment-vertex on at most one of the trees $T_{\\_}i$ and
$T_{\\_}{i^{\prime}}$. By our invariant, $T_{\\_}{i^{\prime}}$ is in the
closure of the outer-face of $T_{\\_}i\cup B$. Therefore,
$T_{\\_}{i^{\prime}}$ intersects $\\{v_{\\_}{s+2},\ldots,v_{\\_}{n-2}\\}$.
Since the vertices $v_{\\_}0,\ldots,v_{\\_}s$ belong to $T_{\\_}i$, the path
$v_{\\_}{n-1}T_{\\_}j^{0}v_{\\_}{s+1}$ separates the trees $T_{\\_}i$ and
$T_{\\_}{i^{\prime}}$ in $J$. Since $T_{\\_}j^{0}\subseteq T_{\\_}j$, every
component of $(B_{\\_}j-A_{\\_}j)-V(T_{\\_}j)$ is adjacent to at most one of
the trees $T_{\\_}i$ and $T_{\\_}{i^{\prime}}$. Since $B$ is a non-trivial
$F_{\\_}j$-bridge contained in $B_{\\_}j$, this means that $B$ has attachment-
vertices in at most one of the trees $T_{\\_}i$ and $T_{\\_}{i^{\prime}}$, as
required. Hence, $B$ has attachment-vertices on at most two components of
$F_{\\_}j$.

Assume without loss of generality that if $B$ has any attachment-vertices that
do not lie on $T_{\\_}j$, then they all lie on the tree $T_{\\_}i$.

Next, we show that every attachment-vertex of $B$ is a leaf of $T_{\\_}i$ or
$T_{\\_}j$. Every attachment-vertex of $B$ on $T_{\\_}i$ is an attachment-
vertex of $B_{\\_}j$, and by induction, is a leaf of $T_{\\_}i$. Since the
tree $T_{\\_}j$ was obtained from $T_{\\_}j^{0}$ by attaching all adjacent
vertices in $B_{\\_}j-A_{\\_}j$ as leaves, all attachment-vertices of $B$ on
$T_{\\_}j$ belong to $V(T_{\\_}j)\setminus V(T_{\\_}j^{0})$, and therefore are
leaves of $T_{\\_}j$.

Finally, we argue that the tree $T_{\\_}i$ is in the closure of the outer-face
of $T_{\\_}j\cup B$, and the tree $T_{\\_}j$ is in the closure of the outer-
face of $T_{\\_}i\cup B$. This will imply that the trees $T_{\\_}i$ and
$T_{\\_}j$ are in the closure of the outer-face of $B$, which will complete
the proof of the invariant. By induction, the tree $T_{\\_}i$ is in the
closure of the outer-face of $B_{\\_}j$. Since $T_{\\_}j\cup B\subseteq
B_{\\_}j$, the tree $T_{\\_}i$ is in the closure of the outer-face of
$T_{\\_}j\cup B$. The vertex $v_{\\_}{s+1}\in V(T_{\\_}j^{0})$ is on the
boundary of the outer-face of $J$. Since $T_{\\_}j^{0}$ and $T_{\\_}i\cup B$
are disjoint subgraphs of $J$, the tree $T_{\\_}j^{0}$ is on the outer-face of
$T_{\\_}i\cup B$. The tree $T_{\\_}j$ is obtained from $T_{\\_}j^{0}$ by
attaching leaves, so it is contained in the closure of the outer-face of
$T_{\\_}i\cup B$. This completes the proof of the invariant and the inductive
construction.

From now on, we assume that $\mathcal{T}=\\{T_{\\_}1,\ldots,T_{\\_}m\\}$ is a
fixed partition obtained by our construction for $\tau=37$, with a tuple
$(B_{\\_}j,A_{\\_}j,X_{\\_}j,A_{\\_}j^{\operatorname{\text{out}}},D_{\\_}j,T_{\\_}j^{0})$
associated to each tree $T_{\\_}j$.

For later reference, we make explicit some implications of the inductive
construction.

######  Claim 2.

For each $j\in\\{1,\ldots,m\\}$, if $X_{\\_}j=\\{i,i^{\prime}\\}$ with $i\neq
i^{\prime}$, then the tree $T_{\\_}j^{0}$ separates the trees $T_{\\_}i$ and
$T_{\\_}{i^{\prime}}$ in the graph $T_{\\_}i\cup T_{\\_}{i^{\prime}}\cup
B_{\\_}j$. Consequently, the tree $T_{\\_}j^{0}$ separates the sets
$A_{\\_}j\cap V(T_{\\_}i)$ and $A_{\\_}j\cap V(T_{\\_}{i^{\prime}})$ in the
graph $B_{\\_}j$.

######  Claim 3.

For each $j\in\\{1,\ldots,m\\}$, no non-trivial $F_{\\_}j$-bridge has an
attachment-vertex on $T_{\\_}j^{0}$.

######  Claim 4.

For any $j\in\\{1,\ldots,m\\}$ and $i\in X_{\\_}j$, the graph $B_{\\_}j$
contains an edge between $A_{\\_}j^{\operatorname{\text{out}}}\cap
V(T_{\\_}i)$ and $D_{\\_}j$. In particular, $T_{\\_}i$ is adjacent to
$T_{\\_}j$ in $G$.

We will also use the following simple properties of our construction.

######  Claim 5.

For $j\in\\{1,\ldots,m\\}$, an $F_{\\_}j$-bridge $B$ has an attachment-vertex
on $T_{\\_}j$ if and only if $B\subseteq B_{\\_}j$.

###### Proof.

Suppose that $B$ has an attachment-vertex on $T_{\\_}j$. If $B$ is trivial,
then it consists of one edge with an end in the component $B_{\\_}j-A_{\\_}j$
of $G-V(F_{\\_}{j-1})$, and hence $B\subseteq B_{\\_}j$. If $B$ is non-
trivial, then it is obtained by adding attachment-vertices to a component of
$G-V(F_{\\_}{j})$ adjacent to $T_{\\_}j$. That component is contained in
$B_{\\_}j-A_{\\_}j$, so again $B\subseteq B_{\\_}j$.

Now suppose that $B\subseteq B_{\\_}j$. If $B$ is trivial, then its two
attachment-vertices belong to $A_{\\_}j\cup V(T_{\\_}j)$. Since $A_{\\_}j$ is
an independent set $B_{\\_}j$, at least one attachment-vertex of $B$ is on
$T_{\\_}j$. If $B$ is non-trivial, then since $B\subseteq B_{\\_}j$, it is
obtained from a component of $(B_{\\_}j-A_{\\_}j)-V(T_{\\_}j)$ by adding all
vertices adjacent to it as attachment-vertices. Since $B_{\\_}j-A_{\\_}j$ is
connected, at least one of these attachment-vertices will lie on $T_{\\_}j$. ∎

######  Claim 6.

For $j\in\\{1,\ldots,m\\}$, every non-trivial $F_{\\_}j$-bridge $B$ is equal
to $B_{\\_}k$ for some $k\in\\{j+1,\ldots,m\\}$.

###### Proof.

The vertex-sets of the trees $T_{\\_}1,\ldots,T_{\\_}m$ partition $V(G)$, so
there exists the least $k\in\\{j+1,\ldots,m\\}$ that contains a non-
attachment-vertex of $B$. Hence, $B$ intersects $F_{\\_}{k-1}$ only in its
attachment-vertices, and they all belong to $F_{\\_}j$, so $B$ is an
$F_{\\_}{k-1}$-bridge that intersects $T_{\\_}k$, and therefore $B=B_{\\_}k$.
∎

Although we do not use this in our proof, we now show that $\mathcal{T}$ is a
chordal partition.

######  Claim 7.

$\mathcal{T}$ is a chordal partition with
$\operatorname{tw}(G/\mathcal{T})\leqslant 2$.

###### Proof.

Clearly $\mathcal{T}$ is a connected partition since each part has a spanning
subtree. Let $j\in\\{1,\ldots,m\\}$. If $T_{\\_}j$ is adjacent in $G$ to a
tree $T_{\\_}i$ with $i<j$, then, since $T_{\\_}j\subseteq B_{\\_}j-A_{\\_}j$,
the $F_{\\_}{j-1}$-bridge $B_{\\_}j$ has an attachment-vertex on $T_{\\_}i$,
that is, $i\in X_{\\_}j$. Since $|X_{\\_}j|\leqslant 2$, the tree $T_{\\_}j$
can be adjacent to at most two of the trees $T_{\\_}1,\ldots,T_{\\_}{j-1}$. It
remains to show that if $T_{\\_}j$ is adjacent to two trees $T_{\\_}i$ and
$T_{\\_}{i^{\prime}}$ with $i<i^{\prime}<j$, then $T_{\\_}i$ is adjacent to
$T_{\\_}{i^{\prime}}$ in $G$. Since $T_{\\_}j$ is adjacent to
$T_{\\_}{i^{\prime}}$, we have $i^{\prime}\in X_{\\_}j$, and therefore, by
Claim 5, we have $B_{\\_}j\subseteq B_{\\_}{i^{\prime}}$. The attachment-
vertices of $B_{\\_}j$ on $T_{\\_}i$ are thus attachment-vertices of
$B_{\\_}{i^{\prime}}$, so $i\in X_{\\_}{i^{\prime}}$. By Claim 4, $T_{\\_}i$
is adjacent to $T_{\\_}{i^{\prime}}$. ∎

The following property of our chordal partition will play a key role in the
proof.

######  Claim 8.

Let $j,k\in\\{1,\ldots,m\\}$ be such that $B_{\\_}k$ is an $F_{\\_}j$-bridge
contained in $B_{\\_}j$, let $B$ be a (possibly trivial) $F_{\\_}j$-bridge
contained in $B_{\\_}j$ that is distinct from $B_{\\_}k$ and has an
attachment-vertex in $A_{\\_}j$, and let $Q$ be a $V(B)$–$V(B_{\\_}k)$ path in
$B_{\\_}j-V(T_{\\_}j^{0})$. Then the end of $Q$ in $V(B_{\\_}k)$ belongs to
$A_{\\_}k^{\operatorname{\text{out}}}$.

###### Proof.

By Claim 5, each of the $F_{\\_}j$-bridges $B$ and $B_{\\_}k$ has an
attachment-vertex on $T_{\\_}j$. The $F_{\\_}j$-bridge $B$ has attachment-
vertices on at most two components of $F_{\\_}j$, so the attachment-vertices
of $B$ in $A_{\\_}j$ must belong to one tree $T_{\\_}i$ with $i<j$. We show
that if $B_{\\_}k$ has any attachment-vertices outside $T_{\\_}j$, then they
all belong to $T_{\\_}i$. By Claim 3, the non-trivial $F_{\\_}j$-bridge
$B_{\\_}k$ is disjoint from $T_{\\_}j^{0}$. Likewise, if $B$ is non-trivial,
then it is is disjoint from $T_{\\_}j^{0}$. Otherwise $B$ is trivial and it
can have attachments on $T_{\\_}j^{0}$. Let $B^{\prime}:=B-V(B)\cap
V(T_{\\_}j^{0})$. Hence, $B^{\prime}$ is a connected graph that contains all
attachment-vertices of $B$ on $T_{\\_}i$ and an end of $Q$. The graph
$B_{\\_}k\cup Q\cup B^{\prime}$ is therefore a connected subgraph of
$B_{\\_}j-V(T_{\\_}j^{0})$ that intersects $T_{\\_}i$. Therefore, by Claim 2,
the graph $B_{\\_}k\cup Q\cup B^{\prime}$ intersects $A_{\\_}j$ only in
vertices belonging to $T_{\\_}i$, so indeed any attachment-vertices of
$B_{\\_}k$ not on $T_{\\_}j$ must lie on $T_{\\_}i$. See Figure 4.

Figure 4: Illustration of Claim 8. The end of $Q$ in $B_{\\_}k$ must belong to
$A_{\\_}k^{\operatorname{\text{out}}}$

We claim that the only face of $T_{\\_}i\cup T_{\\_}j\cup B_{\\_}k$ whose
boundary intersects both $T_{\\_}i$ and $T_{\\_}j$ is the outer-face. By our
invariant, this is true when $B_{\\_}k$ has attachment-vertices in both
$T_{\\_}i$ and $T_{\\_}j$, so suppose that $B_{\\_}k$ has attachment-vertices
only on $T_{\\_}j$. Then $T_{\\_}i\cup T_{\\_}j\cup B_{\\_}k$ has two
components $T_{\\_}i$ and $T_{\\_}j\cup B_{\\_}k$. The graph $T_{\\_}j$ is in
the closure of the outer-face of $B_{\\_}k$, and the graph $T_{\\_}i$ is in
the closure of the outer-face of $B_{\\_}j$. Since $T_{\\_}j\cup
B_{\\_}k\subseteq B_{\\_}j$, this means that $T_{\\_}i$ is on the outer-face
of $T_{\\_}j\cup B_{\\_}k$, and the only face of $T_{\\_}i\cup T_{\\_}j\cup
B_{\\_}k$ whose boundary intersects $T_{\\_}i$ and $T_{\\_}j$ is the outer-
face. Therefore, $B$ is contained in the closure of the outer-face of
$T_{\\_}i\cup T_{\\_}j\cup B_{\\_}k$. By Claim 3, $B_{\\_}j$ is disjoint from
$T_{\\_}i^{0}$. Since $Q\subseteq B_{\\_}j-V(T_{\\_}j^{0})$, this means that
$Q$ is disjoint from $T_{\\_}i^{0}$ and $T_{\\_}j^{0}$, and thus $Q$ can
intersect the trees $T_{\\_}i$ and $T_{\\_}j$ only in their leaves.
Furthermore, $Q$ intersects $B_{\\_}k$ only in one end, so the path $Q$
belongs to the closure of the outer-face of $T_{\\_}i\cup T_{\\_}j\cup
B_{\\_}k$ together with $B$. Hence, the path $Q$ intersects $B_{\\_}k$ in a
vertex on the boundary of the outer-face of $T_{\\_}i\cup T_{\\_}j\cup
B_{\\_}k$. That vertex is an attachment-vertex of $B_{\\_}k$ in
$A_{\\_}k^{\operatorname{\text{out}}}$. ∎

The following claim, while not used in the main proof, provides helpful
intuition for the more complicated proof that follows. The proof of this claim
does not rely on the value of $\tau$, and even works with $\tau=1$. Also, the
trees $T_{\\_}j^{0}$ do not need to minimise the number of edges for this
proof to work. These properties will be useful later, in the proof of Theorem
16.

######  Claim 9.

The partition $\mathcal{T}$ is 6-blocking.

###### Proof.

Consider a $\mathcal{T}$-clean path $P$ in $G$. We now show that the length of
$P$ is at most $6$. Let $T_{\\_}i$ be the tree that intersects $P$ and has the
smallest $i$. Since $P$ is $\mathcal{T}$-clean, it intersects $T_{\\_}i$ in
only one vertex, which splits $P$ into two edge-disjoint paths, each
intersecting $T_{\\_}i$ only in one of its ends. Therefore, it suffices to
show that if $Q=(x_{\\_}0,\ldots,x_{\\_}p)$ is a $\mathcal{T}$-clean path such
that $V(Q)\cap V(F_{\\_}i)=\\{x_{\\_}0\\}\subseteq V(T_{\\_}i)$, then
$p\leqslant 3$.

Suppose towards a contradiction that $p\geqslant 4$. Since $V(Q)\cap
V(F_{\\_}i)=\\{x_{\\_}0\\}$, the path $Q$ is contained in a non-trivial
$F_{\\_}i$-bridge. By Claim 6, that $F_{\\_}i$-bridge is equal to $B_{\\_}j$
for some $j\in\\{i+1,\ldots,m\\}$. Fix the largest $j\in\\{i+1,\ldots,m\\}$
such that $Q\subseteq B_{\\_}j$. We split the argument into two cases based on
whether the path $Q$ intersects $T_{\\_}j^{0}$ or not.

Suppose first that $x_{\\_}\alpha\in V(T_{\\_}j^{0})$ for some
$\alpha\in\\{1,\ldots,p\\}$. Since $Q$ is $\mathcal{T}$-clean, $x_{\\_}\alpha$
is the only vertex of $Q$ on $T_{\\_}j$. In particular, the vertex
$x_{\\_}{\alpha-1}$ is adjacent to $T_{\\_}j^{0}$ in $B_{\\_}j$ and does not
belong to $T_{\\_}j$, so $x_{\\_}{\alpha-1}\in A_{\\_}j$. The path
$x_{\\_}0Qx_{\\_}{\alpha-1}$ is disjoint from $V(T_{\\_}j^{0})$, so by Claim 2
it contains attachment-vertices of $B_{\\_}j$ on at most one component of
$F_{\\_}{j-1}$. Since $x_{\\_}0\in V(T_{\\_}i)$ and $x_{\\_}{\alpha-1}\in
A_{\\_}j$, this implies that $x_{\\_}{\alpha-1}\in V(T_{\\_}i)$, and therefore
$\alpha-1=0$, that is $\alpha=1$.

The vertex $x_{\\_}0$ is the only vertex of $Q$ on $T_{\\_}i$, and the vertex
$x_{\\_}1$ is the only vertex of $Q$ on $T_{\\_}j$. We have $x_{\\_}1\in
V(T_{\\_}j^{0})$, so by definition of $T_{\\_}j$ the vertex $x_{\\_}2$ is an
attachment-vertex of $B_{\\_}j$ on a tree $T_{\\_}{i^{\prime}}$ distinct from
$T_{\\_}i$. By our choice of $i$, we have $i<i^{\prime}<j$. Hence, $B_{\\_}j$
has attachment-vertices only on $T_{\\_}i$ and $T_{\\_}{i^{\prime}}$. Since
$Q\subseteq B_{\\_}j$, and $Q$ is $\mathcal{T}$-clean, this implies $V(Q)\cap
V(F_{\\_}j)=\\{x_{\\_}0,x_{\\_}1,x_{\\_}2\\}$. Since $p\geqslant 4$, the path
$x_{\\_}2Qx_{\\_}p$ is contained in a non-trivial $F_{\\_}j$-bridge which, by
Claim 6 is equal to $B_{\\_}k$ for some $k\in\\{j+1,\ldots,m\\}$. Since
$Q\subseteq B_{\\_}j$, we have $B_{\\_}k\subseteq B_{\\_}j$. The edge
$x_{\\_}1x_{\\_}2$ is a trivial $F_{\\_}j$-bridge contained in $B_{\\_}k$ that
contains an attachment-vertex in $A_{\\_}j$, and its attachment-vertex
$x_{\\_}2$ belongs to $B_{\\_}k$ (see Figure 5(a)). Hence, by Claim 8 applied
to the trivial path consisting of the vertex $x_{\\_}2$ alone, we have
$x_{\\_}2\in A_{\\_}k^{\operatorname{\text{out}}}$.

We have $B_{\\_}k\subseteq B_{\\_}j$, so by Claim 5, the $F_{\\_}j$-bridge
$B_{\\_}k$ has an attachment-vertex on $T_{\\_}j$. The vertex $x_{\\_}2$ is an
attachment-vertex of $B_{\\_}k$ on $T_{\\_}{i^{\prime}}$, so $B_{\\_}k$ has
attachment-vertices only on $T_{\\_}{i^{\prime}}$ and $T_{\\_}j$. Since
$V(Q)\cap V(T_{\\_}{i^{\prime}})=\\{x_{\\_}2\\}$ and $V(Q)\cap
V(T_{\\_}j)=\\{x_{\\_}1\\}$, we have $x_{\\_}3Qx_{\\_}p\subseteq
B_{\\_}k-A_{\\_}k$. Since $x_{\\_}2\in A_{\\_}k^{\operatorname{\text{out}}}$
this implies that $x_{\\_}3\in D_{\\_}k\subseteq V(T_{\\_}k^{0})$, and thus
$x_{\\_}4\in V(T_{\\_}k)$. Hence $\\{x_{\\_}3,x_{\\_}4\\}\subseteq
V(T_{\\_}k)$, contrary to the assumption that $Q$ is $\mathcal{T}$-clean.

Now consider the case when $Q$ is disjoint from $T_{\\_}j^{0}$. We have
$x_{\\_}0\in V(T_{\\_}i)$ and $x_{\\_}1\not\in V(T_{\\_}i)$, so
$x_{\\_}0x_{\\_}1\not\in E(F_{\\_}j)$. Let $B$ be the $F_{\\_}j$-bridge
containing the edge $x_{\\_}0x_{\\_}1$. Because $x_{\\_}0x_{\\_}1\in
E(B_{\\_}j)$, we have $B\subseteq B_{\\_}j$, so by Claim 5, $B$ has an
attachment-vertex on $T_{\\_}j$. The vertex $x_{\\_}0$ is an attachment-vertex
of $B$ on $T_{\\_}i$, so $B$ has attachment-vertices only on $T_{\\_}i$ and
$T_{\\_}j$. Observe that $Q\not\subseteq B$; indeed, if $B$ is trivial, this
follows from the fact that $p\geqslant 4$, and if $B$ is a non-trivial
$F_{\\_}j$-bridge, then by Claim 6, we have $B=B_{\\_}k$ for some
$k\in\\{j+1,\ldots,m\\}$, and $Q\not\subseteq B_{\\_}k$ by our choice of $j$.
Since $Q\not\subseteq B$ and $x_{\\_}0x_{\\_}1\in E(B)$, $Q$ contains a vertex
$x_{\\_}\alpha$ that is an attachment-vertex of $B$ distinct from $x_{\\_}0$.
Since $B$ has attachment-vertices only on $T_{\\_}i$ and $T_{\\_}j$ and $Q$ is
$\mathcal{T}$-clean, the vertex $x_{\\_}{\alpha}$ is the only vertex of $Q$ on
$T_{\\_}j$.

We claim that $\alpha\leqslant 2$. If $B$ is trivial, then $\alpha=1\leqslant
2$, so suppose that $B$ is non-trivial, and thus $B=B_{\\_}k$ for some
$k\in\\{j+1,\ldots,m\\}$. We have $x_{\\_}0\in V(T_{\\_}i)$ and
$x_{\\_}\alpha\in V(T_{\\_}j)$, so by Claim 2, the path
$x_{\\_}0Qx_{\\_}\alpha$ must intersect $T_{\\_}k^{0}$ in a vertex
$x_{\\_}{\alpha^{\prime}}$ with $0<\alpha^{\prime}<\alpha$. Since $Q$ is
$\mathcal{T}$-clean, the vertex $x_{\\_}{\alpha^{\prime}}$ is the only vertex
of $Q$ in $V(T_{\\_}k)$. Hence, by definition of $T_{\\_}k$, the vertices
$x_{\\_}{\alpha^{\prime}-1}$ and $x_{\\_}{\alpha^{\prime}+1}$ are attachment-
vertices of $B_{\\_}k$, and therefore belong to $V(T_{\\_}i)\cup V(T_{\\_}j)$.
The only vertex of $Q$ in $V(T_{\\_}i)$ is $x_{\\_}0$, and the only vertex of
$Q$ in $V(T_{\\_}j)$ is $x_{\\_}\alpha$, so
$x_{\\_}{\alpha^{\prime}-1}=x_{\\_}0$ and
$x_{\\_}{\alpha^{\prime}+1}=x_{\\_}\alpha$. Hence $\alpha^{\prime}=1$ and
$\alpha=2$. This proves $\alpha\leqslant 2$.

Since $Q\subseteq B_{\\_}j-V(T_{\\_}j^{0})$, Claim 2 implies that the only
component of $F_{\\_}{j-1}$ intersected by $Q$ is $T_{\\_}i$. Hence, $V(Q)\cap
V(F_{\\_}j)=\\{x_{\\_}0,x_{\\_}\alpha\\}$. Since $\alpha\leqslant 2$ and
$p\geqslant 4$, the path $x_{\\_}\alpha Qx_{\\_}p$ is contained in a non-
trivial $F_{\\_}j$-bridge, which equals $B_{\\_}k$ for some
$k\in\\{j+1,\ldots,m\\}$. See Figure 5(b). The $F_{\\_}j$-bridge $B$ is
contained in $B_{\\_}j$ and has an attachment-vertex in $A_{\\_}j$, and the
vertex $x_{\\_}\alpha$ is an attachment-vertex of $B_{\\_}{k}$ in
$V(T_{\\_}j)$. Hence, by Claim 8 applied to the trivial path consisting of the
vertex $x_{\\_}\alpha$ alone, we have $x_{\\_}{\alpha}\in
A_{\\_}{k}^{\operatorname{\text{out}}}$. By Claim 3, $B_{\\_}{k}$ is disjoint
from $T_{\\_}j^{0}$, and it is contained in the same component of
$B_{\\_}j-V(T_{\\_}j^{0})$ as $Q$. Hence, by Claim 2, $B_{\\_}{k}$ can only
have attachment-vertices in $V(T_{\\_}i)$ and $V(T_{\\_}j)$. Since $Q$ is
$\mathcal{T}$-clean with $x_{\\_}0\in V(T_{\\_}i)$ and $x_{\\_}\alpha\in
V(T_{\\_}j)$, we have $x_{\\_}{\alpha+1}Qx_{\\_}p\subseteq
B_{\\_}{k}-A_{\\_}{k}$. Since $x_{\\_}\alpha\in
A_{\\_}{k}^{\operatorname{\text{out}}}$, this implies $x_{\\_}{\alpha+1}\in
D_{\\_}{k}\subseteq V(T_{\\_}{k}^{0})$, and thus $x_{\\_}{\alpha+2}\in
V(T_{\\_}{k})$. Therefore, $\\{x_{\\_}{\alpha+1},x_{\\_}{\alpha+2}\\}\subseteq
V(T_{\\_}{k})$, contrary to the assumption that $Q$ is $\mathcal{T}$-clean.

(a) $V(Q)\cap V(T_{\\_}j^{0})\neq\varnothing$

(b) $V(Q)\cap V(T_{\\_}j^{0})=\varnothing$

Figure 5: The two cases in the proof that the length of $Q$ is at most $3$.

∎

Although the partition $\mathcal{T}$ is $6$-blocking, its parts can be
arbitrarily large. The next step of our construction refines the chordal
partition.

##  5 Refinement of the Chordal Partition

In order to define our refinement of the chordal partition $\mathcal{T}$, we
need to study its properties in more detail.

######  Claim 10.

For each $j\in\\{1,\ldots,m\\}$, $|D_{\\_}j|<\Delta^{40}$.

###### Proof.

If $B_{\\_}j$ has no attachment-vertices, then
$|D_{\\_}j|=1\leqslant\Delta^{40}$, so suppose that $B_{\\_}j$ has some
attachment-vertices. $B_{\\_}j$ has attachment-vertices in at most two
components of $F_{\\_}{j-1}$, and on each of them
$A_{\\_}j^{\operatorname{\text{out}}}$ has one or two vertices, so
$|A_{\\_}j^{\operatorname{\text{out}}}|\leqslant 4$. Since each vertex in
$D_{\\_}j$ is at distance at most $\tau$ from a vertex in
$A_{\\_}j^{\operatorname{\text{out}}}$,

$|D_{\\_}j|\leqslant|A_{\\_}j^{\operatorname{\text{out}}}|(\Delta^{0}+\ldots+\Delta^{\tau})<4\Delta^{\tau+1}<\Delta^{\tau+3}=\Delta^{40}.\qed$

Two paths in a graph are _internally disjoint_ if none of them contains an
inner vertex of another, and a path is _internally disjoint_ from a set of
vertices $D$ if no inner vertex of the path belongs to $D$.

######  Claim 11.

For each $j\in\\{1,\ldots,m\\}$, the tree $T_{\\_}j^{0}$ is the union of a
family $\mathcal{P}_{\\_}j$ of at most $2\Delta^{40}$ geodesic paths which are
pairwise internally disjoint and internally disjoint from $D_{\\_}j$.

###### Proof.

Let $S$ denote the set of all vertices of $T_{\\_}j^{0}$ with degree at least
$3$. Since $T_{\\_}j^{0}$ is the tree in $B_{\\_}j-A_{\\_}j$ which contains
all vertices in $D_{\\_}j$ and has the smallest possible number of edges,
every leaf of $T_{\\_}j^{0}$ belongs to $D_{\\_}j$, so $T_{\\_}j^{0}$ has at
most $|D_{\\_}j|$ leaves, and thus $|S|\leqslant|D_{\\_}j|$. The tree
$T_{\\_}j^{0}$ is a subdivision of a tree with vertex-set $S\cup D_{\\_}j$.
Therefore, $T_{\\_}j^{0}$ is the union of a set $\mathcal{P}$ of at most
$|S\cup D_{\\_}j|$ pairwise internally disjoint paths such that each
$P\in\mathcal{P}$ has its ends in $S\cup D_{\\_}j$ and is internally disjoint
from $S\cup D_{\\_}j$. We have $|\mathcal{P}|\leqslant|S\cup
D_{\\_}j|\leqslant 2|D_{\\_}j|$, so by Claim 10, $|\mathcal{P}|\leqslant
2\Delta^{40}$. Suppose towards a contradiction that some path
$P\in\mathcal{P}$ is not geodesic in $B_{\\_}j-A_{\\_}j$, and let $P^{\prime}$
be a geodesic path in $B_{\\_}j-A_{\\_}j$ between the ends of $P$. Hence,
$P^{\prime}$ has less edges than $P$, so any spanning tree of
$P^{\prime}\cup\bigcup_{\\_}{Q\in\mathcal{P}\setminus\\{P\\}}Q$ has less edges
than $T$ and contains all vertices in $D_{\\_}j$, which is a contradiction. ∎

An important property of geodesic paths is that the distances between vertices
are preserved in them. We show that the tree $T_{\\_}j^{0}$ ‘approximates’ the
distances between its vertices in $B_{\\_}j-A_{\\_}j$.

######  Claim 12.

Let $j\in\\{1,\ldots,m\\}$, and let $x,y\in V(T_{\\_}j^{0})$. Then

$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x,y)<\Delta^{40}\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x,y).$

###### Proof.

Let $P$ be a geodesic $x$–$y$ path in $B_{\\_}j-A_{\\_}j$. We have
$\operatorname{dist}_{\\_}P(x,y)=\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x,y)$,
so we need to show that
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x,y)<\Delta^{40}\operatorname{dist}_{\\_}P(x,y)$.

First consider the case when $P$ is internally disjoint from
$V(T_{\\_}j^{0})$.

Let $z_{\\_}0,\ldots,z_{\\_}s$ denote the sequence of all vertices of the path
$xT_{\\_}j^{0}y$ that belong to $D_{\\_}j\cup\\{x,y\\}$ or have degree at
least $3$ in $T$, ordered by increasing distance from $x$ (so that
$z_{\\_}0=x$ and $z_{\\_}s=y$).

We show that $s<|D_{\\_}j|$ by associating a distinct vertex
$z_{\\_}i^{\prime}\in D_{\\_}j$ to each $z_{\\_}i$. Let $i\in\\{0,\dots,s\\}$.
If $z_{\\_}i\in D_{\\_}j$, then let $z_{\\_}i^{\prime}:=z_{\\_}i$. Otherwise
$z_{\\_}i\not\in D_{\\_}j$, and either $z_{\\_}i$ is an end of
$xT_{\\_}j^{0}y$ but not a leaf of $T_{\\_}j^{0}$, or $z_{\\_}i$ has degree at
least $3$ in $T_{\\_}j^{0}$. In both cases, there exists a leaf
$z_{\\_}i^{\prime}$ in $T_{\\_}j^{0}$ such that $z_{\\_}i$ is adjacent to the
component of $T_{\\_}j^{0}-V(xT_{\\_}j^{0}y)$ that contains
$z_{\\_}i^{\prime}$. By our choice of $T_{\\_}j^{0}$, we have
$z_{\\_}i^{\prime}\in D_{\\_}j$. Clearly, the vertices
$z_{\\_}0^{\prime},\ldots,z_{\\_}s^{\prime}$ are distinct, so $s<|D_{\\_}j|$.

For each $i\in\\{0,\ldots,s-1\\}$, let $T(i)$ denote the graph obtained from
$T_{\\_}j^{0}$ by removing all edges and inner vertices of
$z_{\\_}iT_{\\_}j^{0}z_{\\_}{i+1}$ and adding the path $P$. The path $P$ has
ends in $z_{\\_}0$ and $z_{\\_}s$, and is internally disjoint from
$V(T_{\\_}j^{0})$, so $T(i)$ is a tree. This tree still contains $D$, so by
definition of $T_{\\_}j^{0}$,

$|E(T_{\\_}j^{0})|\leqslant|E(T(i))|=|E(T_{\\_}j^{0})|-|E(z_{\\_}iT_{\\_}j^{0}z_{\\_}{i+1})|+|E(P)|,$

so
$\operatorname{dist}_{\\_}{T_{\\_}{j}^{0}}(z_{\\_}i,z_{\\_}{i+1})=|E(z_{\\_}iT_{\\_}j^{0}z_{\\_}{i+1})|\leqslant|E(P)|$.
Therefore,

$\displaystyle\operatorname{dist}_{\\_}{T_{\\_}{j}^{0}}(x,y)=\sum_{\\_}{i=0}^{s-1}|E(z_{\\_}{i}T_{\\_}j^{0}z_{\\_}{i+1})|\leqslant
s\cdot|E(P)|<|D_{\\_}j|\cdot\operatorname{dist}_{\\_}P(x,y)\leqslant\Delta^{40}\cdot\operatorname{dist}_{\\_}P(x,y),$

where the last inequality follows from Claim 10.

It remains to consider the case when $P$ has at least one inner vertex in
$V(T_{\\_}j^{0})$. Let $w_{\\_}0,\ldots,w_{\\_}n$ denote the vertices in
$V(P)\cap V(T_{\\_}j^{0})$ ordered by increasing distance from $x$ in $P$ (so
that $w_{\\_}0=x$ and $w_{\\_}n=y$). For each $i\in\\{0,\ldots,n-1\\}$, the
path $w_{\\_}iPw_{\\_}{i+1}$ has no inner vertices in $V(T_{\\_}j^{0})$, so
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(w_{\\_}i,w_{\\_}{i+1})<\Delta^{40}\cdot\operatorname{dist}_{\\_}{P}(w_{\\_}i,w_{\\_}{i+1})$,
and thus

$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x,y)\leqslant\sum_{\\_}{i=0}^{n-1}\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(w_{\\_}i,w_{\\_}{i+1})<\sum_{\\_}{i=0}^{n-1}\Delta^{40}\cdot\operatorname{dist}_{\\_}P(w_{\\_}i,w_{\\_}{i+1})=\Delta^{40}\cdot\operatorname{dist}_{\\_}P(x,y).\qed$

Let $c\in\mathbb{N}$. For any vertex $x\in V(G)$, the number of vertices
$x^{\prime}\in V(G)$ with $\operatorname{dist}_{\\_}G(x,x^{\prime})\leqslant
c$ is at most $\sum_{\\_}{i=0}^{c}\Delta^{i}$, and therefore less than
$\Delta^{c+1}$. For all edges $e,e^{\prime}\in E(G)$, if
$\operatorname{dist}_{\\_}G(e,e^{\prime})\leqslant c$, then $e^{\prime}$ is
incident with a vertex $x^{\prime}$ such that
$\operatorname{dist}_{\\_}G(x,x^{\prime})\leqslant c$ for some $x$ incident
with $e$. Therefore, for any edge $e\in E(G)$, the number of edges
$e^{\prime}\in E(G)$ with $\operatorname{dist}_{\\_}G(e,e^{\prime})\leqslant
c$ is less than $\Delta(2\Delta^{c+1})=2\Delta^{c+2}$. We use these bounds
implicitly in the following part of this section.

In a graph $J$, we say that a set of edges $M\subseteq E(J)$ is _$d$
-independent_ if for any pair of distinct edges $e_{\\_}1,e_{\\_}2\in M$ we
have $\operatorname{dist}_{\\_}J(e_{\\_}1,e_{\\_}2)>d$. We aim to refine the
partition $\mathcal{T}$ be removing a set of edges $M_{\\_}j\subseteq
E(T_{\\_}j^{0})$ from each $T_{\\_}j$, and letting the components of the
resulting forests be the parts of the partition. The precise description of
the desired properties of the sets $M_{\\_}j$ will be given in Claim 14.
Roughly speaking, we want the edges in each $M_{\\_}j$ to be far away from
each other, from other sets $M_{\\_}{j^{\prime}}$, and from the set
$D_{\\_}j$, while ensuring that the components of $T_{\\_}j-M_{\\_}j$ have
bounded size. In order to formalise being far away, we need the following
definition. Let $i\in\\{1,\ldots,m\\}$, and suppose that the set
$M_{\\_}i\subseteq E(T_{\\_}i^{0})$ is already defined. Let $S$ be a set of
vertices or a set of edges in $B_{\\_}i-V(T_{\\_}i^{0})$. The _mixed distance_
of $S$ from $M_{\\_}i$ is

${\color[rgb]{.5,0,0}\operatorname{mdist}_{\\_}i(S)}:=\min\\{\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(M_{\\_}i,v)+\operatorname{dist}_{\\_}{B_{\\_}i-V(T_{\\_}i^{0})}(v,S):v\in
V(T_{\\_}i)\setminus V(T_{\\_}i^{0})\\}.$

Our goal is to construct the sets $M_{\\_}j$ so that for an appropriate
constant $c$ (specified in the next section), for each $j\in\\{1,\ldots,m\\}$
with $X_{\\_}j\neq\varnothing$, we have
$\operatorname{mdist}_{\\_}i(M_{\\_}j)>c$ for all $i\in X_{\\_}j$.

The sets $M_{\\_}j$ will be constructed one-by-one, where each set $M_{\\_}j$
is obtained from $T_{\\_}j^{0}$ by selecting an appropriate set of edges from
each geodesic path in $\mathcal{P}_{\\_}j$, using the following claim, which
exploits the fact that $G$ is a plane graph.

######  Claim 13.

Let $c\geqslant 1$, let $d:=(8c+12)\Delta^{c+2}$, and let $n_{\\_}0\geqslant
d+2c$. Let $P$ be a geodesic path in $B_{\\_}j-A_{\\_}j$ for some
$j\in\\{1,\ldots,m\\}$ with $X_{\\_}j\neq\varnothing$, and suppose that for
each $i\in X_{\\_}j$ we are given a set $M_{\\_}i\subseteq E(T_{\\_}i^{0})$
that is $(d+2c)$-independent in $B_{\\_}i-A_{\\_}i$, Then there exists a set
$M_{\\_}P\subseteq E(P)$ that is $(d+2c)$-independent in $B_{\\_}j-A_{\\_}j$
such that each component of $P-M_{\\_}P$ has length at least
$\min\\{n_{\\_}0,|E(P)|\\}$ and less than $5n_{\\_}0$, and for each $i\in
X_{\\_}j$ we have $\operatorname{mdist}_{\\_}i(M_{\\_}P)>c$.

###### Proof.

We may assume that the length of $P$ is at least $5n_{\\_}0$, as otherwise the
lemma is satisfied by $M_{\\_}P=\varnothing$. Let $x$ and $y$ denote the ends
of $P$. Let $\\{P_{\\_}1,\ldots,P_{\\_}t\\}$ be an inclusion-maximal family of
pairwise vertex-disjoint subpaths of $P$ each of length $d$ such that
$\operatorname{dist}_{\\_}P(V(P_{\\_}\alpha),V(P_{\\_}\beta))\geqslant
n_{\\_}0$ for distinct $\alpha,\beta\in\\{1,\ldots,t\\}$, and
$\operatorname{dist}_{\\_}P(V(P_{\\_}\alpha),\\{x,y\\})\geqslant n_{\\_}0$ for
every $\alpha\in\\{1,\ldots,t\\}$. Since $n_{\\_}0>d$ and the length of $P$ is
at least $5n_{\\_}0$, we have $t>0$. Consider any maximal subpath
$P^{\prime}\subseteq P$ internally disjoint from each of the paths
$P_{\\_}1,\ldots,P_{\\_}t$. Then the length of $P^{\prime}$ is at least
$n_{\\_}0$. Since our family of paths is inclusion-maximal, the length of
$P^{\prime}$ is less than $d+2n_{\\_}0$ as otherwise we would be able to
extend our family with a path of length $d$ obtained from $P^{\prime}$ by
removing at least $n_{\\_}0$ vertices from each side. Since
$d+2n_{\\_}0<3n_{\\_}0$, we conclude that the length of any such $P^{\prime}$
is at least $n_{\\_}0$ and less than $3n_{\\_}0$.

We claim that each path $P_{\\_}\alpha$ contains an edge $e_{\\_}\alpha$ such
that for every $i\in X_{\\_}j$ we have
$\operatorname{mdist}_{\\_}i(e_{\\_}\alpha)>c$. Since $|X_{\\_}j|\leqslant 2$,
it suffices to show that for each $i\in X_{\\_}j$, there is less than $d/2$
edges $e\in E(P)$ with $\operatorname{mdist}_{\\_}i(e)\leqslant c$. Fix
$\alpha\in\\{1,\ldots,t\\}$ and $i\in X_{\\_}j$. Partition $M_{\\_}i$ into two
sets $M_{\\_}i^{\prime}$ and $M_{\\_}i^{\prime\prime}$ by assigning each edge
$e^{\prime}\in M_{\\_}i$ to $M_{\\_}i^{\prime}$ if
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(e^{\prime},V(P_{\\_}\alpha))\leqslant
c$, and to $M_{\\_}i^{\prime\prime}$ if
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(e^{\prime},V(P_{\\_}\alpha))>c$.
Since $M_{\\_}i$ is $(d+2c)$-independent in $B_{\\_}i-A_{\\_}i$, and the
length of $P_{\\_}\alpha$ is at most $d$, the set $M_{\\_}i^{\prime}$ contains
at most one edge.

For every $e^{\prime}\in M_{\\_}i^{\prime\prime}$, let $U_{\\_}{e^{\prime}}$
denote a subtree of $G$ on all vertices at distance at most $c$ from
$e^{\prime}$ in $B_{\\_}i-A_{\\_}i$ such that each $u\in
V(U_{\\_}{e^{\prime}})$ has the same distance from $e^{\prime}$ in
$U_{\\_}{e^{\prime}}$ as in $B_{\\_}i-A_{\\_}i$ (one can think of
$U_{\\_}{e^{\prime}}$ as a “bfs-spanning tree rooted at the edge
$e^{\prime}$”) Since the set $M_{\\_}i$ is $(d+2c)$-independent in
$B_{\\_}i-A_{\\_}i$, the trees $U_{\\_}{e^{\prime}}$ are pairwise vertex-
disjoint, and by definition of $M_{\\_}i^{\prime\prime}$ the trees
$U_{\\_}{e^{\prime}}$ are disjoint from the path $P_{\\_}\alpha$. For each
$e^{\prime}\in M_{\\_}i^{\prime\prime}$, let
$Z_{\\_}{e^{\prime}}:=N_{\\_}{B_{\\_}i}(V(U_{\\_}{e^{\prime}}))\cap A_{\\_}i$.
For each $z\in Z_{\\_}{e^{\prime}}$, define a $V(T_{\\_}i)$–$A_{\\_}i$ path
$Q(e^{\prime},z)$ as follows. Let $y$ be a vertex of $U_{\\_}{e^{\prime}}$
adjacent to $z$ in $B_{\\_}i$ which minimises
$\operatorname{dist}_{\\_}{U_{\\_}{e^{\prime}}}(e^{\prime},y)$ (and thus also
minimises $\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(e^{\prime},y)$). Let
$x$ be the vertex on the path between $y$ and $e^{\prime}$ which lies on
$V(T_{\\_}i)$ and minimises
$\operatorname{dist}_{\\_}{U_{\\_}{e^{\prime}}}(x,y)$ (this is well defined
since $e^{\prime}$ has both ends in $V(T_{\\_}i)$). Then the path
$Q(e^{\prime},z)$ is obtained from $xU_{\\_}{e^{\prime}}y$ by adding the
vertex $z$ attached to $y$. Each pair of distinct paths
$Q_{\\_}1=Q(e_{\\_}1^{\prime},z_{\\_}1)$ and
$Q_{\\_}2=Q(e_{\\_}2^{\prime},z_{\\_}2)$ is _consistent_ , meaning that if
their intersection $Q_{\\_}1\cap Q_{\\_}2$ is not empty, then $Q_{\\_}1\cap
Q_{\\_}2$ is a path with an end in a common end of $Q_{\\_}1$ and $Q_{\\_}2$.

Let $J$ denote the union of $T_{\\_}i$ and the paths $Q(e^{\prime},z)$ for all
$e^{\prime}\in M_{\\_}i^{\prime\prime}$ and $z\in Z_{\\_}{e^{\prime}}$. The
graph $J$ is a subgraph of $B_{\\_}i$ that intersects $A_{\\_}i$ only in the
sets $Z_{\\_}{e^{\prime}}$. Thus, all vertices in the sets
$Z_{\\_}{e^{\prime}}$ are incident with the outer face of $B_{\\_}i$. Let
$J^{+}$ denote the planar graph obtained from $J$ by adding a new vertex
$w_{\\_}+$ on the outer-face of $B_{\\_}i$ and making it adjacent to all
vertices in the sets $Z_{\\_}{e^{\prime}}$. See Figure 6.

Figure 6: Illustration of a possible scenario in Claim 13. The set
$M_{\\_}i^{\prime}$ consists of the edge $e^{\prime}$, and the boundary of the
face $f$ contains two paths $Q(e^{\prime}_{\\_}1,z_{\\_}1)$ and
$Q(e^{\prime}_{\\_}2,z_{\\_}2)$. Hence, $S=\\{e^{\prime}\\}\cup
E(Q(e^{\prime}_{\\_}1,z_{\\_}1))\cup E(Q(e^{\prime}_{\\_}2,z_{\\_}2))$.

Since $P_{\\_}\alpha\subseteq B_{\\_}i-A_{\\_}i$ and
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(V(P_{\\_}\alpha),M_{\\_}i^{\prime\prime})>c$,
the path $P_{\\_}\alpha$ is disjoint from $J^{+}$ and therefore the path
$P_{\\_}\alpha$ is contained in a face $f$ of $J^{+}$. Let $S$ denote the set
of all edges in $E(J)\setminus E(T_{\\_}i)$ on the boundary of $f$. Since the
paths $Q(e^{\prime},z)$ are pairwise consistent $V(T_{\\_}i)$–$A_{\\_}i$
paths, the edges in $S$ can be covered by the union of at most two paths of
the form $Q(e^{\prime},z)$. In particular, $|S|\leqslant 2c+2$.

We claim that for every $e\in E(P_{\\_}\alpha)$ with
$\operatorname{mdist}_{\\_}i(e)\leqslant c$ we have
$\operatorname{dist}_{\\_}{B_{\\_}i}(S\cup M_{\\_}i^{\prime},e)\leqslant c$.
Suppose that $\operatorname{mdist}_{\\_}i(e)\leqslant c$. Hence, there exist
$e^{\prime}\in M_{\\_}i$ and $v\in V(T_{\\_}i)\setminus V(T_{\\_}i^{0})$ that
satisfy
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(e^{\prime},v)+\operatorname{dist}_{\\_}{B_{\\_}i-V(T_{\\_}i^{0})}(v,e)\leqslant
c$. If $e^{\prime}\in M_{\\_}i^{\prime}$, then we indeed have
$\operatorname{dist}_{\\_}{B_{\\_}i}(S\cup M_{\\_}i^{\prime},e)\leqslant c$,
so we assume that $e^{\prime}\in M_{\\_}i^{\prime\prime}$. Let $R$ be a
shortest path between $v$ and $e$ in $B_{\\_}i-V(T_{\\_}i^{0})$. Since
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(e,e^{\prime})>c$, the path $R$
must intersect $A_{\\_}i$. Let $z$ be the vertex of $R$ that belongs to
$A_{\\_}i$ and is closest to $v$ on $R$. Hence, $z\in Z_{\\_}{e^{\prime}}$.
Since $J^{+}$ contains $Q(e^{\prime},z)$, the path $Q(e^{\prime},z)$ is
disjoint from the interior of $f$. Therefore, the subpath of $R$ between $z$
and $e$ must intersect the boundary of $f$ in a vertex $u$, and since $R$ is
disjoint from $T_{\\_}i^{0}$, the vertex $u$ is an end of an edge in $S$.
Therefore, $\operatorname{dist}_{\\_}{B_{\\_}i}(S,e)\leqslant c$. This
completes the proof that for every $e\in E(P_{\\_}\alpha)$, if
$\operatorname{mdist}_{\\_}i(e)\leqslant c$, then
$\operatorname{dist}_{\\_}{B_{\\_}i}(S\cup M_{\\_}i^{\prime},e)\leqslant c$.
Since $|S\cup M_{\\_}i^{\prime}|\leqslant|S|+|M_{\\_}i^{\prime}|\leqslant
2c+3$, for each $i\in X_{\\_}j$ there exist less than $(4c+6)\Delta^{c+2}$
edges $e\in E(P_{\\_}\alpha)$ with $\operatorname{mdist}_{\\_}i(e)\leqslant
c$. Since $|X_{\\_}j|\leqslant 2$ and the length of $P_{\\_}\alpha$ is
$(8c+12)\Delta^{c+2}$, for each $\alpha\in\\{1,\ldots,t\\}$ there exists an
edge $e_{\\_}\alpha\in E(P_{\\_}\alpha)$ such that
$\operatorname{mdist}_{\\_}i(e_{\\_}\alpha)>c$ for all $i\in X_{\\_}j$.

Let $M_{\\_}P:=\\{e_{\\_}1,\ldots,e_{\\_}t\\}$. Thus,
$\operatorname{mdist}_{\\_}i(M_{\\_}P)>c$ for each $i\in X_{\\_}j$. Since the
distance between any two of the paths $P_{\\_}1,\ldots,P_{\\_}t$ is at least
$n_{\\_}0$ on $P$, the set $M_{\\_}P$ is $n_{\\_}0$-independent in $P$.
Because $P$ is geodesic in $B_{\\_}j-A_{\\_}j$ and $n_{\\_}0\geqslant d+2c$,
the set $M_{\\_}P$ is $(d+2c)$-independent in $B_{\\_}j-M_{\\_}j$.

It remains to show that the components of $P-M_{\\_}P$ have appropriate sizes.
Let $Q$ be a component of $P-M_{\\_}P$. Since $M_{\\_}P$ contains one edge
from each of the subpaths $P_{\\_}1,\ldots,P_{\\_}t$, the path $Q$ intersects
at most two of the paths $P_{\\_}1,\ldots,P_{\\_}t$, and the total number of
edges of $Q$ shared with $P_{\\_}1,\ldots,P_{\\_}t$ is at most $2d$, and thus
less than $2n_{\\_}0$. The edges of $Q$ that do not belong to any of the paths
$P_{\\_}1,\ldots,P_{\\_}t$ induce a maximal subpath of $P$ internally disjoint
from each of the paths $P_{\\_}1,\ldots,P_{\\_}t$, which thus has length at
least $n_{\\_}0$ and less than $3n_{\\_}0$. Hence, the length of $P^{\prime}$
is at least $n_{\\_}0$ and less than $5n_{\\_}0$. ∎

Finally, we are ready to construct the sets $M_{\\_}j$.

######  Claim 14.

Let $c\geqslant 1$ and $d:=(8c+12)\Delta^{c+2}$. There exists a family
$\\{M_{\\_}j\subseteq E(T_{\\_}j^{0}):j\in\\{1,\ldots,m\\}\\}$ such that for
every $j\in\\{1,\ldots,m\\}$:

  1. ()

$M_{\\_}j$ is $(d+2c)$-independent in $B_{\\_}j-A_{\\_}j$,

  2. ()

$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(D_{\\_}j,M_{\\_}j)\geqslant
2\Delta^{40}$,

  3. ()

for each $i\in X_{\\_}j$, $\operatorname{mdist}_{\\_}i(M_{\\_}j)>c$,

  4. ()

each component of $T_{\\_}j^{0}-M_{\\_}j$ has at most $10\Delta^{80}(d+2c)$
vertices, and

  5. ()

for any pair of vertices $x,y\in V(T_{\\_}j^{0})$ satisfying
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}{j}}(x,y)\leqslant d+2c$ and
$E(xT_{\\_}j^{0}y)\cap M_{\\_}j\neq\varnothing$, we have
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x,y)=\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x,y)$.

###### Proof.

Let $n_{\\_}0:=\Delta^{40}(d+2c)$.

We construct the sets $M_{\\_}j$ by induction on $j$. Let
$j\in\\{1,\ldots,m\\}$, and suppose that the sets $M_{\\_}i$ with $i<j$ have
already been constructed. In particular, each $M_{\\_}i$ is
$(d+2c)$-independent in $B_{\\_}i-A_{\\_}i$. We now construct $M_{\\_}j$.

By Claim 11 there is a family $\mathcal{P}_{\\_}j$ of at most $2\Delta^{40}$
pairwise internally disjoint geodesic paths in $B_{\\_}j-A_{\\_}j$ whose union
is $T_{\\_}j^{0}$, and which are internally disjoint from $D_{\\_}j$.

For each $P\in\mathcal{P}_{\\_}j$, let $M_{\\_}P\subseteq E(P)$ be the subset
of edges obtained by applying Claim 13 to $c$, $n_{\\_}0$ and $P$. Thus,
$M_{\\_}P$ is $(d+2c)$-independent in $B_{\\_}j-A_{\\_}j$,
$\operatorname{mdist}_{\\_}i(M_{\\_}P)>c$ for each $i\in X_{\\_}j$, and each
component of $P-M_{\\_}P$ is a path of length at least
$\min\\{n_{\\_}0,|E(P)|\\}$ and less than $5n_{\\_}0$.

We show that the set $M_{\\_}j:=\bigcup\\{M_{\\_}P:P\in\mathcal{P}_{\\_}j\\}$
satisfies the claim. For the proof of Item 1, we need to show that $M_{\\_}j$
is $(d+2c)$-independent in $B_{\\_}j-A_{\\_}j$. Suppose towards a
contradiction that there are distinct $e_{\\_}1,e_{\\_}2\in M_{\\_}j$ with
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e_{\\_}1,e_{\\_}2)\leqslant
d+2c$. By Claim 12,

$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(e_{\\_}1,e_{\\_}2)<\Delta^{40}\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e_{\\_}1,e_{\\_}2)\leqslant\Delta^{40}(d+2c)=n_{\\_}0.$

However, if $P\in\mathcal{P}_{\\_}j$ is the path containing $e_{\\_}1$, then
the shortest path between $e_{\\_}1$ and $e_{\\_}2$ in $T_{\\_}j^{0}$ contains
a component of $P-M_{\\_}P$, and therefore has length at least
$\min\\{n_{\\_}0,|E(P)|\\}=n_{\\_}0$ (since $e_{\\_}1\in E(P)$); that is,
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(e_{\\_}1,e_{\\_}2)\geqslant
n_{\\_}0$, a contradiction.

For any $P\in\mathcal{P}_{\\_}j$ and $e\in M_{\\_}P$, the distance between $e$
and the ends of $P$ is at least $n_{\\_}0=\Delta^{40}(d+2c)$, and therefore at
least $2\Delta^{40}$. Since the paths in $\mathcal{P}_{\\_}j$ are pairwise
internally disjoint, and internally disjoint from $D_{\\_}j$, this implies
that $\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(D_{\\_}j,M_{\\_}j)\geqslant
2\Delta^{40}$. Therefore Item 2 is satisfied.

By definition of the sets $M_{\\_}P$, for any $P\in\mathcal{P}_{\\_}j$ and
$i\in X_{\\_}j$ we have $\operatorname{mdist}_{\\_}i(M_{\\_}P)>c$, and
therefore for each $i\in X_{\\_}j$ we have
$\operatorname{mdist}_{\\_}i(M_{\\_}j)>c$. This proves Item 3.

For Item 4, observe that if a component $T^{\prime}$ of
$T_{\\_}j^{0}-M_{\\_}j$ intersects a path $P\in\mathcal{P}_{\\_}j$, then
$T^{\prime}\cap P$ is a component of $P-M_{\\_}P$, so it has less than
$5n_{\\_}0$ edges, and therefore at most $5n_{\\_}0$ vertices. Hence,

$\displaystyle|V(T^{\prime})|$
$\displaystyle\leqslant|\mathcal{P}_{\\_}j|\cdot 5n_{\\_}0\leqslant
2\Delta^{40}\cdot 5\Delta^{40}(d+2c)=10\Delta^{80}(d+2c).$

Finally, for the proof of Item 5, let $x,y\in V(T_{\\_}j^{0})$ be vertices
satisfying $\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x,y)\leqslant d+2c$
and $E(xT_{\\_}j^{0}y)\cap M_{\\_}j\neq\varnothing$. Let $e\in
E(xT_{\\_}j^{0}y)\cap M_{\\_}j$, and let $P\in\mathcal{P}_{\\_}j$ be the path
containing $e$. By Claim 12,

$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x,y)<\Delta^{40}\cdot\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x,y)\leqslant\Delta^{40}\cdot(d+2c)=n_{\\_}0.$

If at least one of $x,y$ is not in $V(P)$, then the path $xT_{\\_}j^{0}y$
contains some component of $P-M_{\\_}P$, and thus has length at least
$n_{\\_}0$, which is a contradiction. Therefore, we conclude that $x$ and $y$
are in $P$, and since $P$ is geodesic in $B_{\\_}j-A_{\\_}j$, we have
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x,y)=\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x,y)$.
∎

##  6 Analysis of the Partition

Let $\ell:=222$, and let $c:=2\ell+6=450$. Fix a family
$\\{M_{\\_}j:j\in\\{1,\ldots,m\\}\\}$ satisfying Claim 14 for our value of
$c$. Let $\mathcal{R}$ denote the partition of $V(G)$ where each part is the
vertex-set of a component of $\bigcup_{\\_}{j=1}^{m}(T_{\\_}j-M_{\\_}j)$. By
Claim 144, for each $j\in\\{1,\ldots,m\\}$, the size of every component of
$T_{\\_}j^{0}-M_{\\_}j$ is at most
$10\Delta^{80}((8c+12)\Delta^{c+2}+2c)=10\Delta^{80}(3612\,\Delta^{452}+900)$.
Since each component of $T_{\\_}j-M_{\\_}j$ can be obtained from a component
of $T_{\\_}j^{0}-M_{\\_}j$ by attaching at most $\Delta$ vertices to each
vertex of the component, the width of $\mathcal{R}$ is at most
$(\Delta+1)\cdot 10\Delta^{80}(3612\,\Delta^{452}+900)$.

To complete the proof of Theorem 16, we show that $\mathcal{R}$ is
$\ell$-blocking; that is, no $\mathcal{R}$-clean path in $G$ has length
greater than $\ell$. Since a subpath of an $\mathcal{R}$-clean path is
$\mathcal{R}$-clean, it suffices to show that there is no $\mathcal{R}$-clean
path of length exactly $\ell+1$, so in our analysis we focus only on paths of
length at most $\ell+1$.

We start by proving some properties of $\mathcal{R}$-clean paths.

######  Claim 15.

Let $j\in\\{1,\ldots,m\\}$, and let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be an
$\mathcal{R}$-clean path in $B_{\\_}j-A_{\\_}j$ with
$\\{x_{\\_}0,x_{\\_}q\\}\subseteq V(T_{\\_}j)$ and
$q\in\\{1,\ldots,\ell+1\\}$. Then $E(x_{\\_}0T_{\\_}jx_{\\_}q)\cap
M_{\\_}j\neq\varnothing$, and for each $e\in E(x_{\\_}0T_{\\_}jx_{\\_}q)\cap
M_{\\_}j$ we have
$\operatorname{dist}_{\\_}{T_{\\_}j}(e,x_{\\_}\alpha)\leqslant q+2$ for
$\alpha\in\\{0,q\\}$. In particular,

$\operatorname{dist}_{\\_}{T_{\\_}j}(M_{\\_}j,x_{\\_}\alpha)\leqslant
q+2\quad\textrm{for $\alpha\in\\{0,q\\}$}.$

###### Proof.

For each $\alpha\in\\{0,q\\}$, let $x_{\\_}\alpha^{\prime}$ denote the vertex
$x_{\\_}\alpha$ if $x_{\\_}\alpha\in V(T_{\\_}j^{0})$, or the vertex in
$V(T_{\\_}j^{0})$ that is adjacent to $x_{\\_}\alpha$ in $T_{\\_}j$ if
$x_{\\_}\alpha\not\in V(T_{\\_}j^{0})$. Hence, $x_{\\_}\alpha^{\prime}$ in the
same part of $\mathcal{R}$ as $x_{\\_}\alpha$ and
$\operatorname{dist}_{\\_}{T_{\\_}j}(x_{\\_}\alpha^{\prime},x_{\\_}\alpha)\leqslant
1$. In order to apply Claim 145 to $x_{\\_}0^{\prime}$ and
$x_{\\_}q^{\prime}$, observe that

$\displaystyle\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}0^{\prime},x_{\\_}q^{\prime})$
$\displaystyle\leqslant\operatorname{dist}_{\\_}{T_{\\_}j}(x_{\\_}0^{\prime},x_{\\_}0)+\operatorname{dist}_{\\_}Q(x_{\\_}0,x_{\\_}q)+\operatorname{dist}_{\\_}{T_{\\_}j}(x_{\\_}q,x_{\\_}q^{\prime})$
$\displaystyle\leqslant q+2$ $\displaystyle\leqslant\ell+3$
$\displaystyle<(8c+12)\Delta^{c+2}+2c.$

Furthermore, since $Q$ is $\mathcal{R}$-clean, the part of $\mathcal{R}$
containing $x_{\\_}0$ and $x_{\\_}0^{\prime}$ is distinct from the part
containing $x_{\\_}q$ and $x_{\\_}q^{\prime}$, so
$E(x_{\\_}0^{\prime}T_{\\_}j^{0}x_{\\_}q^{\prime})\cap
M_{\\_}j\neq\varnothing$. Therefore, by Claim 145,

$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(x_{\\_}0^{\prime},x_{\\_}q^{\prime})=\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}0^{\prime},x_{\\_}q^{\prime})\leqslant
q+2.$

Since $M_{\\_}j\subseteq E(T_{\\_}j^{0})$, we have
$E(x_{\\_}0T_{\\_}jx_{\\_}q)\cap
M_{\\_}j=E(x_{\\_}0^{\prime}T_{\\_}j^{0}x_{\\_}q^{\prime})\cap
M_{\\_}j\neq\varnothing$. Let $e\in
E(x_{\\_}0^{\prime}T_{\\_}j^{0}x_{\\_}q^{\prime})\cap M_{\\_}j$. The length of
the path $x_{\\_}0^{\prime}T_{\\_}j^{0}x_{\\_}q^{\prime}$ is at most $q+2$, so
for each $\alpha\in\\{0,q\\}$ we have
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(e,x_{\\_}\alpha^{\prime})\leqslant
q+1$, and therefore

$\operatorname{dist}_{\\_}{T_{\\_}j}(e,x_{\\_}\alpha)=\operatorname{dist}_{\\_}{T_{\\_}j}(e,x_{\\_}\alpha^{\prime})+\operatorname{dist}_{\\_}{T_{\\_}j}(x_{\\_}\alpha^{\prime},x_{\\_}\alpha)\leqslant(q+1)+1=q+2.\qed$

######  Claim 16.

Let $j\in\\{1,\ldots,m\\}$, and let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be a
$\mathcal{R}$-clean path in $B_{\\_}j$ with $q\in\\{0,\ldots,\ell+1\\}$ that
is internally disjoint from $A_{\\_}j$. Then $|V(Q)\cap V(T_{\\_}j)|\leqslant
2$.

###### Proof.

Suppose to the contrary that there exist distinct vertices
$y_{\\_}1,y_{\\_}2,y_{\\_}3\in V(Q)\cap V(T_{\\_}j)$. Since $T_{\\_}j\subseteq
B_{\\_}j-A_{\\_}j$ and $Q$ is internally disjoint from $A_{\\_}j$, each
subpath of $Q$ between two of the vertices $y_{\\_}1,y_{\\_}2,y_{\\_}3$ is
contained in $B_{\\_}j-A_{\\_}j$. By Claim 15 applied to $y_{\\_}1Qy_{\\_}2$,
there exists an edge $e\in E(y_{\\_}1T_{\\_}jy_{\\_}2)\cap M_{\\_}j$ with
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e,y_{\\_}1)\leqslant q+2$ and
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e,y_{\\_}2)\leqslant q+2$.
Without loss of generality, $y_{\\_}3$ belongs to the same component of
$T_{\\_}j-e$ as $y_{\\_}1$, and therefore $e\not\in
E(y_{\\_}1T_{\\_}jy_{\\_}3)$. By Claim 15 applied to $y_{\\_}1Qy_{\\_}3$,
there exists an edge $e^{\prime}\in E(y_{\\_}1T_{\\_}jy_{\\_}3)\cap M_{\\_}j$
with
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e^{\prime},y_{\\_}1)\leqslant
q+2$. Therefore, $e\neq e^{\prime}$, and

$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e,e^{\prime})\leqslant\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(e,y_{\\_}1)+\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(y_{\\_}1,e^{\prime})\leqslant
2(q+2)\leqslant 2\ell+6=c,$

which contradicts Claim 141. ∎

######  Claim 17.

Let $j\in\\{1,\ldots,m\\}$, and let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be an
$\mathcal{R}$-clean path in $B_{\\_}j$ with $q\in\\{0,\ldots,\ell+1\\}$ that
is internally disjoint from $A_{\\_}j$, such that $x_{\\_}0$ is an attachment-
vertex of $B_{\\_}j$ on a tree $T_{\\_}i$ with $i\in X_{\\_}j$ and
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(x_{\\_}0,M_{\\_}i)\leqslant\ell+3$.
Then $|V(Q)\cap V(T_{\\_}j)|\leqslant 1$.

###### Proof.

Suppose to the contrary that $|V(Q)\cap V(T_{\\_}j)|>1$. Hence, by Claim 16,
we have $|V(Q)\cap V(T_{\\_}j)|=2$, say $V(Q)\cap
V(T_{\\_}j)=\\{x_{\\_}\alpha,x_{\\_}\beta\\}$ for some
$\alpha,\beta\in\\{0,\ldots,q\\}$ with $\alpha<\beta$. Since $x_{\\_}0\in
V(T_{\\_}i)$, we have $\alpha\geqslant 1$. Since
$\\{x_{\\_}\alpha,x_{\\_}\beta\\}\subseteq V(T_{\\_}j)\subseteq
B_{\\_}j-A_{\\_}j$ and $Q$ is internally disjoint from $A_{\\_}j$, we have
$x_{\\_}1Qx_{\\_}\beta\subseteq B_{\\_}j-A_{\\_}j$. By Claim 15 applied to
$x_{\\_}\alpha Qx_{\\_}\beta$, we have

$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}\alpha,M_{\\_}j)\leqslant\beta-\alpha+2\leqslant
q-\alpha+2\leqslant\ell-\alpha+3.$

The vertex $x_{\\_}0$ is an attachment-vertex of $B_{\\_}j$ in $V(T_{\\_}i)$,
$i\in X_{\\_}j$, and by Claim 5, we have $B_{\\_}j\subseteq B_{\\_}i$, and by
Claim 3, $B_{\\_}j$ has no attachment-vertices in $V(T_{\\_}i^{0})$, so
$B_{\\_}j-A_{\\_}j\subseteq B_{\\_}j\subseteq B_{\\_}i-V(T_{\\_}i^{0})$.
Therefore,

$\displaystyle\operatorname{mdist}_{\\_}i(M_{\\_}j)$
$\displaystyle\leqslant\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(M_{\\_}i,x_{\\_}0)+\operatorname{dist}_{\\_}{B_{\\_}i-V(T_{\\_}i^{0})}(x_{\\_}0,M_{\\_}j)$
$\displaystyle\leqslant(\ell+3)+(\operatorname{dist}_{\\_}{B_{\\_}j}(x_{\\_}0,x_{\\_}\alpha)+\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}\alpha,M_{\\_}j))$
$\displaystyle\leqslant(\ell+3)+\alpha+(\ell-\alpha+3)=2\ell+6=c.$

This contradicts Claim 143. ∎

Next, we bound the length of $\mathcal{R}$-clean paths in some special cases.
Recall that $F_{\\_}j=\bigcup_{\\_}{i<j}T_{\\_}i$.

######  Claim 18.

Let $i,j\in\\{1,\ldots,m\\}$ with $i<j$, and let $Q=x_{\\_}0\cdots x_{\\_}q$
be an $\mathcal{R}$-clean path with $q\in\\{1,\ldots,\ell+1\\}$, $x_{\\_}0\in
V(T_{\\_}i)$, $x_{\\_}q\in V(T_{\\_}j)$, and $V(Q)\cap
V(F_{\\_}j)=\\{x_{\\_}0,x_{\\_}q\\}$. Then

  1. ()

if
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(x_{\\_}0,M_{\\_}i)\leqslant\ell+3$
or
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}q,M_{\\_}j)\leqslant\ell+3$,
then $q\leqslant 2$;

  2. ()

otherwise, $q\leqslant 4$.

###### Proof.

Since $V(Q)\cap V(F_{\\_}j)=\\{x_{\\_}0,x_{\\_}q\\}$, the path $Q$ is
contained in some $F_{\\_}j$-bridge. If that $F_{\\_}j$-bridge is trivial,
then $q=1$ and the claim follows. Hence, $Q$ is contained in a non-trivial
$F_{\\_}j$-bridge, which equals $B_{\\_}k$ for some $k>j$ by Claim 6. By Claim
2, the set $V(T_{\\_}k^{0})$ separates the vertices $x_{\\_}0$ and $x_{\\_}q$
in $B_{\\_}k$, so some inner vertex of $Q$ must lie on $T_{\\_}k^{0}$.

Let $x_{\\_}{\alpha}$ be an inner vertex of $Q$ in $V(T_{\\_}k^{0})$. Since
the vertices $x_{\\_}{\alpha-1}$ and $x_{\\_}{\alpha+1}$ are adjacent to
$V(T_{\\_}k^{0})$ in $B_{\\_}k$, they belong to $A_{\\_}k\cup V(T_{\\_}k)$.
Since the only attachment-vertices of $B_{\\_}k$ on $Q$ are $x_{\\_}0\in
V(T_{\\_}i)$ and $x_{\\_}q\in V(T_{\\_}j$), we conclude that
$x_{\\_}{\alpha-1}\in\\{x_{\\_}0\\}\cup V(T_{\\_}k)$ and
$x_{\\_}{\alpha+1}\in\\{x_{\\_}q\\}\cup V(T_{\\_}k)$. By Claim 16, we have
$|V(Q)\cap V(T_{\\_}k)|\leqslant 2$. Since $x_{\\_}\alpha\in
V(T_{\\_}k^{0})\subseteq V(T_{\\_}k)$, at most one of the vertices
$x_{\\_}{\alpha-1}$ and $x_{\\_}{\alpha+1}$ lies on $T_{\\_}k$. In particular,
$x_{\\_}{\alpha-1}=x_{\\_}0$ or $x_{\\_}{\alpha+1}=x_{\\_}q$, so
$\alpha\in\\{1,q-1\\}$. If $x_{\\_}{\alpha-1}=x_{\\_}0$ and
$x_{\\_}{\alpha+1}=x_{\\_}q$, then $\alpha=1$ and $q=2$, and the claim holds.
Hence we may assume that one of $x_{\\_}{\alpha-1}$ and $x_{\\_}{\alpha+1}$
lies on $T_{\\_}k$, and therefore $V(Q)\cap
V(T_{\\_}k)=\\{x_{\\_}1,x_{\\_}2\\}$ or $V(Q)\cap
V(T_{\\_}k)=\\{x_{\\_}{q-2},x_{\\_}{q-1}\\}$. Thus, there exists
$\beta\in\\{1,q-2\\}$ such that $V(Q)\cap
V(T_{\\_}k)=\\{x_{\\_}\beta,x_{\\_}{\beta+1}\\}$. By Claim 15 applied to the
path $x_{\\_}\beta Qx_{\\_}{\beta+1}$, we have
$\operatorname{dist}_{\\_}{B_{\\_}k-A_{\\_}k}(x_{\\_}\beta,M_{\\_}k)\leqslant
3$ and
$\operatorname{dist}_{\\_}{B_{\\_}k-A_{\\_}k}(x_{\\_}{\beta+1},M_{\\_}k)\leqslant
3$.

For the proof of Item 1, suppose that
$\operatorname{dist}_{\\_}{B_{\\_}i-A_{\\_}i}(x_{\\_}0,M_{\\_}i)\leqslant\ell+3$
or
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}q,M_{\\_}j)\leqslant\ell+3$.
Hence, by Claim 17, we have $|V(Q)\cap V(T_{\\_}k)|=1$, so
$x_{\\_}{\alpha-1}=x_{\\_}0$ and $x_{\\_}{\alpha+1}=x_{\\_}q$, and therefore
$q=2$. This proves Item 1.

Next, we show Item 2. Suppose that $\beta=1$. Then $x_{\\_}q\in V(T_{\\_}j)$,
$x_{\\_}2\in V(T_{\\_}k)$, $V(x_{\\_}2Qx_{\\_}q)\cap
V(F_{\\_}k)=\\{x_{\\_}q,x_{\\_}2\\}$, and
$\operatorname{dist}_{\\_}{B_{\\_}k-A_{\\_}k}(x_{\\_}2,M_{\\_}k)\leqslant
3<\ell+3$. Hence, by 1, the length of $x_{\\_}2Qx_{\\_}q$ is at most $2$, and
therefore $q\leqslant 4$. The case when $\beta=q-2$ is similar: We have
$x_{\\_}0\in V(T_{\\_}i)$, $x_{\\_}{q-2}\in V(T_{\\_}k)$,
$V(x_{\\_}0Qx_{\\_}{q-2})\cap V(F_{\\_}k)=\\{x_{\\_}0,x_{\\_}{q-2}\\}$, and
$\operatorname{dist}_{\\_}{B_{\\_}k-A_{\\_}k}(x_{\\_}{q-2},(M_{\\_}k))\leqslant
3<\ell+3$. Hence, by 1, the length of $x_{\\_}0Qx_{\\_}{q-2}$ is at most $2$,
so $q\leqslant 4$. This completes the proof of 2. ∎

######  Claim 19.

Let $i\in\\{1,\ldots,m\\}$, and let $Q=x_{\\_}0\cdots x_{\\_}q$ be an
$\mathcal{R}$-clean path with $q\in\\{0,\ldots,\ell+1\\}$ and
$\\{x_{\\_}0,x_{\\_}q\\}\subseteq V(Q)\cap V(F_{\\_}i)\subseteq V(T_{\\_}i)$.
Then $q\leqslant 4$.

###### Proof.

If $q=0$, then the claim holds trivially, so we assume that $x_{\\_}0\neq
x_{\\_}q$. By Claim 16, we have $|V(Q)\cap V(F_{\\_}i)|\leqslant 2$, so
$V(Q)\cap V(F_{\\_}i)=\\{x_{\\_}0,x_{\\_}q\\}$. Since $(V(T_{\\_}j)\colon
j\in\\{1,\dots,m\\})$ is a partition of $V(G)$, each inner vertex of $Q$
belongs to some tree $T_{\\_}j$ with $j>i$. Let $T_{\\_}j$ be the tree
containing an inner vertex of $Q$ with the smallest $j$. Thus, $Q$ intersects
$F_{\\_}{j-1}$ only in its ends, and $B_{\\_}j$ is the $F_{\\_}{j-1}$-bridge
containing $Q$. By Claim 5, $B_{\\_}j\subseteq B_{\\_}i$. Since $B_{\\_}j$ has
attachment-vertices in $V(T_{\\_}i)$, we have $i\in X_{\\_}j$. By Claim 15, we
have $\operatorname{dist}_{\\_}{T_{\\_}i}(x_{\\_}0,M_{\\_}i)\leqslant
q+2\leqslant\ell+3$ and
$\operatorname{dist}_{\\_}{T_{\\_}i}(x_{\\_}q,M_{\\_}i)\leqslant
q+2\leqslant\ell+3$. Hence, by Claim 17, we have $|V(Q)\cap V(T_{\\_}j)|=1$,
say $V(Q)\cap V(T_{\\_}j)=\\{x_{\\_}\alpha\\}$. By Claim 18Item 1, each of the
paths $x_{\\_}0Qx_{\\_}\alpha$ and $x_{\\_}\alpha Qx_{\\_}q$ has length at
most $2$, so $q\leqslant 4$. ∎

For each $j\in\\{1,\ldots,m\\}$, the graph $B_{\\_}j$ intersects at most three
components of $F_{\\_}j$, namely, $T_{\\_}j$ and at most two components of
$F_{\\_}{j-1}$ on which $B_{\\_}j$ has attachment-vertices. We aim to show
that every $\mathcal{R}$-clean path in $B_{\\_}j$ with both ends on $F_{\\_}j$
has length at most $36$ (the value $\tau=37$ was chosen to be greater than
this bound). We first prove the following helper claim.

######  Claim 20.

Let $i,j\in\\{1,\ldots,m\\}$ with $i<j$, let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be
an $\mathcal{R}$-clean path in $B_{\\_}j$ with $q\in\\{0,\ldots,\ell+1\\}$,
$V(Q)\cap V(T_{\\_}i)=\\{x_{\\_}0\\}$ and $x_{\\_}q\in V(F_{\\_}j)$. Then
$q\leqslant 8(a-1)$, where $a\in\\{1,2,3\\}$ is the number of components of
$F_{\\_}j$ that intersect $Q$.

###### Proof.

If $a=1$, then since $V(Q)\cap V(T_{\\_}i)=\\{x_{\\_}0\\}$, the only component
of $F_{\\_}j$ intersecting $Q$ is $T_{\\_}i$, and thus $x_{\\_}q=x_{\\_}0$, so
$q=0=8(a-1)$. Hence, we assume that $a\geqslant 2$. Let $T_{\\_}{i^{\prime}}$
be the component of $F_{\\_}j$ that contains a vertex of $Q$, is distinct from
$T_{\\_}i$ and has $i^{\prime}$ as small as possible. Let $x_{\\_}\alpha$ and
$x_{\\_}\beta$ denote respectively the first and the last vertex of $Q$ in
$V(T_{\\_}{i^{\prime}})$. By Claim 18, the length of $x_{\\_}0Qx_{\\_}\alpha$
is at most $4$, and by Claim 19, the length of $x_{\\_}\alpha Qx_{\\_}{\beta}$
is also at most $4$. Hence, $\beta\leqslant 8$. If $i^{\prime}=j$, then by our
choice of $i^{\prime}$, we have $V(Q)\cap
V(F_{\\_}j)\subseteq\\{x_{\\_}0\\}\cup V(T_{\\_}j)$, so $x_{\\_}q\in
V(T_{\\_}j)$, and therefore $q=\beta\leqslant 8\leqslant 8(a-1)$. Hence,
assume that $i^{\prime}\neq j$ which means that $i^{\prime}\in X_{\\_}j$. The
path $Q$ intersects $T_{\\_}i$ and $T_{\\_}{i^{\prime}}$, and by Claim 2 it
intersects also $T_{\\_}j$, so $a=3$. We have $V(x_{\\_}\beta Qx_{\\_}q)\cap
V(T_{\\_}{i^{\prime}})=\\{x_{\\_}\beta\\}$, and the path $x_{\\_}\beta
Qx_{\\_}q$ intersects at most two components of $F_{\\_}j$, so we already know
that its length is at most $8(2-1)=8$, so $q\leqslant\beta+8\leqslant
16=8(a-1)$. ∎

######  Claim 21.

Let $j\in\\{1,\ldots,m\\}$, and let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be an
$\mathcal{R}$-clean path in $B_{\\_}j$ with $p\in\\{0,\ldots,\ell+1\\}$ such
that $\\{x_{\\_}0,x_{\\_}p\\}\subseteq V(F_{\\_}j)$. Then $q\leqslant 36$.

###### Proof.

Let $T_{\\_}i$ be the tree intersecting $Q$ with the smallest $i$. So $i\in
X_{\\_}j\cup\\{j\\}$. Let $x_{\\_}\alpha$ and $x_{\\_}\beta$ denote the first
and the last vertex of $Q$ in $V(T_{\\_}i)$. By Claim 19, the length of
$x_{\\_}\alpha Qx_{\\_}\beta$ is at most $4$. If $i=j$, then $\alpha=0$ and
$\beta=q$, so $q\leqslant 4$. Therefore, we assume that $i<j$. We have
$V(x_{\\_}0Qx_{\\_}{\alpha})\cap V(T_{\\_}i)=\\{x_{\\_}\alpha\\}$ and
$V(x_{\\_}\beta Qx_{\\_}q)\cap V(T_{\\_}i)=\\{x_{\\_}\beta\\}$. Hence, by
Claim 20, each of the paths $x_{\\_}0Qx_{\\_}\alpha$ and $x_{\\_}\beta
Qx_{\\_}q$ has length at most $16$, which implies that $q\leqslant
16+4+16=36$. ∎

We proceed to the main part of the proof of Theorem 16. Towards a
contradiction, assume that $\mathcal{R}$ is not $\ell$-blocking. Hence, there
exists an $\mathcal{R}$-clean path $P=(x_{\\_}0,\ldots,x_{\\_}p)$ with
$p>\ell$. Every subpath of an $\mathcal{R}$-clean path is $\mathcal{R}$-clean,
so we may assume without loss of generality that the length of $P$ is exactly
$\ell+1$. Let $T_{\\_}i$ be the tree intersecting $Q$ that has the smallest
$i$. Let $x_{\\_}\alpha$ and $x_{\\_}\beta$ denote respectively the first and
the last vertex of $Q$ belonging to $T_{\\_}i$. By Claim 19, the length of
$x_{\\_}\alpha Px_{\\_}\beta$ is at most $4$. Hence, there exists
$Q\in\\{x_{\\_}0Px_{\\_}\alpha,x_{\\_}\beta Px_{\\_}p\\}$ with length at least
$\lceil((\ell+1)-4)/2\rceil=110$. The path $Q$ intersect $V(F_{\\_}i)$ only in
one of its ends, and that end lies on $T_{\\_}i$. Therefore, to reach a
contradiction and complete the proof it suffices to show the following claim.

######  Claim 22.

Let $i\in\\{1,\ldots,m\\}$, and let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be an
$\mathcal{R}$-clean path with $q\in\\{0,\ldots,\ell+1\\}$ and $V(Q)\cap
V(F_{\\_}i)=\\{x_{\\_}0\\}\subseteq V(T_{\\_}i)$. Then $q\leqslant 109$.

Claim 22 is a consequence of the following technical claim.

######  Claim 23.

Let $i\in\\{1,\ldots,m\\}$, let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be an
$\mathcal{R}$-clean path contained in an $F_{\\_}i$-bridge such that
$q\in\\{74,\ldots,\ell+1\\}$ and $V(Q)\cap V(T_{\\_}i)=\\{x_{\\_}0\\}$. Then

  1. ()

there exist $i^{\prime}\in\\{1,\ldots,m\\}$ and an $\mathcal{R}$-clean path
$Q^{\prime}=(x_{\\_}0^{\prime},\ldots,x_{\\_}{q^{\prime}}^{\prime})$ contained
in an $F_{\\_}{i^{\prime}}$-bridge such that
$q^{\prime}\in\\{q-36,\ldots,\ell+1\\}$, $V(Q^{\prime})\cap
V(T_{\\_}{i^{\prime}})=\\{x_{\\_}0^{\prime}\\}$ and
$\operatorname{mdist}_{\\_}{i^{\prime}}(x_{\\_}0^{\prime})\leqslant 39$, and

  2. ()

there exist $j\in\\{i+1,\ldots,m\\}$ such that $i\in X_{\\_}j$ and
$\operatorname{dist}_{\\_}{B_{\\_}i-V(T_{\\_}{i}^{0})}(x_{\\_}0,M_{\\_}j)\leqslant
42$.

Before proving Claim 23, we show how it implies Claim 22.

###### Proof of Claim 22 assuming Claim 23.

Towards a contradiction, suppose that $q\geqslant 110$. We will apply Claim
23Item 1 to $(i,Q)$ to obtain a pair $(i^{\prime},Q^{\prime})$, and then we
will apply Claim 23Item 2 to $(i^{\prime},Q^{\prime})$ to obtain an index
$j^{\prime}$ with contradictory properties.

We have $q\geqslant 110$, so in particular, $q\in\\{74,\ldots,\ell+1\\}$.
Since $V(Q)\cap V(F_{\\_}i)=\\{x_{\\_}0\\}\subseteq V(T_{\\_}i)$, we have
$V(Q)\cap V(T_{\\_}i)=\\{x_{\\_}0\\}$ and the path $Q$ is contained in an
$F_{\\_}i$-bridge, so $i$ and $Q$ satisfy the preconditions of Claim 23. By
Claim 231, there exist $i^{\prime}\in\\{1,\ldots,m\\}$ and an
$\mathcal{R}$-clean path
$Q^{\prime}=(x_{\\_}0^{\prime},\ldots,x_{\\_}{q^{\prime}}^{\prime})$ contained
in an $F_{\\_}{i^{\prime}}$-bridge such that
$q^{\prime}\in\\{q-36,\ldots,q\\}\subseteq\\{74,\ldots,\ell+1\\}$, $V(Q)\cap
V(T_{\\_}{i^{\prime}})=\\{x_{\\_}0^{\prime}\\}$ and
$\operatorname{mdist}_{\\_}{i^{\prime}}(x_{\\_}0^{\prime})\leqslant 39$.
Hence, $i^{\prime}$ and $Q^{\prime}$ satisfy the preconditions of Claim 23. By
Claim 232 applied to $i^{\prime}$ and $Q^{\prime}$, there exist
$j^{\prime}\in\\{i^{\prime}+1,\ldots,m\\}$ such that $i^{\prime}\in
X_{\\_}{j^{\prime}}$ and
$\operatorname{dist}_{\\_}{B_{\\_}{i^{\prime}}-V(T_{\\_}{i^{\prime}}^{0})}(x_{\\_}0^{\prime},M_{\\_}j)\leqslant
42$. Therefore,

$\displaystyle\operatorname{mdist}_{\\_}{i^{\prime}}(M_{\\_}{j^{\prime}})\leqslant\operatorname{mdist}_{\\_}{i^{\prime}}(x_{\\_}0^{\prime})+\operatorname{dist}_{\\_}{B_{\\_}{i^{\prime}}-V(T_{\\_}{i^{\prime}}^{0})}(x_{\\_}0^{\prime},M_{\\_}{j^{\prime}})\leqslant
39+42=81,$

which contradicts Claim 143 since $c=450>81$. ∎

The proof of Claim 23 makes use of the following claim:

######  Claim 24.

Let $j\in\\{1,\ldots,m\\}$, let $Q=(x_{\\_}0,\ldots,x_{\\_}q)$ be an
$\mathcal{R}$-clean path in $B_{\\_}j-V(T_{\\_}j^{0})$ with
$q\in\\{0,\ldots,\ell+1\\}$ such that $x_{\\_}0\in A_{\\_}j$, and there exists
an $F_{\\_}j$-bridge $B$ contained in $B_{\\_}j$ with $x_{\\_}0\in V(B)$ and
$x_{\\_}q\not\in V(B)$. Then $q\leqslant 37$.

###### Proof.

Let $x_{\\_}\alpha$ be the last vertex on $Q$ that belongs to $V(F_{\\_}j)$.
By Claim 21, we have $\alpha\leqslant 36$. Unless $q=\alpha\leqslant 36$, the
path $x_{\\_}\alpha Qx_{\\_}q$ is contained in a non-trivial $F_{\\_}k$-bridge
which equals $B_{\\_}k$ for some $k\in\\{j+1,\ldots,m\\}$ by Claim 6. Let
$x_{\\_}{\alpha^{\prime}}$ be the first vertex of $Q$ that belongs to
$V(B_{\\_}k)$. By Claim 8, we have $x_{\\_}{\alpha^{\prime}}\in
A_{\\_}k^{\operatorname{\text{out}}}$. Towards a contradiction, suppose that
$q\geqslant 38$, and thus $q\geqslant\alpha+2$. Since
$\operatorname{dist}_{\\_}G(x_{\\_}{\alpha^{\prime}},x_{\\_}\alpha)\leqslant
36$, we have $x_{\\_}{\alpha+1}\in D_{\\_}k\subseteq V(T_{\\_}k^{0})$, and
therefore $x_{\\_}{\alpha+2}\in V(T_{\\_}k)$. By definition of $T_{\\_}k$,
there exists a vertex $x_{\\_}{\alpha+2}^{\prime}\in V(T_{\\_}k^{0})$ that
belongs to the same component of $T_{\\_}k-M_{\\_}k$ as $x_{\\_}{\alpha+2}$
and satisfies
$\operatorname{dist}_{\\_}{T_{\\_}k}(x_{\\_}{\alpha+2},x_{\\_}{\alpha+2}^{\prime})\leqslant
1$. In particular,
$\operatorname{dist}_{\\_}{B_{\\_}k-A_{\\_}k}(x_{\\_}{\alpha+1},x_{\\_}{\alpha+2}^{\prime})\leqslant
2$. By Claim 12, the length of the path
$x_{\\_}{\alpha+1}T_{\\_}k^{0}x_{\\_}{\alpha+2}^{\prime}$ is less than
$2\Delta^{40}$. Since $Q$ is $\mathcal{R}$-clean, we have
$E(x_{\\_}{\alpha+1}T_{\\_}k^{0}x_{\\_}{\alpha+2}^{\prime})\cap
M_{\\_}k\neq\varnothing$, and therefore
$\operatorname{dist}_{\\_}{T_{\\_}j^{0}}(D_{\\_}k,M_{\\_}k)<2\Delta^{40}$,
which contradicts Claim 142. ∎

It remains to prove Claim 23.

###### Proof of Claim 23.

Since $V(Q)\cap V(F_{\\_}i)=\\{x_{\\_}0\\}$ and $q\geqslant 74>1$, $Q$ is
contained in a non-trivial $F_{\\_}i$-bridge, so by Claim 3, we have
$x_{\\_}0\not\in V(T_{\\_}i^{0})$, and by Claim 6, there exists
$j\in\\{i+1,\ldots,m\\}$ with $Q\subseteq B_{\\_}j$. Fix the largest
$j\in\\{i+1,\ldots,m\\}$ with $Q\subseteq B_{\\_}j$. We split the argument
into two cases based on whether $Q$ intersects $T_{\\_}j^{0}$ or not.

Case 1. $V(Q)\cap V(T_{\\_}j^{0})=\varnothing$. Let $B$ be the
$F_{\\_}j$-bridge containing the edge $x_{\\_}0x_{\\_}1$. Hence, $B\subseteq
B_{\\_}j$, and $B$ has attachment-vertices in $V(T_{\\_}i)$ and $V(T_{\\_}j)$.
We have $x_{\\_}q\in V(B)$ because otherwise Claim 24 would imply $q\leqslant
37$ contrary to our assumption that $q\geqslant 74$. Therefore
$\\{x_{\\_}0,x_{\\_}1,x_{\\_}q\\}\subseteq V(B)$, and in particular, $B$ is
non-trivial. By Claim 6, we have $B=B_{\\_}k$ for some
$k\in\\{j+1,\ldots,m\\}$. By our choice of $j$, we have $Q\not\subseteq
B_{\\_}k$. Hence there exist $\alpha,\beta\in\\{0,\ldots,q\\}$ with
$\alpha<\beta$ such that $\\{x_{\\_}\alpha,x_{\\_}\beta\\}\subseteq
V(B_{\\_}k)$, $x_{\\_}\alpha Qx_{\\_}\beta$ is edge-disjoint from $B_{\\_}k$
and $x_{\\_}\beta Qx_{\\_}q\subseteq B_{\\_}k$. Since $x_{\\_}0x_{\\_}1\in
E(B_{\\_}k)$, we have $\alpha>0$. The vertices $x_{\\_}\alpha$ and
$x_{\\_}\beta$ are attachment-vertices of $B_{\\_}k$. Since $x_{\\_}0$ is the
only vertex of $Q$ in $V(T_{\\_}i)$, the vertices $x_{\\_}\alpha$ and
$x_{\\_}\beta$ lie on $T_{\\_}j$. By Claim 19, the length of $x_{\\_}\alpha
Qx_{\\_}\beta$ is at most $4$, and we have
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}\beta,M_{\\_}j)\leqslant
6$ by Claim 15. In particular,
$\operatorname{mdist}_{\\_}{j}(x_{\\_}\beta)\leqslant 6$. By Claim 21, we have
$\beta\leqslant 36$, so 1 is satisfied by $i^{\prime}=j$ and
$Q^{\prime}=x_{\\_}\beta Qx_{\\_}q$. Furthermore,
$\operatorname{dist}_{\\_}{B_{\\_}i-V(T_{\\_}i^{0})}(x_{\\_}0,M_{\\_}j)\leqslant\beta+6\leqslant
42$, so $j$ satisfies 2.

Case 2. $V(Q)\cap V(T_{\\_}j^{0})\neq\varnothing$. Let $x_{\\_}\alpha$ be the
last vertex of $Q$ in $V(T_{\\_}j^{0})$. By Claim 21, we have $\alpha\leqslant
36$. Since $x_{\\_}{\alpha}\in V(T_{\\_}j^{0})$, we have $x_{\\_}{\alpha+1}\in
A_{\\_}j\cup V(T_{\\_}j)$. Suppose towards a contradiction, that
$x_{\\_}{\alpha+1}\in A_{\\_}j$. By Claim 21, we have $\alpha+1\leqslant 36$.
Then $x_{\\_}\alpha x_{\\_}{\alpha+1}$ is a trivial $F_{\\_}j$-bridge
contained in $B_{\\_}j$ that contains $x_{\\_}{\alpha+1}$ and does not contain
$x_{\\_}q$. By Claim 24 applied to $x_{\\_}{\alpha+1}Qx_{\\_}q$, the length of
$x_{\\_}{\alpha+1}Qx_{\\_}q$ is at most $37$, so
$q\leqslant(\alpha+1)+37\leqslant 36+37<74$, a contradiction. Therefore,
$x_{\\_}{\alpha+1}\not\in A_{\\_}j$, so $x_{\\_}{\alpha+1}\in V(T_{\\_}j)$. By
Claim 15 applied to $x_{\\_}\alpha Qx_{\\_}{\alpha+1}$, we have
$\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(x_{\\_}{\alpha+1},M_{\\_}j)\leqslant
3$, and thus
$\operatorname{dist}_{\\_}{B_{\\_}i-V(T_{\\_}i^{0})}(x_{\\_}0,M_{\\_}j)\leqslant(\alpha+1)+3\leqslant
36+3=39$. This proves 2.

For the proof of 1, let $x_{\\_}\beta$ and $x_{\\_}\gamma$ denote the last two
vertices of $Q$ in $V(F_{\\_}j)$ where $\beta<\gamma$. Since
$\\{x_{\\_}\alpha,x_{\\_}{\alpha+1}\\}\subseteq V(T_{\\_}j)$, we have
$\beta\geqslant\alpha$, and by Claim 21, we have $\gamma\leqslant 36$. We have
$\\{x_{\\_}\beta,x_{\\_}\gamma\\}\subseteq V(B_{\\_}j)\cap
V(F_{\\_}j)=A_{\\_}j\cup V(T_{\\_}j)$. We consider three subcases.

Subcase 2.1. $x_{\\_}\gamma\in V(T_{\\_}j)$. By definition of $x_{\\_}\alpha$,
the path $x_{\\_}{\alpha+1}Qx_{\\_}\gamma$ is disjoint from $T_{\\_}j^{0}$, so
$x_{\\_}{\alpha+1}\in V(T_{\\_}j)\setminus V(T_{\\_}j^{0})$ and Item 1 is
satisfied by $i^{\prime}=j$ and $Q^{\prime}=x_{\\_}\gamma Qx_{\\_}q$ since

$\operatorname{mdist}_{\\_}j(x_{\\_}\gamma)\leqslant\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(M_{\\_}j,x_{\\_}{\alpha+1})+\operatorname{dist}_{\\_}{B_{\\_}j-V(T_{\\_}j^{0})}(x_{\\_}{\alpha+1},x_{\\_}\gamma)\leqslant\alpha+1+3\leqslant
36+3=39.$

Subcase 2.2. $x_{\\_}\gamma\in A_{\\_}j$ and $x_{\\_}\beta\in V(T_{\\_}j)$.
The path $x_{\\_}\beta Qx_{\\_}\gamma$ is internally disjoint from $F_{\\_}j$,
so it is contained in an $F_{\\_}j$-bridge $B$ such that $B\subseteq
B_{\\_}j$. We have $x_{\\_}q\in V(B)$, since otherwise by Claim 24 applied to
$x_{\\_}\gamma Qx_{\\_}q$ the length of $x_{\\_}\gamma Qx_{\\_}q$ is at most
$37$, so $q\leqslant\gamma+37\leqslant 36+37<74$, which is a contradiction.
Hence, $x_{\\_}q\in V(B)$. Therefore, $B$ is non-trivial, and by Claim 3, we
have $B\subseteq B_{\\_}j-V(T_{\\_}j^{0})$. Since $\gamma<q$, $x_{\\_}q$ is
not an attachment-vertex of $B$, and we have $x_{\\_}\gamma Qx_{\\_}q\subseteq
B$, so $x_{\\_}\beta Qx_{\\_}q\subseteq B\subseteq B_{\\_}j-V(T_{\\_}j^{0})$.
Thus, Item 1 is satisfied by $i^{\prime}=j$ and $Q^{\prime}=x_{\\_}\beta
Qx_{\\_}q$ since

$\operatorname{mdist}_{\\_}j(x_{\\_}\beta)\leqslant\operatorname{dist}_{\\_}{B_{\\_}j-A_{\\_}j}(M_{\\_}j,x_{\\_}{\alpha+1})+\operatorname{dist}_{\\_}{B_{\\_}j-V(T_{\\_}j^{0})}(x_{\\_}{\alpha+1},x_{\\_}\beta)\leqslant\alpha+1+3\leqslant
36+3=39.$

Subcase 2.3 $x_{\\_}\gamma\in A_{\\_}j$ and $x_{\\_}\beta\in A_{\\_}j$. Since
the only vertex of $Q$ on $T_{\\_}i$ is $x_{\\_}0$, the vertices
$x_{\\_}\gamma$ and $x_{\\_}\beta$ lie on one tree $T_{\\_}{i^{\prime}}$ with
$i^{\prime}\neq i$. By Claim 19, the length of $x_{\\_}\beta Qx_{\\_}\gamma$
is at most $4$, and by Claim 15, we have
$\operatorname{dist}_{\\_}{B_{\\_}{i^{\prime}}-A_{\\_}{i^{\prime}}}(M_{\\_}{i^{\prime}},x_{\\_}\gamma)\leqslant
6$. In particular,
$\operatorname{mdist}_{\\_}{i^{\prime}}(x_{\\_}\gamma)\leqslant 6$. Hence, 1
is satisfied by $i^{\prime}$ and $Q^{\prime}=x_{\\_}\gamma Qx_{\\_}q$. This
completes the proof. ∎

##  7 Graphs on Surfaces

This section proves Theorem 17 which lifts our result for blocking partitions
of planar graphs (Theorem 16) to graphs on surfaces. We need the following
folklore lemma (implicit in [16, 8] for example).

######  Lemma 21.

For every connected graph $G$ with Euler genus $g$ and for every bfs-layering
$(V_{\\_}0,V_{\\_}1,\dots)$ of $G$, $G$ contains a tree $T$ that is the union
of at most $2g$ vertical paths with respect to $(V_{\\_}0,V_{\\_}1,\dots)$
such that $G-V(T)$ is planar.

The next lemma is stated in terms of the following subgraph variant of clean
paths: Let $G$ be a graph and $\mathcal{Z}$ be a connected partition of a
subgraph $Z$ of $G$. A path $P$ in $G$ is _$\mathcal{Z}$ -clean_ if $|V(P)\cap
V|\leqslant 1$ for each $V\in\mathcal{Z}$.

######  Lemma 22.

For any integers $g\geqslant 0$ and $\ell\geqslant 1$, every connected graph
$G$ with Euler genus $g$ has a connected subgraph $Z$ such that $G-V(Z)$ is
planar and $Z$ has a connected partition $\mathcal{Z}$ with width at most
$2g((5g+1)\ell+3)$ such that every $\mathcal{Z}$-clean path of length at most
$\ell$ in $G$ intersects at most three parts in $\mathcal{Z}$.

###### Proof.

The $g=0$ case holds trivially with $Z$ the empty graph and $\mathcal{Z}$ the
empty set. Now assume that $g\geqslant 1$. Let $(V_{\\_}0,V_{\\_}1,\dots)$ be
a bfs-layering of $G$ where $V_{\\_}0=\\{r\\}$ for some $r\in V(G)$. By Lemma
21, $G$ contains a tree $T$ that is the union of at most $2g$ vertical paths
such that $G^{\prime}:=G-V(T)$ is planar. For $a,b\in\mathbb{N}_{\\_}0$ where
$a\leqslant b$, let $V_{\\_}{[a,b]}:=\bigcup(V_{\\_}j\colon
j\in\\{a,\dots,b\\})$ and $T_{\\_}{[a,b]}:=T[V(T)\cap V_{\\_}{[a,b]}]$. For
$i\in\mathbb{N}_{\\_}0$, we inductively construct a sequence of tuples
$(x_{\\_}i,X_{\\_}i,Z_{\\_}i,\mathcal{X}_{\\_}i,\mathcal{Z}_{\\_}i)$ with the
following properties:

  1. (1)

$x_{\\_}0=0$ and
$x_{\\_}i\in\\{x_{\\_}{i-1}+3g\ell+1,\dots,x_{\\_}{i-1}+5g\ell+1\\}$ for all
$i\geqslant 1$;

  2. (2)

$X_{\\_}i$ is an induced subgraph of $G$ with
$V(T_{\\_}{[x_{\\_}{i-1}+1,x_{\\_}i]})\subseteq V(X_{\\_}i)\subseteq
V_{\\_}{[x_{\\_}{i-2}+\ell+1,x_{\\_}i]}$;

  3. (3)

$Z_{\\_}i$ is an induced subgraph of $G$ with
$V(T_{\\_}{[0,x_{\\_}i]})\subseteq V(Z_{\\_}i)\subseteq
V_{\\_}{[0,x_{\\_}i]}$;

  4. (4)

$X_{\\_}i=Z_{\\_}i-V(Z_{\\_}{i-1})$;

  5. (5)

$\mathcal{X}_{\\_}i$ is a connected partition of $X_{\\_}i$ of width at most
$2g((5g+1)\ell+3)$;

  6. (6)

$\mathcal{Z}_{\\_}i$ is a connected partition of $Z_{\\_}i$ of width at most
$2g((5g+1)\ell+3)$ where
$\mathcal{Z}_{\\_}{i}=\mathcal{Z}_{\\_}{i-1}\cup\mathcal{X}_{\\_}i$;

  7. (7)

Every path in $G-V(Z_{\\_}{i-1})$ of length at most $\ell$ intersects at most
one part in $\mathcal{X}_{\\_}i$; and

  8. (8)

Every $\mathcal{Z}_{\\_}i$-clean path in $G$ of length at most $\ell$
intersects at most three parts in $\mathcal{Z}_{\\_}i$.

Note that when $i:=|V(G)|$, we have $x_{\\_}i\geqslant|V(G)|$ and $T\subseteq
Z_{\\_}i$, which implies that $(Z_{\\_}i,\mathcal{Z}_{\\_}i)$ satisfies the
lemma statement.

For $i=0$, such a tuple exists with $X_{\\_}i=G[\\{r\\}]$,
$Z_{\\_}i=X_{\\_}i$, $\mathcal{X}_{\\_}i=(\\{r\\})$, and
$\mathcal{Z}_{\\_}i=\mathcal{X}_{\\_}i$. Now assume that $i\geqslant 1$ and
such a tuple exists for $i-1$.

Let $x_{\\_}{i,1}:=x_{\\_}{i-1}+3g\ell+1$ and
$X_{\\_}{i,1}:=T_{\\_}{[x_{\\_}{i-1}+1,x_{\\_}{i,1}]}$. Then $X_{\\_}{i,1}$ is
the union of at most $2g$ vertical paths, and thus has at most $2g$
components. Suppose $G-V(Z_{\\_}{i-1})$ contains a path $P$ of length at most
$\ell$ that intersects at least two components of $X_{\\_}{i,1}$. Let
$x_{\\_}{i,2}:=\max\\{\\{j\colon V(P)\cap V_{\\_}j\neq\varnothing\\}\cup
x_{\\_}{i,1}\\}$ and
$X_{\\_}{i,2}:=G[V(T_{\\_}{[x_{\\_}{i-1}+1,x_{\\_}{i,2}]})\cup V(P)]$. Then
$X_{\\_}{i,2}$ has at most $2g-1$ components. Moreover, since $P$ has length
at most $\ell$, it follows that
$x_{\\_}{i,2}\in\\{x_{\\_}{i,1},\dots,x_{\\_}{i,1}+\ell\\}$ and $V(P)\subseteq
V_{\\_}{[x_{\\_}{i-1}-\ell+1,x_{\\_}{i,1}]}$, so $V(X_{\\_}{i,2})\subseteq
V_{\\_}{[x_{\\_}{i-1}-\ell+1,x_{\\_}{i,1}]}$. Iterate the above procedure
until there is no path of length at most $\ell$ that intersects two components
of $X_{\\_}{i,j}$. Such a process must terminate within at most $2g$
iterations, since no path can exist if $X_{\\_}{i,j}$ has only one component.
As such, there exists $j\in\\{1,\dots,2g\\}$ such that
$x_{\\_}{i,j}\in\\{x_{\\_}{i-1}+3g\ell+1,\dots,x_{\\_}{i-1}+5g\ell+1\\}$,
$V(X_{\\_}{i,j})\subseteq
V_{\\_}{[x_{\\_}{i-1}-2g\ell+1,x_{\\_}{i,1}]}\subseteq
V_{\\_}{[x_{\\_}{i-2}+\ell+1,x_{\\_}{i,1}]}$ and every path in
$G-V(Z_{\\_}{i-1})$ of length at most $\ell$ intersects at most one component
of $X_{\\_}{i,j}$. Set $x_{\\_}i:=x_{\\_}{i,j}$,
$X_{\\_}i:=G[V(X_{\\_}{i,j})]$, and $Z_{\\_}i:=G[Z_{\\_}{i-1}\cup X_{\\_}i]$.
Let $\mathcal{X}_{\\_}i$ be the connected partition of $X_{\\_}i$ where each
part induces a component of $X_{\\_}i$ and
$\mathcal{Z}_{\\_}i:=\mathcal{Z}_{\\_}{i-1}\cup X_{\\_}{i,j}$. We now show
that the construction satisfies the desired properties.

By construction, 1, 2, 3, 4 and 7 hold clearly. For 5, since $X_{\\_}{i}$ is
the union of at most $2g$ vertical paths of length at most $5g\ell+1$ together
with the union of at most $2g$ paths of length at most $\ell$, it follows that
$|V(X_{\\_}{i})|\leqslant 2g((5g+1)\ell+3)$. Thus 5 holds and so, by
induction, 6 holds. It remains to show 8. Let $P$ be a
$\mathcal{Z}_{\\_}i$-clean path in $G$ of length at most $\ell$. If
$V(P)\subseteq V_{\\_}{0,x_{\\_}{i-2}+\ell}$, then the claim follows by
induction. So assume that $V(P)\cap
V_{\\_}{x_{\\_}{i-2}+\ell+1,x_{\\_}i}\neq\varnothing$. So $V(P)\cap
V(Z_{\\_}{i-2})=\varnothing$. Thus $P$ only intersects parts in
$\mathcal{X}_{\\_}{i-1}\cup\mathcal{X}_{\\_}i$. As $P$ has length at most
$\ell$, it follows by 7 that $P$ only intersects at most one part of
$\mathcal{X}_{\\_}{i-1}$. Let $W:=V(P)\cap V(Z_{\\_}{i-1})$. Since $P$ is
$\mathcal{Z}_{\\_}i$-clean, it follows that $|W|\leqslant 1$. So $P-W$
consists of at most two components that are $\mathcal{Z}_{\\_}i$-clean paths
in $G-V(Z_{\\_}{i-1})$. By 7, each component of $P-W$ intersects at most one
part in $\mathcal{X}_{\\_}i$. So $P$ intersects at most three parts in
$\mathcal{Z}_{\\_}i$, as required. ∎

###### Proof of Theorem 17.

Without loss of generality, we may assume that $G$ is connected. By Lemma 22
with $\ell=895$, $G$ contains a subgraph $Z$ such that $G^{\prime}:=G-V(Z)$ is
planar and $Z$ has a connected partition $\mathcal{Z}$ with width at most
$8950g^{2}+1796g$ such that every path of length at most $895$ in $G$
intersects at most three parts in $\mathcal{Z}$. By Theorem 16, $G^{\prime}$
has a $222$-blocking partition $\mathcal{R}^{\prime}$ with width at most
$10\Delta^{80}(3612\,\Delta^{452}+900)$. Let
$\mathcal{R}:=\mathcal{R}^{\prime}\cup\mathcal{Z}$, which is a connected
partition of $G$ with width at most
$\max\\{10\Delta^{80}(3612\,\Delta^{452}+900),8950g^{2}+1796g\\}$. We claim
that $\mathcal{R}$ is $894$-blocking. Consider an $\mathcal{R}$-clean path $P$
in $G$. Then $P$ intersects at most three parts in $\mathcal{Z}$. Let
$W:=V(P)\cap V(Z)$. Since $P$ is $\mathcal{R}$-clean, $|W|\leqslant 3$.
Therefore, $P-W$ has at most four components, each of which is an
$\mathcal{R}^{\prime}$-clean path in $G^{\prime}$. Since each
$\mathcal{R}^{\prime}$-clean path in $G^{\prime}$ has length at most $222$, it
follows that $P$ has length at most $4\cdot 222+6=894$. Hence $\mathcal{R}$ is
$894$-blocking. ∎

##  8 Reflections on Blocking Partitions

This section considers which graph classes have $\ell$-blocking partitions of
width at most $c$ for some constants $\ell,c$. Bounded maximum degree is
necessary, even for trees.

######  Proposition 23.

If every tree with maximum degree $\Delta$ has an $\ell$-blocking partition of
width at most $c$, then $c\geqslant\Delta$.

###### Proof.

Let $T$ be the complete $(\Delta-1)$-ary rooted tree of height $\ell+1$. So
$T$ has maximum degree $\Delta$ and every root-to-leaf path has length
$\ell+1$. Let $\mathcal{R}$ be an $\ell$-blocking partition of $T$ of width at
most $c$. For the sake of contradiction, suppose $c<\Delta$. Then every non-
leaf vertex of $T$ has a child that belongs to a different part in
$\mathcal{R}$. So $T$ contains a root-to-leaf path $P$ where every pair of
consecutive vertices belong to different parts in $\mathcal{R}$. Moreover, no
two non-consecutive vertices in $P$ belong to the same part, since each part
in $\mathcal{R}$ is connected. Hence $P$ is an $\mathcal{R}$-clean path of
length $\ell+1$, which is a contradiction. ∎

On the other hand, bounded maximum degree is not enough.

######  Proposition 24.

There are no constants $c,d\in\mathbb{N}$ such that every 4-regular graph has
a $d$-blocking partition of width at most $c$.

###### Proof.

Suppose for the sake of contradiction that every 4-regular graph has a
$d$-blocking partition of width at most $c$. Erdős and Sachs [20] showed that
for any integers $\Delta,g\geqslant 3$ there is a $\Delta$-regular graph with
girth at least $g$. Let $G$ be a 4-regular $n$-vertex graph with girth
$g\geqslant c+d+2$. Consider a $d$-blocking partition $\mathcal{R}$ of $G$
with width at most $c$. Say that an edge $uv\in E(G)$ is _red_ if $u,v\in V$
for some $V\in\mathcal{R}$, otherwise it is _blue_. Since $g>c$, each part
$V\in\mathcal{R}$ induces a tree, so the total number of red edges is less
than $n$. Thus the number of blue edges is more than $|E(G)|-n=n$. Hence there
is a cycle $C$ in $G$ that consists of blue edges, which has length at least
$g\geqslant d+2$. Therefore $C$ contains a path $P$ of length $d+1$ that
consists of blue edges. If distinct vertices $v,w$ in $P$ are in the same part
in $\mathcal{R}$, then $G$ contains a cycle of length at most $c+d$, which
contradicts the choice of $g$. Hence $P$ is $\mathcal{R}$-clean, which is a
contradiction. ∎

Proposition 24 says that for a graph class to admit bounded blocking
partitions, some structural assumption in addition to bounded degree is
necessary. Theorem 16 shows that bounded Euler genus is such an assumption. We
now show that bounded treewidth is another such assumption.

######  Theorem 25.

Every graph $G$ has a $2$-blocking partition with width at most

$1350(\operatorname{tw}(G)+1)(\Delta(G))^{2}.$