questiontheorem question lemmatheorem lemma claimtheorem claim
invarianttheorem invariant propositiontheorem proposition observationtheorem
observation corollarytheorem corollary definitiontheorem definition
conjecturetheorem conjecture counterexampletheorem counterexample

# Obstructions to Erdős-Pósa Dualities for Minors††thanks: All authors were
supported by the French-German Collaboration ANR/DFG Project UTMA
(ANR-20-CE92-0027). The third author was also supported by the Franco-
Norwegian project PHC AURORA 2024 (Projet n° 51260WL). The last author was
also supported by the Institute for Basic Science (IBS-R029-C1).

Christophe Paul LIRMM, Univ Montpellier, CNRS, Montpellier, France. Evangelos
Protopapas††footnotemark:  Dimitrios M. Thilikos††footnotemark:
Sebastian Wiederrecht Discrete Mathematics Group, Institute for Basic Science,
Daejeon, South Korea.

###### Abstract

Let $\mathcal{G}$ and $\mathcal{H}$ be minor-closed graph classes. We say that
the pair $(\mathcal{H},\mathcal{G})$ is an Erdős-Pósa pair (EP-pair) if there
exists a function $f$ such that for every $k$ and every graph
$G\in\mathcal{G},$ either $G$ has $k$ pairwise vertex-disjoint subgraphs which
do not belong to $\mathcal{H},$ or there exists a set $S\subseteq V(G)$ of
size at most $f(k)$ for which $G-S\in\mathcal{H}.$ The classic result of Erdős
and Pósa says that if $\mathcal{F}$ is the class of forests, then
$(\mathcal{F},\mathcal{G})$ is an EP-pair for all graph classes $\mathcal{G}.$
A minor-closed graph class $\mathcal{G}$ is an EP-counterexample for
$\mathcal{H}$ if $\mathcal{G}$ is minimal with the property that
$(\mathcal{H},\mathcal{G})$ is not an EP-pair.

In this paper, we prove that for every minor-closed graph class $\mathcal{H}$
the set $\mathfrak{C}_{\mathcal{H}}$ of all EP-counterexamples for
$\mathcal{H}$ is finite. In particular, we provide a complete characterization
of $\mathfrak{C}_{\mathcal{H}}$ for every $\mathcal{H}$ and give a
constructive upper bound on its size. We show that each class $\mathcal{G}$ in
$\mathfrak{C}_{\mathcal{H}}$ can be described as the set of all minors of
some, suitably defined, sequence of grid-like graphs
$\langle\mathscr{W}_{k}\rangle_{k\in\mathbb{N}}.$ Moreover, each
$\mathscr{W}_{k}$ admits a half-integral packing, i.e., $k$ copies of some
$H\not\in\mathcal{H}$ where no vertex is used more than twice. This implies a
complete delineation of the half-integrality threshold of the Erdős-Pósa
property for minors and as a corollary, we obtain a constructive proof of
Thomas’ conjecture on the half-integral Erdős-Pósa property for minors which
was recently confirmed by Liu. Our results are algorithmic. Let
$h=h(\mathcal{H})$ denote the maximum size of an obstruction to $\mathcal{H}.$
For every minor-closed graph class $\mathcal{H},$ we construct an algorithm
that, given a graph $G$ and an integer $k,$ either outputs a half-integral
packing of $k$ copies of some $H\not\in\mathcal{H}$ or outputs a set of at
most ${2^{k^{\mathcal{O}_{h}(1)}}}$ vertices whose deletion creates a graph in
$\mathcal{H}$ in time $2^{2^{{k^{\mathcal{O}_{h}(1)}}}}\cdot|G|^{4}\log|G|.$
Moreover, as a consequence of our results, for every minor-closed class
$\mathcal{H},$ we obtain min-max-dualities, which may be seen as analogues of
the celebrated Grid Theorem of Robertson and Seymour, for the recently
introduced parameters $\mathcal{H}$-treewidth and elimination distance to
$\mathcal{H}.$

Keywords: Erdős-Pósa dualities; Graph parameters; Graph minors; Treewidth,
Elimination distance; Universal Obstructions; Parametric graphs; Decomposition
theorems

Mathematics Subject Classification: 05C83; 05C85; 05C10; 05C75, 68R10

###### Contents

  1. 1 Introduction
    1. 1.1 Erdős-Pósa dualities for graph minors
    2. 1.2 Min-max dualities and a high-level overview of our approach
    3. 1.3 Algorithmic consequences
    4. 1.4 A short description of the proof of Theorem 1.2
    5. 1.5 Defining the families $\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ and $\mathfrak{W}_{\mathcal{H}}$: A constructive description of $\mathfrak{C}_{\mathcal{H}}$
    6. 1.6 A (more) detailed outline of the proof of Theorem 1.2.
  2. 2 Preliminaries
    1. 2.1 Basic concepts
    2. 2.2 Surfaces, decompositions, and renditions
    3. 2.3 Fibers and folios of linear societies
    4. 2.4 $t$-segments
    5. 2.5 Meadows, gardens, and orchards.
  3. 3 Preliminary results
    1. 3.1 Finding a homogeneous subwall
    2. 3.2 Taming a linkage crossing large nests
  4. 4 Plowing a meadow
    1. 4.1 Creating a meadow
    2. 4.2 The meadow plowing lemma
  5. 5 Sowing a garden
    1. 5.1 Planting the seeds
    2. 5.2 The garden creation lemma
  6. 6 Growing an orchard
    1. 6.1 Developing the tools
    2. 6.2 Cultivating a transaction
    3. 6.3 Greenhouses
    4. 6.4 Swapping a thicket and a parterre
    5. 6.5 The extraction lemma
    6. 6.6 The proof of Section 6
  7. 7 Harvesting
    1. 7.1 Lines in cylindrical renditions
    2. 7.2 Pseudo-disks in cylindrical renditions
    3. 7.3 Critical pseudo-disks and fibers
    4. 7.4 Harvesting fibers
    5. 7.5 Main harvesting lemmata
  8. 8 Plucking flowers from thickets
    1. 8.1 Certifying flatness
    2. 8.2 Flatness certifying complements of thickets
    3. 8.3 A variant of the combing lemma
    4. 8.4 Plucking a flower
  9. 9 The local structure theorem
    1. 9.1 Finding the universal obstruction
    2. 9.2 Bringing everything together
  10. 10 Extensions of graphs in their guest walloids
    1. 10.1 Designs of embedding pairs
    2. 10.2 Designs as minors of walloids
    3. 10.3 Graphs as minors of their designs
  11. 11 Universal obstructions for $\mathcal{H}$-treewidth
    1. 11.1 A torso-free definition of $\mathcal{H}$-treewidth
    2. 11.2 Strict $\mathcal{H}$-brambles
    3. 11.3 The lower bound
    4. 11.4 The upper bound
  12. 12 Universal obstructions for ${\sf apex}_{\mathcal{H}}$ and $\mathcal{H}$-td
    1. 12.1 Global apex pairs
    2. 12.2 The disconnected case
    3. 12.3 Universal obstructions for $\mathcal{H}$-${\sf td}$
  13. 13 Consequences and open problems

##  1 Introduction

Min-max dualities like Menger’s Theorem or the related Max-Flow/Min-Cut
Theorem are among the most powerful results in discrete mathematics, usually
having strong algorithmic consequences. In many cases, exact dualities like
the ones above do not exist, however, allowing for some gap may yield
approximate results. Two emblematic theorems of this type in structural graph
theory are the Erdős-Pósa Theorem for hitting and packing cycles [19] and the
Grid Theorem of Robertson and Seymour which ties treewidth to the existence of
large and highly connected planar minors [62]. In this paper we generalize
both results above, maintaining their deep connection, to arbitrary minor-
closed graph classes $\mathcal{H}.$ Regarding the former, we determine all
minor-closed classes $\mathcal{G}$ where, for each of its members, the absence
of a small hitting set for the obstructions of $\mathcal{H}$ implies the
presence of many disjoint such obstructions. Moreover, regarding the second,
we prove that any graph where the parameter “$\mathcal{H}$-treewidth” is large
must contain a certificate for this in the form of a highly regular grid-like
minor containing many “highly entangled” obstructions to $\mathcal{H}.$

###  1.1 Erdős-Pósa dualities for graph minors

We begin with a general introduction to Erdős-Pósa-type dualities together
with some basic notation for the presentation of our results.

#### Minors.

A graph $Z$ is a _minor_ of a graph $G$ if $Z$ can be obtained from a subgraph
of $G$ by contracting edges. This induces a partial order on the class of all
graphs which we denote by $\leq.$ A graph class $\mathcal{G}$ is _minor-
closed_ if it contains all minors of its elements and it is _proper_ if it
does not contain all graphs. The _obstruction set_ ${\sf obs}(\mathcal{G})$ of
a minor-closed graph class $\mathcal{G}$ is the set of $\leq$-minimal graphs
not in $\mathcal{G}.$ We refer to the graphs in ${\sf obs}(\mathcal{G})$ as
the _obstructions_ of $\mathcal{G}.$ Due to the main result of the Graph
Minors series by Robertson and Seymour [66] we know that
$\mathsf{obs}(\mathcal{G})$ is a finite set for all minor-closed graph classes
$\mathcal{G}.$

#### Apices and barriers.

Given a graph class $\mathcal{H},$ an _$\mathcal{H}$ -modulator_ of a graph
$G$ is a subset of vertices of $G$ whose deletion yields a graph in
$\mathcal{H}.$ The _$\mathcal{H}$ -apex_ number of $G,$ denoted by ${\sf
apex}_{\mathcal{H}}(G),$ is defined as the minimum size of an
$\mathcal{H}$-modulator in $G.$ When $\mathcal{H}$ is a minor-closed graph
class, the study of this parameter includes the proof of constructive bounds,
as a function in $k,$ for the number of obstructions of the graph class
$\\{G\mid{\sf apex}_{\mathcal{H}}(G)\leq k\\}$ [2, 21] as well as fixed-
parameter algorithms for deciding whether a graph belongs to $\\{G\mid{\sf
apex}_{\mathcal{H}}(G)\leq k\\},$ parameterized by $k$ [50, 41, 33, 36, 71,
72, 73]. Instances of this problem include the classic case where
$\mathcal{H}$ is the class of all forests [15, 8, 30, 49] as well as other
classes with “good” algorithmic properties such as planar graphs [36, 33] and
graphs of bounded genus [41], that have attracted particular interest.

As an attempt to introduce an “obstructing measure” for a graph $G$ to belong
to some graph class $\mathcal{H},$ we consider a collection $\mathcal{B}$ of
subgraphs of $G,$ each “obstructing” membership to $\mathcal{H}.$ When
$\mathcal{H}$ is minor-closed, every member of $\mathcal{B}$ should contain a
common111One might alternatively ask for minor-containment of different
elements of ${\sf obs}(\mathcal{H})$; however this would not define a
parameter that is functionally different, as $\mathsf{obs}(\mathcal{H})$ is
finite by the Robertson-Seymour Theorem. element of ${\sf obs}(\mathcal{H})$
as a minor. If the subgraphs in $\mathcal{B}$ are pairwise vertex disjoint we
call $\mathcal{B}$ an _integral $\mathcal{H}$-barrier_ (or
$\mathcal{H}$-barrier for short). If every vertex of $G$ belongs to at most
two members of $\mathcal{B},$ then $\mathcal{B}$ is a _half-integral
$\mathcal{H}$-barrier_. We may turn this notion into a maximization parameter
${\sf barrier}_{\mathcal{H}}(G)$ (resp. $\nicefrac{{1}}{{2}}\text{-}{\sf
barrier}_{\mathcal{H}}(G)$) by defining it as the maximum size of an
$\mathcal{H}$-barrier (resp. half-integral $\mathcal{H}\text{-}{\sf barrier}$)
of $G.$ For example, in the case where $\mathcal{H}$ is the class of forests,
an integral $\mathcal{H}$-barrier of $G$ is a set of pairwise vertex-disjoint
cycles in $G$ (notice that each cycle contains
$K_{3}\in\mathsf{obs}(\mathcal{H})=\\{K_{3}\\}$ as a minor).

#### Erdős-Pósa dualities.

If $G$ contains an $\mathcal{H}$-barrier $\mathcal{B},$ then every
$\mathcal{H}$-modulator is forced to contain at least one vertex from each
member of $\mathcal{B}.$ Therefore, ${\sf barrier}_{\mathcal{H}}(G)\leq{\sf
apex}_{\mathcal{H}}(G).$ This holds for all possible choices of $\mathcal{H}$
and $G.$ Similarly, one may observe that $\nicefrac{{1}}{{2}}\text{-}{\sf
barrier}_{\mathcal{H}}(G)\leq\frac{1}{2}\cdot{\sf apex}_{\mathcal{H}}(G).$ The
question of duality is whether the reverse inequalities hold approximately:

> Under which assumptions does the absence of a large (half-integral)
> $\mathcal{H}$-barrier imply the existence of a small
> $\mathcal{H}$-modulator?

Providing a precise and complete answer to the “when” but also to the “why” of
the question above is the objective of this paper.

In order to discuss this objective formally, let us present a unified way to
express Erdős-Pósa type questions and results. Let $\mathcal{H}$ and
$\mathcal{G}$ be two minor-closed graph classes. We refer to $\mathcal{H}$ as
the _target class_ and $\mathcal{G}$ as the _environment class_. The pair
$(\mathcal{H},\mathcal{G})$ is an _Erdős-Pósa pair_ , or _EP-pair_ for short,
if there is a function $f\colon\mathbb{N}\to\mathbb{N},$ called the _gap
function_ , such that, for every graph $G\in\mathcal{G},$ it holds that ${\sf
apex}_{\mathcal{H}}(G)\leq f({\sf barrier}_{\mathcal{H}}(G)).$ The concept of
_EP-pair_ allows us to express all possible Erdős-Pósa dualities for the minor
relation and thereby formalize the “when”-part of the question above as
follows

(1)

Let $\mathcal{G}_{\mathsf{all}}$ denote the class of all graphs and let
$\mathcal{F}$ be the class of all forests. The seminal theorem of Erdős and
Pósa [19] initiated research for Erdős-Pósa dualities and motivated their
name. It can be reformulated as:

(2)

Robertson and Seymour, as a consequence of their celebrated Grid Theorem,
proved the following: [62]

(3)

The proof of (3) identifies candidates for graph families that indicate an
answer to the “why”-part of (1): they are wall-like structures representing
the graphs embeddable in non-spherical surfaces such as the projective plane
or the torus (see Figure 1). Cames van Batenburg, Huynh, Joret, and Raymond
[11] proved that for every EP-pair $(\mathcal{H},\mathcal{G}_{\mathsf{all}})$
the gap function222Given two functions
$\chi,\psi\colon\mathbb{N}\rightarrow\mathbb{N},$ we write
$\chi(n)=\mathcal{O}_{x}(\psi(n))$ to denote that there exists a computable
function $f\colon\mathbb{N}\rightarrow\mathbb{N}$ such that
$\chi(n)=\mathcal{O}(f(x)\cdot\psi(n)).$ Moreover, we write
$\chi(n)=\text{$\mathsf{poly}$}_{x}(\psi(n))$ to denote that there exists a
function $f\colon\mathbb{N}\to\mathbb{N}$ such that
$\chi(n)=f(x)n^{\mathcal{O}(1)}.$ is $\mathcal{O}_{h}(k\log k)$ where
$h\coloneqq h(\mathcal{H})$ denotes the maximum size of a member of
$\mathsf{obs}(\mathcal{H}),$ thereby matching the bound of (2).

Using $\nicefrac{{1}}{{2}}\text{-}{\sf barrier}_{\mathcal{H}}(G)$ instead of
${\sf barrier}_{\mathcal{H}}(G)$ in the discussion above yields the concept of
an _$\nicefrac{{1}}{{2}}\text{-}$ Erdős-Pósa pair_, or a
_$\nicefrac{{1}}{{2}}\text{-}$ EP-pair_ for short. In a major breakthrough
result, Liu [47] proved333A proof of Thomas’ Conjecture was announced by Norin
in 2010 at the SIAM Conference on Discrete Mathematics but it was never
published [54]. The proof we present in this paper is independent of both
Liu’s and Norin’s work. the conjecture of Thomas (see [35]) stating the
following:

(4)

A major drawback of Liu’s result is that it does neither provide explicit
bounds on the gap function for (4), nor does it provide a constructive way to
obtain either the $\mathcal{H}$-modulator, or the half-integral
$\mathcal{H}$-barrier. For this reason, algorithmic applications of (4) are
not immediate. Pursuing a constructive version of Liu’s result appears to be a
crucial step in the further development of the algorithmic aspects of Graph
Minors series and its applications.

The Grid Theorem of Robertson and Seymour [62] implies that the target graph
classes $\mathcal{H}$ which together with $\mathcal{G}_{{\text{\rm{all}}}}$
form EP-pairs are exactly those of bounded treewidth444A definition of
treewidth can be found in Section 11.. This leads to the following variant of
(1):

> Given a minor-closed class $\mathcal{H}$ of unbounded treewidth, what is the
> most general environment class $\mathcal{G}$ such that
> $(\mathcal{H},\mathcal{G})$ is an EP-pair?

#### Counterexamples to the Erdős-Pósa property.

To answer the question above, we define $\mathfrak{C}_{\mathcal{H}}$ as the
collection of all graph classes $\mathcal{G}$ for which
$(\mathcal{H},\mathcal{G})$ is not an EP-pair, while
$(\mathcal{H},\mathcal{G}^{\prime})$ is an EP-pair for every minor-closed
class $\mathcal{G}^{\prime}$ properly contained in $\mathcal{G}.$ In other
words, $\mathfrak{C}_{\mathcal{H}}$ contains all environment classes that are
subset-minimal counterexamples for being an EP-pair with $\mathcal{H}$ as the
target class. Observe that, by (3), $\mathfrak{C}_{\mathcal{H}}=\emptyset$ if
and only if $\mathcal{H}$ has bounded treewidth.

We wish to stress the “second order” nature of the collection of graph classes
$\mathfrak{C}_{\mathcal{H}}.$

#### An order-theoretic perspective.

With respect to set containment, we may think of $\mathfrak{C}_{\mathcal{H}}$
as an obstruction for a minor-closed environment class $\mathcal{G}$ to form
an EP-pair with $\mathcal{H}.$ Indeed, if $\mathbb{E}_{\mathcal{H}}$ is the
collection of all environment minor-closed graph classes that form EP-pairs
with the target minor-closed class $\mathcal{H},$ then
$\mathfrak{C}_{\mathcal{H}}$ contains the $\subseteq$-minimal minor-closed
graph classes that do not belong in $\mathbb{E}_{\mathcal{H}}.$ In this way,
$\mathfrak{C}_{\mathcal{H}}$ can be seen as a second-order obstruction for the
collection of classes $\mathbb{E}_{\mathcal{H}}.$

Therefore, providing a characterization of $\mathfrak{C}_{\mathcal{H}}$ is a
way to describe all possible Erdős-Pósa duality theorems for minor-closed
graph classes. The fact that the collection $\mathfrak{C}_{\mathcal{H}}$
exists and is countable for every $\mathcal{H}$ is a consequence of the fact
that $(\mathcal{G}_{{\text{\rm{all}}}},\leq)$ is a WQO, as proven by Robertson
and Seymour [66]. Indeed, this follows by the fact that every graph class in
$\mathfrak{C}_{\mathcal{H}}$ is minor-closed and thereby is characterized by a
finite set of obstructions. However, since $\mathfrak{C}_{\mathcal{H}}$ is a
collection of graph classes, WQO for the minor relation does not imply that
$\mathfrak{C}_{\mathcal{H}}$ is finite. In fact, the finiteness of
$\mathfrak{C}_{\mathcal{H}},$ for all $\mathcal{H},$ would follow immediately
from the stronger conjecture that $(\mathcal{G}_{{\text{\rm{all}}}},\leq)$ is
an “$\omega^{2}$-WQO” [55]. This conjecture, as well as the more general one
that $(\mathcal{G}_{{\text{\rm{all}}}},\leq)$ is a Better Quasi Ordering (BQO)
remain central open problem in order theory [57]. Unfortunately, proving these
conjectures seems to be a “hopelessly difficult problem”, as mentioned by
Robertson, Seymour, and Thomas in [69]. Moreover, it is unlikely that if such
a proof ever appears, it is a constructive one. Even a constructive proof that
$(\mathcal{G}_{{\text{\rm{all}}}},\leq)$ is a WQO appears to be out of reach
[24, 45, 20].

An alternative way to obtain explicit bounds for the gap function would be a
constructive proof for Erdős-Pósa-type dualities. This would constitute the
basis of an algorithmic theory. For these reasons, to tackle such theorems, it
seems imperative to study the collections $\mathfrak{C}_{\mathcal{H}}$
explicitly.

#### Our results.

In this paper we fully characterize the collection
$\mathfrak{C}_{\mathcal{H}}$ for every proper minor-closed graph class
$\mathcal{H}$ and prove that it is finite.

A _parametric graph_ is a minor-monotone sequence
$\mathscr{G}=\langle\mathscr{G}_{t}\rangle_{t\in\mathbb{N}}$ of graphs,
i.e.for every $t\in\mathbb{N},$ $\mathscr{G}_{t}\leq\mathscr{G}_{t+1}.$ As we
shall see, the concept of parametric graph is central to the characterization
of the collection $\mathfrak{C}_{\mathcal{H}},$ for every proper minor-closed
graph class $\mathcal{H}.$ Indeed, for every proper minor-closed graph class
$\mathcal{H},$ we construct a finite collection of parametric graphs
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}=\\{\mathscr{F}^{\mathcal{H},1},\ldots,\mathscr{F}^{\mathcal{H},r}\\},$
$r\coloneqq r(\mathcal{H}),$ consisting of “wall-like” parametric graphs,
hereafter called walloids, and prove that, every class in
$\mathfrak{C}_{\mathcal{H}}$ is the set of all minors of some parametric graph
from $\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}.$ In particular, we
prove the following.

######  Theorem 1.1 (Main result).

For every proper minor-closed graph class $\mathcal{H}$ and every minor-closed
graph class $\mathcal{G},$ $(\mathcal{H},\mathcal{G})$ is an EP-pair if and
only if the class $\mathcal{G}$ excludes a member of $\mathscr{F},$ for every
$\mathscr{F}\in\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}.$

Notice that Theorem 1.1 indeed provides an answer to the “when” part of our
leading question (1): the absence of a large $\mathcal{H}$-barrier in a graph
$G\in\mathcal{G}$ implies the existence of a small $\mathcal{H}$-modulator if
and only if $\mathcal{G}$ excludes a graph for each of the classes generated
by the parametric graphs in
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}.$ An important feature of
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ (see the definition in (9))
is the following.

######  Observation .

For every proper minor-closed graph class $\mathcal{H},$ every
$\langle\mathscr{F}_{t}\rangle_{t\in\mathbb{N}}\in{\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}},$
and every $t\in\mathbb{N}$ we have that ${\sf
barrier}_{\mathcal{H}}(\mathscr{F}_{t})=1.$

In light of Subsection 1.1, the “why” part is answered precisely because the
parametric graphs in $\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ are
those where it is impossible to pack two copies of some member of
$\mathsf{obs}(\mathcal{H}),$ while, with increasing $t,$ they require larger
and larger $\mathcal{H}$-modulators. In this sense, they indeed act as proper
counterexamples to the Erdős-Pósa property in the exact same way as the
surface-based examples of Robertson and Seymour [62].

For each proper minor-closed class $\mathcal{H},$ the set
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ is constructed using the
obstructions of $\mathcal{H}$ as a starting point. We postpone the description
of this construction to Subsection 1.5. We stress however that for every class
$\mathcal{H}$ of bounded treewidth, as $\mathfrak{C}_{\mathcal{H}}=\emptyset,$
we have that $\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}=\emptyset.$ As
a first non-trivial example, let us consider $\mathcal{H}$ to be a minor-
closed class such that $\mathsf{obs}(\mathcal{H})$ contains no planar graphs
and at least one single-crossing minor555A graph is a _single-crossing minor_
if it is a minor of some graph that can be drawn in the plane with at most one
crossing.. It turns out that
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ is composed of the two
parametric graphs that are depicted in Figure 1666In [56], we have proven,
among others, that the parametric graphs depicted in Figure 1 are the two
parametric graphs in $\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ for
every minor-closed graph class $\mathcal{H}$ whose all obstructions are non-
planar and at least one of them is single-crossing minor. The result of the
first paper only applies to a restricted collection of classes $\mathcal{H}$
whose obstruction set contains at least one graph that belongs to a specific
proper subclass of $K_{8}$-minor-free graphs. We explain this in more detail
in Section 13..

Figure 1: Two wall-like graphs in
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ when $\mathcal{H}$ is the
class of $K_{3,3}$-minor free graphs.

This implies that $\mathfrak{C}_{\mathcal{H}}$ is composed of the class of all
toroidal graphs and the class of all projective planar graphs. This
generalizes (3), by replacing the condition that the target graph class has a
planar obstruction, to the condition that the target graph class $\mathcal{H}$
has obstructions that are all non-planar and that at least one of them is a
single-crossing minor, obtaining that, in this case,
$(\mathcal{H},\mathcal{G})$ is an EP-pair if and only if $\mathcal{G}$
excludes some toroidal and some projective planar graph.

In fact, for every class $\mathcal{H}$ whose obstruction set does not contain
a planar graph, $\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ contains a
parametric graph representing some orientable surface other than the sphere
and a parametric graph representing a non-orientable surface. However, in
general not all members of $\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$
correspond to surfaces. As we shall see in Subsection 1.5, the members of
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ may be arbitrarily far away
from being surface-embeddable. A wide family of $\mathcal{H}$’s where
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ indeed corresponds to
surfaces is studied in [56].

Finally, we wish to stress that our results yield two additional insights. The
first is that

(5)

where $\ell(\cdot)$ is the so-called _unique linkage function_ (see [67, 40,
51, 3, 26] and Subsection 3.2) and $h\coloneqq h(\mathcal{H})$ is the maximum
size of a member of $\mathsf{obs}(\mathcal{H}).$

The second resides on following important feature of
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$: each parametric graph
$\mathscr{F}=\langle\mathscr{F}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$
consists of wall-like graphs that contain a half-integral
$\mathcal{H}\text{-}{\sf barrier}$ whose size increases as a function in their
index $t$ (see Subsection 11.3). Likewise, the wall-like objects that
“obstruct” the integral Erdős-Pósa duality (see Theorem 1.1), do serve as
certificates of the half-integral Erdős-Pósa duality. As a corollary of this,
we obtain a constructive proof of Thomas’ conjecture which implies that the
gap function of (4) is bounded by ${2^{k^{\mathcal{O}_{h}(1)}}}.$

###  1.2 Min-max dualities and a high-level overview of our approach

At its core, our approach is very close to the spirit of the Graph Minor
series of Robertson and Seymour. That is, we do not immediately obtain Theorem
1.1. Instead, we take a detour and first describe the structure of graphs that
“locally” exclude a large (half-integral) $\mathcal{H}$-barrier.

The Grid Theorem [62] states that there exists a function
$f\colon\mathbb{N}\to\mathbb{N}$ such that for every graph $G$ and every
integer $k,$ if $G$ has treewidth at least $f(k)$ then $G$ contains a
$k$-wall777See Subsection 2.4 for the definition of walls. as a subgraph. For
this we need two ingredients. The first is a description of what “local” with
respect to a wall means. Let $k$ be a positive integer, $W$ be a $k$-wall in a
graph $G$ and $S\subseteq V(G)$ be a set of strictly less than $k$ vertices.
Then there exists at least one pair of a horizontal and a vertical path of $W$
which avoids $S.$ Notice that all possible choices of such pairs belong to the
same connected component of $G-S.$ We say that this component _contains the
majority of $G-S$_888For the reader familiar with the theory of graph minors
it is probably apparent that this notion does indeed define a tangle. However,
for our purposes it suffices to deal with tangles only in this implicit
fashion.. The second ingredient is another collection of parametric graphs
whose explicit definition we postpone to Subsection 1.5. For every proper
minor-closed graph class $\mathcal{H},$ we will describe a finite collection
of parametric graphs
$\mathfrak{W}_{\mathcal{H}}=\\{\mathscr{W}^{\mathcal{H},1},\dots,\mathscr{W}^{\mathcal{H},w}\\},$
where $w=w(\mathcal{H})$ is a constant depending only on the class
$\mathcal{H},$ consisting of “wall-like” parametric graphs which have, among
others, the following three important properties:

  1. 1.

if, for some
$\mathscr{W}=\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}_{\mathcal{H}},$
there does not exist $q\in\mathbb{N}$ such that $\mathscr{W}_{q}$ contains two
disjoint copies of some member of $\mathsf{obs}(\mathcal{H})$ as a minor, then
$\mathscr{W}\in\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}},$

  2. 2.

there exists $f^{1}_{\mathcal{H}}\colon\mathbb{N}\to\mathbb{N}$ such that for
every $\mathscr{W}=\langle
W_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}_{\mathcal{H}}\setminus\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$
and every $k\in\mathbb{N},$ $\mathscr{W}_{{f^{1}_{\mathcal{H}}}(k)}$ contains
an $\mathcal{H}$-barrier of size $k,$ and

  3. 3.

there exists a function $f^{2}_{\mathcal{H}}\colon\mathbb{N}\to\mathbb{N}$
such that for every $i\in[w]$ and every positive integer $k,$
$\mathscr{W}^{\mathcal{H},i}_{f^{2}_{\mathcal{H}}(k)}$ contains a half-
integral $\mathcal{H}$-barrier of size $k$ and an
$f^{2}_{\mathcal{H}}(k)$-wall such that the wall and the barrier cannot be
separated by fewer than $k$ vertices.

At the heart of our proof sits the following “local structure theorem”. We
present here an equivalent but slightly simplified version of Theorem 9.1
which avoids a lot of the heavier notations and technical definitions.

######  Theorem 1.2 (Local structure theorem (simplified)).

For every proper minor-closed graph class $\mathcal{H}$ there exist functions
$f^{1},f^{2}\colon\mathbb{N}\to\mathbb{N}$ such that for every positive
integer $k$ and every graph $G,$ if $W$ is a $f^{1}(k)$-wall in $G,$ then

  * •

there exists a parametric graph
$\mathscr{W}=\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}_{\mathcal{H}}$
such that $G$ contains a subdivision $W^{\prime}$ of $\mathscr{W}_{k}$ and
$W^{\prime}$ cannot be separated from $W$ by fewer than $k$ vertices, or

  * •

there exists a set $S\subseteq V(G)$ of size at most $f^{2}(k)<f^{1}(k)$ such
that the component of $G-S$ which contains the majority of the
degree-$3$-vertices of $W-S$ belong to $\mathcal{H}.$

With Theorem 1.2 we have a powerful tool at our disposal which allows us to
describe any graph $G$ which excludes a member of every parametric graph in
$\mathfrak{W}_{\mathcal{H}}$ in terms of a tree decomposition into pieces that
are either small or belong to $\mathcal{H}.$ This type of behavior is very
reminiscent of the Grid Theorem of Robertson and Seymour [62], but also of
their general structure theorem for $H$-minor-free graphs [65], and it is
similar to other, more recent results such as the one in [76]. To provide a
description of this intermediate result and how it leads to Theorem 1.1, we
require some additional definitions. In the following we describe, roughly,
how all of our results reduce to Theorem 1.2.

A (very) brief outline of the proof of Theorem 1.2 is given in Subsection 1.4,
for a slightly more in-depth discussion and overview of the proof, including
several of the more technical definitions we postponed so far, we refer the
reader to Subsection 1.5 and Subsection 1.6.

#### Parametric families.

Let $\mathscr{G}=\langle\mathscr{G}_{t}\rangle_{t\in\mathbb{N}}$ and
$\mathscr{G}^{\prime}=\langle\mathscr{G}_{t}^{\prime}\rangle_{t\in\mathbb{N}}$
be two parametric graphs. We write $\mathscr{G}\lesssim\mathscr{G}^{\prime},$
if there is some function $f\colon\mathbb{N}\to\mathbb{N}$ such that
$\mathscr{G}_{t}\leq\mathscr{G}_{f(t)}^{\prime}$ for all $t\in\mathbb{N}.$ If
$\mathscr{G}\lesssim\mathscr{G}^{\prime}$ and
$\mathscr{G}^{\prime}\lesssim\mathscr{G}$ we say that $\mathscr{G}$ and
$\mathscr{G}^{\prime}$ are _equivalent_ , denoted by
$\mathscr{G}\equiv\mathscr{G}^{\prime}.$

Let $\mathfrak{G}$ and $\mathfrak{G}^{\prime}$ be parametric families. We say
that $\mathfrak{G}\lesssim^{*}\mathfrak{G}^{\prime}$ if for every
$\mathscr{G}^{\prime}\in\mathfrak{G}^{\prime}$ there is some
$\mathscr{G}\in\mathfrak{G}$ such that
$\mathscr{G}\lesssim\mathscr{G}^{\prime}$999This “lifting” of the relation
$\lesssim$ on parametric graphs to families of parametric graphs is called the
Smyth extension of $\lesssim$ in the theory of WQOs.. Moreover, $\mathfrak{G}$
and $\mathfrak{G}^{\prime}$ are said to be _equivalent_ if
$\mathfrak{G}\lesssim^{*}\mathfrak{G}^{\prime}$ and
$\mathfrak{G}^{\prime}\lesssim^{*}\mathfrak{G},$ this is denoted by
$\mathfrak{G}\equiv^{*}\mathfrak{G}^{\prime}.$ A parametric family
$\mathfrak{G}$ is an _antichain_ if for every pair
$\mathscr{G},\mathscr{G}^{\prime}\in\mathfrak{G}$ with
$\mathscr{G}\neq\mathscr{G}^{\prime}$ it holds that
$\mathscr{G}\not\lesssim\mathscr{G}^{\prime}$ and
$\mathscr{G}^{\prime}\not\lesssim\mathscr{G}.$ If $\mathfrak{G}$ is a
parametric family, we say that a subset $\mathfrak{G}^{\prime}$ of
$\mathfrak{G}$ is a _minimization_ of $\mathfrak{G}$ if
$\mathfrak{G}^{\prime}\equiv^{*}\mathfrak{G}$ and $\mathfrak{G}^{\prime}$ is
an antichain. Notice that all minimizations of $\mathfrak{G}$ are pairwise
equivalent. This permits us to use $\mathsf{min}(\mathfrak{G})$ to denote an
arbitrarily chosen minimization of $\mathfrak{G}.$

#### Graph parameters and universal obstructions.

A graph parameter is a function ${\sf
p}\colon\mathcal{G}_{{\text{\rm{all}}}}\to\mathbb{N}$ mapping graphs to non-
negative integers. Given two graph parameters ${\sf p}$ and $\mathsf{q},$ we
write ${\sf p}\preceq\mathsf{q}$ if there is a function
$f\colon\mathbb{N}\to\mathbb{N}$ such that ${\sf p}(G)\leq f(\mathsf{q}(G))$
for every graph $G.$ We refer to $f$ as the _gap function_ of this relation.
It is not hard to observe that $\preceq$ is a quasi-ordering on the set of
graph parameters. We also say that ${\sf p}$ and $\mathsf{q}$ are _equivalent_
with gap function $f,$ denoted by ${\sf p}\sim\mathsf{q},$ if ${\sf
p}\preceq\mathsf{q}$ and $\mathsf{q}\preceq{\sf p}$ where $f$ is a gap
function witnessing both relations. Let $\mathfrak{P}$ be a finite set of
graph parameters. We define $\max(\mathfrak{P})$ as the parameter ${\sf
p}(G)\coloneqq\max\\{\mathsf{q}(G)\mid\mathsf{q}\in\mathfrak{P}\\}.$

Given a parametric graph
$\mathscr{G}=\langle\mathscr{G}_{t}\rangle_{t\in\mathbb{N}},$ we define the
graph parameter ${\sf
p}_{\mathscr{G}}\colon\mathcal{G}_{{\text{\rm{all}}}}\to\mathbb{N}$ to be

$\displaystyle{\sf p}_{\mathscr{G}}(G)\coloneqq\max\\{t\mid\mathscr{G}_{t}\leq
G\\}.$

Let $\mathfrak{G}$ be a parametric family. We define ${\sf
p}_{\mathfrak{G}}(G)\coloneqq\max(\\{{\sf
p}_{\mathscr{G}}\mid\mathscr{G}\in\mathfrak{G}\\}).$ One may now observe that
$\mathfrak{G}^{1}\lesssim^{*}\mathfrak{G}^{2}$ if and only if ${\sf
p}_{\mathfrak{G}^{1}}\preceq{\sf p}_{\mathfrak{G}^{2}}.$ We say that a
parametric family $\mathfrak{G}$ is an _obstructing set_ for a graph parameter
${\sf p}$ if ${\sf p}\sim{\sf p}_{\mathfrak{G}}.$ Moreover, $\mathfrak{G}$ is
a _universal obstruction_ for ${\sf p}$ if it is an obstructing set for ${\sf
p}$ and a $\lesssim$-antichain. Observe that $\mathfrak{G}_{1}$ and
$\mathfrak{G}_{2}$ are both obstructing sets for the same graph parameter if
and only if $\mathfrak{G}_{1}\equiv^{*}\mathfrak{G}_{2}.$

With these notions at hand, we are now ready to describe how our approach
yields a far-reaching generalization of the Grid Theorem of Robertson and
Seymour. Indeed, as we will see, the parameter
$\mathsf{p}_{\mathfrak{W}_{\mathcal{H}}}$ is equivalent to a generalization of
treewidth which has received considerable attention in recent years,
specifically by the algorithmic community.

####  $\mathcal{H}$-treewidth.

Given a graph $G$ and a set $X\subseteq V(G),$ we define $\mathsf{torso}(G,X)$
as the graph obtained from $G[X]$ by turning, for each component $K$ of $G-X,$
the set $N_{G}(V(K))$ (i.e., the neighbors of the component in $X$) into a
clique. Given a class $\mathcal{H},$ the parameter _$\mathcal{H}$ -treewidth_,
denoted by $\mathcal{H}$-${\sf tw},$ is defined as follows.

$\displaystyle\mathcal{H}\text{-}\mathsf{tw}(G)\coloneqq\min\big{\\{}k\in\mathbb{N}\mid$
$\displaystyle\text{\ there exists }X\subseteq V(G)\text{ such that
}\mathsf{tw}(\mathsf{torso}(G,X))\leq k\text{ and}$ (6) $\displaystyle\text{
every component of }G-X\text{ belongs to }\mathcal{H}\big{\\}}$

Here $\mathsf{tw}(G)$ denotes the treewidth of the graph $G$ (see Section 11
for a definition).

The above definition was proposed by Eiben, Ganian, Hamm, and Kwon [18] as a
natural extension of treewidth that measures the tree decomposability of a
graph into pieces belonging to some class $\mathcal{H}$ and has interesting
algorithmic applications (see [18, 31, 4, 5, 32, 29, 53]). A direct
consequence of the Grid Theorem of Robertson and Seymour is that
$\mathcal{H}$-$\mathsf{tw}\sim{\sf tw}$ if and only if
$\mathsf{obs}(\mathcal{H})$ contains a planar graph (see Subsection 11.1).

Our first core result is that, for every $\mathcal{H},$
$\mathfrak{W}_{\mathcal{H}}$ is an obstructing set for $\mathcal{H}$-${\sf
tw}.$ For this, we need two results. The first is the following.

######  Theorem 1.3.

For every proper minor-closed graph class $\mathcal{H},$ every parametric
graph $\mathscr{W}=\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}$ in
$\mathfrak{W}_{\mathcal{H}},$ and every $t\in\mathbb{N}$ it holds that
$\mathcal{H}\text{-}{\sf tw}(\mathscr{W}_{t})\in\Omega_{h}(t).$

The proof of Theorem 1.3 is based on an appropriate adaptation of the notion
of brambles to the concept of $\mathcal{H}$-treewidth. Brambles are known to
act as lower bounds to treewidth [59]. For the notion of
$\mathcal{H}$-treewidth we adopt the following definition. A _strict
101010Notice that the original notion of brambles (see for example [61])
allows for two bramble elements to be disjoint if they are joined by an edge.
While we believe that such a (more relaxed) definition of
$\mathcal{H}$-brambles could yield even tighter duality results, strict
$\mathcal{H}$-brambles occur more naturally within our proofs.
$\mathcal{H}$_-bramble in a graph $G$ is a collection $\mathcal{B}$ of
connected subgraphs of $G$ which pairwise intersect such that
$\mathcal{B}\cap\mathcal{H}=\emptyset.$ The _order_ of a strict
$\mathcal{H}$-bramble $\mathcal{H}$ is the minimum size of a hitting set for
all elements of $\mathcal{B}.$ In Figure 2 we provide a sketch of the
construction of a strict $\mathcal{H}$-bramble of large order in a member of
$\mathfrak{W}_{\mathcal{H}}.$ The fact that the members of
$\mathfrak{W}_{\mathcal{H}}$ contain large order strict $\mathcal{H}$-brambles
stems from their construction. We show that for each
$\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}_{\mathcal{H}}$
there exists some constant $c=c(\mathcal{H})$ such that $\mathscr{W}_{c}$
contains a member of $\mathsf{obs}(\mathcal{H})$ as a minor (see Theorem
10.1). In fact, for increasing $t,$ $\mathscr{W}_{t}$ contains a large half-
integral $\mathcal{H}$-barrier consisting of such minors and this barrier also
acts as the strict $\mathcal{H}$-bramble.

Figure 2: A strict bramble of subgraphs, all obstructing membership to
$\mathcal{H},$ in a member $\mathscr{W}_{k}$ of $\mathfrak{W}_{\mathcal{H}}.$
The blue strip at the bottom represents the large wall that constitutes the
basis of $\mathscr{W}_{k}.$
At the top of this wall, we attach gadgets with different properties. These
gadgets are, from left to right, two “handle segments” and two “crosscap
segments” which model a surface. What follows are several “flower segments”.
These segments model parts of an obstruction $Z\in\mathsf{obs}(\mathcal{H})$
which attach to the rest of the graph through few (that is less than three)
vertices. Each “flower segment” hosts $k$ disjoint copies of the same part.
Finally, on the far right, there are additional “flower segments”. These
flowers still model parts of $Z,$ but these parts are now allowed to attach to
the rest of the graph via boundaries of size larger than three (although we
will show that the boundaries are still of bounded size).
The gray area serves two purposes. First, it illustrates one possible way $Z$
might fit into $\mathscr{W}_{k}$ as a minor. Second, it indicates how to draw
several copies of $Z$ in a way that no vertex of $\mathscr{W}_{k}$ is
contained in more than two copies and that any two copies intersect. Such a
family of copies of $Z,$ embedded as minors into $\mathscr{W}_{k}$ forms the
strict bramble. See Figure 9 and Subsection 11.3 for a more detailed
description.

The proof that strict $\mathcal{H}$-brambles of large order act as lower
bounds to $\mathcal{H}$-treewidth follows the line of fairly standard
arguments (see Subsection 11.2). The most technical part of this paper is the
upper bound towards the parametric equivalence between
$\mathcal{H}\text{-}\mathsf{tw}$ and
$\mathsf{p}_{\mathfrak{W}_{\mathcal{H}}}.$ This proof spans Section 4 to
Section 10. The key step, which is the proof of Theorem 1.2, can be found in
Section 9 while the most involved and novel technical parts are confined to
Section 7 and Section 8.

Due to the wall-like nature of the parametric graphs in
$\mathfrak{W}_{\mathcal{H}},$ Theorem 1.4 and Theorem 1.3 provide a grid
theorem for $\mathcal{H}$-treewidth for every proper minor-closed graph class
$\mathcal{H}.$ The final proof of Theorem 1.4 utilizes Theorem 1.2 together
with known balanced separator arguments.

######  Theorem 1.4 (General grid theorem).

There exists a function
$f_{\ref{main_grid_general}}\colon\mathbb{N}^{2}\to\mathbb{N}$ such that for
every proper minor-closed graph class $\mathcal{H},$ where $h=h(\mathcal{H}),$
every graph $G,$ and every $k\in\mathbb{N},$ if $\mathcal{H}\text{-}{\sf
tw}(G)\geq f(h,k),$ then there exists
$\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}_{\mathcal{H}}$
such that $G$ contains a subdivision of $\mathscr{W}_{k}.$ Moreover,
$f_{\ref{main_grid_general}}(h,k)={2^{k^{\mathcal{O}_{h}(1)}}}.$

As a direct corollary, we also obtain a similar statement for the set
$\mathfrak{W}_{\mathcal{H}}^{\mathsf{min}}$ of universal obstructions.

######  Corollary .

There exists a function
$f_{\ref{cor_grid_general}}\colon\mathbb{N}^{2}\to\mathbb{N}$ such that for
every proper minor-closed graph class $\mathcal{H},$ where $h=h(\mathcal{H}),$
every graph $G,$ and every $k\in\mathbb{N},$ if $\mathcal{H}\text{-}{\sf
tw}(G)\geq f(h,k),$ then there exists
$\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}^{\mathsf{min}}_{\mathcal{H}}$
such that $G$ contains a subdivision of $\mathscr{W}_{k}.$

#### From $\mathcal{H}\text{-}{\sf tw}$ to ${\sf apex}_{\mathcal{H}}.$

To express the structural behavior of $\mathsf{apex}_{\mathcal{H}}$ in the
form of an equivalence between parameters we must consider the family
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ and all possible
$\mathcal{H}$-barriers. We define (see (10) and the surrounding definitions)
$\mathfrak{F}_{\mathcal{H}}$ to be the union of
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ and the parametric family
$\\{\mathscr{W}^{\mathbf{p}_{Z}}\mid Z\in\mathsf{obs}(\mathcal{H})\\}$ where
$\mathscr{W}^{\mathbf{p}_{Z}}\coloneqq\langle t\cdot
Z\rangle_{t\in\mathbb{N}}.$

With this, we obtain the following lower bound towards our desired parametric
equivalence between the parameters $\mathsf{apex}_{\mathcal{H}}$ and
$\mathsf{p}_{\mathfrak{F}_{\mathcal{H}}}.$

######  Observation .

For every proper minor-closed graph class $\mathcal{H}$ and every parametric
graph
$\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{F}_{\mathcal{H}}$
it holds that ${\sf apex}_{\mathcal{H}}(\mathscr{W}_{t})=\Omega_{h}(t)$ where
$h\coloneqq h(\mathcal{H})$ is the maximum size of a member of
$\mathsf{obs}(\mathcal{H}).$

The less trivial direction of the equivalence between ${\sf
apex}_{\mathcal{H}}$ and ${\sf p}_{\mathfrak{F}_{\mathcal{H}}}$ and, in
particular, obtaining its single exponential gap function are mostly a matter
of carefully combining our results on $\mathcal{H}$-treewidth with established
techniques from the study of the Erdős-Pósa property for minors.

######  Theorem 1.5.

There exists a function
$f_{\ref{thm_apex_upper_bound}}\colon\mathbb{N}^{2}\to\mathbb{N}$ such that
for every proper minor-closed graph class $\mathcal{H},$ where
$h=h(\mathcal{H}),$ every graph $G,$ and every $k\in\mathbb{N},$ if ${\sf
apex}_{\mathcal{H}}(G)\geq f_{\ref{thm_apex_upper_bound}}(h,k),$ then there
exists
$\langle\mathscr{F}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{F}_{\mathcal{H}}$
such that $G$ contains $\mathscr{F}_{k}$ as a minor. Moreover,
$f_{\ref{thm_apex_upper_bound}}(h,k)={2^{k^{\mathcal{O}_{h}(1)}}}.$

The proof of Theorem 1.5 makes use of the three core properties of the family
$\mathfrak{W}_{\mathcal{H}}$ which allow, by Theorem 1.4 to reduce to the case
of bounded $\mathcal{H}\text{-}\mathsf{tw}.$ This reduction goes as follows:
If we find a large enough member of one of the parametric graphs in
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ we are done. Moreover, by
combining the first and the second core property of
$\mathfrak{W}_{\mathcal{H}}$ we know that, whenever we find a large enough
member of one of the parametric graphs in
$\mathfrak{W}_{\mathcal{H}}\setminus\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}},$
we have found a member of one of the parametric graphs in
$\\{\mathscr{W}^{\mathbf{p}_{Z}}\mid Z\in\mathsf{obs}(\mathcal{H})\\}.$ Hence,
whenever $\mathcal{H}$-treewidth of some graph $G$ is large enough, we
immediately obtain that $\mathsf{p}_{\mathfrak{F}_{\mathcal{H}}}(G)$ is also
large by Theorem 1.4. It follows that the only instances we have to check are
those where $\mathcal{H}$-treewidth is bounded.

From here, we are able to use standard arguments in two steps. First, we show
the theorem for every class, minor-excluding some connected graph $Z$
(Subsection 12.1). Roughly speaking, we employ the same recursive method as
described by Diestel in his proof of (3) (see [13]). This leaves open only
cases where $\mathsf{obs}(\mathcal{H})$ contains disconnected graphs. These
cases need some additional arguments using the connected case as a basis
(Subsection 12.2).

It is worthwhile to mention that the mechanism that allows us to deduce a
finite obstructing set for $\mathsf{apex}_{\mathcal{H}}$ appears far more
universal. In Section 13 we discuss this approach in a more general setting
and conjecture that our results are the basis for a whole family of similar
results based on the knowledge of obstructing sets for certain parameters. As
a proof of concept, we apply this mechanism to the parameter
$\mathcal{H}$-treedepth (also known as elimination distance to $\mathcal{H}$)
in Subsection 12.3 and obtain a finite obstructing set for every choice of a
proper minor-closed graph class $\mathcal{H}.$ This parameter was originally
introduced by Bulian and Dawar [9, 10] and has inspired its own avenue of
research [18, 31, 4, 5, 32, 29, 53].

#### A sketch of the proof of Theorem 1.1.

By the definition, $\mathfrak{F}_{\mathcal{H}}$ is the union of two parametric
families, namely $\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ and
$\\{\mathscr{W}^{\mathbf{p}_{Z}}\mid Z\in\mathsf{obs}(\mathcal{H})\\}$ where
the latter is consisting exclusively of $\mathcal{H}$-barriers. Now let
$h=h(\mathcal{H})$ be the maximum size of a member of
$\mathsf{obs}(\mathcal{H})$ and let $\mathcal{G}$ be a minor-closed graph
class. If there exists
$\mathscr{F}=\langle\mathscr{F}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$
such that $\mathscr{F}_{t}\in\mathcal{G}$ for every $t\in\mathbb{N},$ then, by
Subsection 1.1 and Subsection 1.2, it follows that $(\mathcal{H},\mathcal{G})$
is not an Erdős-Pósa pair. For the reverse direction, we may assume that for
each
$\mathscr{F}=\langle\mathscr{F}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}},$
there exists some $t_{\mathscr{F}}\in\mathbb{N}$ such that
$\mathscr{F}_{t}\notin\mathcal{G}$ for all $t\geq t_{\mathscr{F}}.$ Let
$t^{\star}\coloneqq\max\\{t_{\mathscr{F}}\mid\mathscr{F}\in\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}\\}.$
It follows that, for every $k\in\mathbb{N},$ if for any graph
$G\in\mathcal{G}$ it holds that $\mathsf{apex}_{\mathcal{H}}(G)\geq
f_{\ref{thm_apex_upper_bound}}(h,t^{\star}+1+k),$ then, by Theorem 1.5, $G$
must contain an $\mathcal{H}$-barrier of size $k.$ Therefore,
$(\mathcal{H},\mathcal{G})$ is indeed an Erdős-Pósa pair.

###  1.3 Algorithmic consequences

Let us address some important algorithmic consequences of our results along
with subsequent open problems.

#### A constructive (approximation) FPT-algorithm for half-integral packing.

Our results imply, for every proper minor-closed graph class $\mathcal{H},$
the existence of an algorithm $\mathbf{A}_{\mathcal{H}}$ that, given a graph
$G$ and an integer $k,$ either outputs a half-integral $\mathcal{H}$-barrier
of size $k$ or an $\mathcal{H}$-modulator of size at most
$2^{k^{\mathcal{O}(1)}}$ in time
$2^{2^{{k^{\mathcal{O}_{h}(1)}}}}\cdot|G|^{4}\log|G|.$ Observe that
$\mathbf{A}_{\mathcal{H}}$ can be used as an FPT-approximation algorithm for
the following problem, defined for every graph $Z.$ Given a graph $Z,$ we
define $\mathsf{excl}(Z)$ to be the class of all graphs that exclude $Z$ as a
minor.

Half-Integral $Z$-Packing

Input:

A graph $G$ and a non-negative integer $k.$

Question:

Does $G$ contain a half-integral $\mathsf{excl}(Z)$-barrier of size $k$?

Due to the algorithmic consequences of the Robertson and Seymour theorem,
there exists an algorithm that resolves the problem above, for every
$\mathcal{H},$ in time $f(k)\cdot|G|^{2}$ (see [20]), however it is non-
constructive as it is based on the knowledge of the set ${\sf
obs}(\\{G\mid\nicefrac{{1}}{{2}}\text{-}{\sf barrier}_{\mathcal{H}}(G)\leq
k\\}).$ Due to the lack of an explicit upper bound on the size of this set and
of its members, so far no constructive algorithm is known for any non-planar
graph $Z.$ We observe that for the class $\mathsf{excl}({Z}),$ the algorithm
$\mathbf{A}_{\mathsf{excl}(Z)}$ discussed above, either decides that $(G,k)$
is a yes-instance of Half-Integral $Z$-Packing or that $(G,f(k))$ is a no-
instance of Half-Integral $Z$-Packing, where
$f(k)={2^{k^{\mathcal{O}_{h}(1)}}}.$ This constitutes the first constructive
(approximation) FPT-algorithm for the Half-Integral $Z$-Packing problem. In
Section 13 we discuss further algorithmic consequences of our results.

#### Deciding when an enviroment class has the Erdős-Pósa property.

Given a minor antichain $\mathcal{R},$ we denote by
$\mathsf{excl}(\mathcal{R})$ the class of graphs that excludes the graphs in
$\mathcal{R}$ as minors, i.e., the class
$\mathcal{G}_{{\text{\rm{all}}}}\cap\bigcap_{R\in\mathcal{R}}\mathsf{excl}(R).$
Consider the following problem for any given non-empty minor antichain
$\mathcal{R}.$

Checking EP-pairs for $\mathcal{R}$-minor free target

Input:

An antichain $\mathcal{Z}$ for the minor relation.

Output:

Is $\big{(}\mathsf{excl}(\mathcal{R}),{\sf excl}(\mathcal{Z})\big{)}$ an EP-
pair?

The antichain $\mathcal{R}$ (resp. $\mathcal{Z}$) provides a finite
representation of a target (resp. environment) class and the question is
whether the fixed target class ${\sf excl}(\mathcal{R})$ makes an EP-pair with
the input environment class ${\sf excl}(\mathcal{Z}).$

For every
$\mathscr{F}=\langle\mathscr{F}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{F}_{\mathsf{excl}(\mathcal{R})},$
we define $\mathscr{F}\\!\\!\downarrow\coloneqq\\{G\mid\text{$G$ is a minor of
$\mathscr{F}_{t}$ for some $t\in\mathbb{N}$}\\}.$ Notice that, by definition,
$\mathscr{F}\\!\\!\downarrow$ is a minor-closed class. Let now

$\mathbb{O}_{\mathcal{R}}\coloneqq\\{{\sf
obs}(\mathscr{F}\\!\\!\downarrow)\mid\mathscr{F}\in\mathfrak{F}_{{\sf
excl}(\mathcal{R})}\\}.$

Observe that our results imply that the set above is finite. Moreover, by
Robertson and Seymour theorem, it consists of finite sets of graphs. In light
of the definitions above, a possible restatement of our main result (Theorem
1.1), is the following:

> For any two antichains $\mathcal{R}$ and $\mathcal{Z}$ for the minor
> relation, where $\mathcal{R}\neq\emptyset,$ the tuple
> $\big{(}\mathsf{excl}(\mathcal{R}),{\sf excl}(\mathcal{Z})\big{)}$ is an EP-
> pair if and only if for every $\mathcal{O}\in\mathbb{O}_{\mathcal{R}},$
> there exists some graph $Z\in\mathcal{Z}$ such that no graph in
> $\mathcal{O}$ is a minor of $Z.$

The description above is given in terms of finite obstruction sets to
emphasize that the entire problem has a finite description. The formulation
above reflects that for each
$\mathscr{F}\in\mathfrak{F}_{\mathsf{excl}(\mathcal{R})},$
$\mathcal{Z}\cap\mathscr{F}\\!\\!\downarrow\neq\emptyset,$ i.e., none of the
$\mathscr{F}\\!\\!\downarrow$ is fully contained in
$\mathsf{excl}(\mathcal{Z}).$

This implies that the Checking EP-pairs for $\mathcal{R}$-minor free target
problem can be solved by performing
$\sum_{\mathcal{O}\in\mathbb{O}_{\mathcal{R}}}\sum_{Z\in\mathcal{Z}}|\mathcal{O}|$
calls to the almost-linear minor-checking algorithm of Korhonen, Pilipczuk,
and Stamoulis [42] (see also [64, 37] for previous algorithms, dating back to
the Graph Minor series). Therefore, for every non-empty antichain
$\mathcal{R}$ of the minor relation, Checking EP-pairs for $\mathcal{R}$-minor
free target is solvable in almost-linear time. Making this algorithm
constructive, assuming the knowledge of $\mathcal{R},$ is an interesting open
question.

#### Erdős-Pósa dualities for topological minors.

A relevant question on Erdős-Pósa dualities is, to what extent an analogous
theory of half-integrality, based on obstructing sets, can be build for other
partial-orders one might define on graphs. A particularly natural cousin of
the minor relation that we may consider is the topological minor relation.
Here, we already have the half-integrality result of Liu [47]. Let
$\mathcal{H}$ and $\mathcal{G}$ be graph classes that are closed under
topological minors. We say that $(\mathcal{H},\mathcal{G})$ is an _Erdős-Pósa
pair for topological minors_ , in short is a _tEP-pair_ , if there exists a
function $f\colon\mathbb{N}\to\mathbb{N}$ such that every graph
$G\in\mathcal{G},$ without $k$ disjoint subdivisions of graphs that do not
belong to $\mathcal{H},$ contains a set $S$ of at most $f(k)$ vertices such
that $G-S\in\mathcal{H}.$

An immediate question is: When is
$(\mathcal{H},\mathcal{G}_{{\text{\rm{all}}}})$ a tEP-pair? Is there a
characterization analogous to the one of (3) for the topological minor
relation? This question was already asked by Robertson and Seymour in [62]
and, as mentioned in [47], Liu, Postle, and Wollan have indeed found a
complete (but complicated) characterization. Moreover, this characterization
seems to be qualitatively more complex than the planarity criterion in (3) for
the case of minors.

Let $\mathsf{texcl}(R)$ be the class of graphs excluding the graph $R$ as a
topological minor. According to Liu [48], the problem that, given a graph $R,$
asks whether $\big{(}\mathsf{texcl}(R),\mathcal{G}_{{\text{\rm{all}}}}\big{)}$
is a tEP-pair is NP-complete even if we restrict its inputs to trees. We wish
to stress the contrast to the fact that, by (3), the question “is
$\big{(}\mathsf{excl}(R),\mathcal{G}_{{\text{\rm{all}}}}\big{)}$ an EP-pair?”
is just planarity testing and thus, can be answered in polynomial time. This
suggests that a theory of obstructing sets such as the one for minors
presented in this paper is either impossible or, at least, extremely complex
for the case of topological minors. A possible source of this complexity gap
seems to be the fact that graphs ordered by the topological minor relation do
not form a WQO. However, it is an interesting question whether our approach
may help in the direction of finding a constructive proof of Liu’s theorem
with explicit bounds. In Figure 3 we illustrate the current landscape of
Erdős-Pósa dualities.

Figure 3: The iceberg provides a visual metaphor for the landscape on Erdős-
Pósa dualities for (topological) minor-closed graph classes.

#### Improving the gap function.

All parametric equivalences that we prove in this paper, namely ${\sf
p}_{\mathfrak{W}_{\mathcal{H}}}\sim\mathcal{H}\text{-}{\sf tw},$
$p_{\mathfrak{T}_{\mathcal{H}}}\sim\mathcal{H}\text{-}{\sf td},$ and
$p_{\mathfrak{F}_{\mathcal{H}}}\sim{\sf apex}_{\mathcal{H}},$ have exponential
gap functions, i.e., $f(h,k)\in{2^{k^{\mathcal{O}_{h}(1)}}}.$ A natural
question is whether this gap can be improved to a polynomial one, that is, one
of the form $k^{\mathcal{O}_{h}(1)}.$ This would also imply an improvement of
the approximation gap of the FPT-approximation algorithm for the Half-Integral
$Z$-Packing problem (mentioned on page 1.3). One of the two sources of
exponential explosion can be found in Subsection 4.1 whose proof is given in
[77] which, in turn uses [39, Theorem 11.4] as a departure point where the
parametric dependencies are already exponential. This indicates that any
improvement on this might require a general improvement of the dependencies of
the Graph minors Structural Theorem (GMST) in [65, 39]. The second level of
exponentiation comes from Section 6 where we need thickets with nests of
exponential size around their vortices in order to split those vortices. This
is because each split consumes a part of the nest to maintain the large radial
linkage which leads back to the wall, and to extract new flowers.
Interestingly the reason for the exponentiality in the proof of [39, Theorem
11.4] is also the vortex splitting operation. It seems reasonable to
conjecture that finding a way to bound the dependencies of the GMST by
polynomials would also provide a way to avoid the first source of
exponentiation. Such a result would be a major advancement.

Finally, the degree of the polynomial in $k,$ even in the exponent of
$2^{k^{\mathcal{O}_{h}(1)}},$ is highly dependent on the “meta parameter”
$h=h(\mathcal{H}).$ In fact, this dependency is at least double exponential in
$h.$ Therefore, another avenue of improvement could be to lower this
dependency. A bound on the gap function of the form
$2^{\mathsf{poly}_{h}(k)},$ or, if the improvements to polynomial dependency
we mention above can indeed be achieved, even $\mathsf{poly}_{h}(k)$ cannot be
ruled out.

###  1.4 A short description of the proof of Theorem 1.2

Since this proof is by far the most technical and involved part of the entire
paper, to properly explain it requires a large number of deeply nested
definitions. Several of these definitions are given in Subsection 1.5 and the
majority of the remaining definitions can be found in Section 2. Here we
provide a very brief and informal overview of the different steps and our
approach. A second, more in-depth but also more technical overview of our
proof can be found in Subsection 1.6.

To avoid dealing with graph classes $\mathcal{H}$ directly in our proof, we
aim for the following variant of Theorem 1.2.

######  Theorem 1.6.

There exist functions $f^{1},f^{2}\colon\mathbb{N}^{2}\to\mathbb{N}$ such that
for all positive integers $h$ and $k$ and every graph $G,$ if $W$ is an
$f^{1}(h,k)$-wall in $G,$ then there exists a set $S\subseteq V(G)$ of size at
most $f^{2}(h,k)<f^{1}(h,k)$ such that for every graph $Z$ on at most $h$
vertices, either

  * •

there exists a parametric graph
$\mathscr{W}=\langle\mathscr{W}_{t}\rangle_{t\in\mathbb{N}}\in\mathfrak{W}_{\mathsf{excl}(Z)}$
such that $G$ contains a subdivision $W^{\prime}$ of $\mathscr{W}_{k}$ and
$W^{\prime}$ cannot be separated from $W$ by fewer than $k$ vertices, or

  * •

the component of $G-S$ which contains the majority of $W-S$ is $Z$-minor-free.

#### The Graph Minor Structure Theorem of Robertson and Seymour.

To explain our approach, it is necessary to introduce the Graph Minor
Structure Theorem (GMST) of Robertson and Seymour [65, 39]. We present here an
abbreviated version of the local version of their theorem which avoids most of
the technical statements. Here local means again “with respect to a large
wall”.

Let $\alpha,b,d$ be non-negative integers. We say that a graph $G$ is
_$\alpha$ -almost embeddable_ with _breadth_ $b$ and _depth_ $d$ in some
surface $\Sigma$ if there exists a set $A\subseteq V(G)$ of size at most
$\alpha$ and there are graphs $G^{(i)}$ such that $G-A=G^{(0)}\cup
G^{(1)}\cup\dots\cup G^{(b)}$ where $G^{(0)}$ is a graph embedded in $\Sigma$
and each _vortex_ $G^{(i)},$ $i\in[b],$ is a graph of pathwidth at most $d$
which is “attached along a path decomposition111111Please see Subsection 2.2
for a formal definition.” to the vertices of some face of $G^{(0)}.$

The local version of the GMST of Robertson and Seymour now reads as follows.

(7)

Instead of starting at (7) we make use of a recent refinement by Thilikos and
Wiederrecht [77] which allows us to obtain one of three things. We either
find: (1) a large clique minor; (2) a walloid of large order that represents a
surface $\Sigma$ of large enough Euler-genus such that every graph on at most
$h$ vertices can be drawn on $\Sigma;$ or (3) a subgraph $G^{\prime}$ with the
properties from the second outcome of (7) together with a walloid $W^{*}$ of
large order which is fully contained in the graph $G^{(0)}$ of the almost
embedding of the torso of $G^{\prime}$ in this outcome.

From here on our proof follows along three crucial steps.

#### Step 1: Almost embeddings of a graph $Z.$

Let us fix $G^{(0)}$ to be the part of the torso of $G^{\prime}$ as above
which is drawn in the surface. Moreover, let $M$ be a minimal connected
subgraph of $G$ such that $M$ contains some graph $Z$ on at most $h$ vertices
as a minor and $M$ contains a vertex of the wall $W.$ Now some part of $M$
belongs to $G^{(0)},$ but other parts of $M$ may belong to the vortices
$G^{(i)}$ or to the so-called “flaps”. Flaps are those parts of $G$ which are
separated from $G^{\prime}-A$ by at most three vertices. Since these
separators are so small, they do not have to be caught within the vortices.
Instead, they form facial triangles in $G^{(0)}$ (see Subsection 2.2 and the
definitions surrounding it). This induces a specific $0$-almost embedding of
bounded breadth and depth for the graph $M.$ A _flower_ of $M$ is any maximal
subgraph of $M$ which is fully contained in either a vortex or a flap121212We
refer to Subsection 1.5 for a formal definition.. Our proof introduces a
procedure that either finds many duplicates of every single flower of $M,$ or
finds a small hitting set for at least one of those flowers.

In Section 7 and Section 8 we show, among others, that it suffices to repeat
this procedure for only a bounded number of such graphs $M$ for every graph
$Z$ on at most $h$ vertices. Moreover, we show that we may assume that $M$ has
only a bounded number, in $|Z|,$ of vertices of degree different than two.

For any such $M,$ where each individual flower appears in abundance, we will
then be able to construct a corresponding member of
$\mathfrak{W}_{\mathsf{excl}(Z)}$ of large order. This is made precise in
Subsection 9.1. A formal definition of flowers and the way we obtain these
graphs $M$ and their $0$-almost embeddings, together with a full definition of
the family $\mathfrak{W}_{\mathsf{excl}(Z)}$ is given in Subsection 1.5.

#### Step 2: Refining an almost embedding.

The “gathering” and “hitting” of the flowers of the graphs $M$ as above
happens in two stages. In the first stage we gather all possible flowers which
can easily be found to be abundant. Meanwhile all flowers where this is
impossible, or success is at least “not as apparent”, are confined within a
small number of disks described with reference to the embedding of $G^{(0)}.$
Dealing with these disks, we call them thickets, is the second stage and the
only part where we actually find the hitting set.

The first stage is exclusively concerned with flowers of $M$ that are produced
via the flaps of $G^{(0)}.$ Recall that we have the walloid $W^{*}$ within
$G^{(0)}$ which fully represents our surface $\Sigma.$ With the help of
$W^{*}$ we now produce a tiling of $\Sigma$ using only hexagons. We may assume
that there are only a bounded number of $M$’s we have to consider and each $M$
can only produce a bounded number of different flowers. This allows us to
classify, using the pigeonhole principle, those flowers that appear (a) in
many different and far apart hexagons of our tiling and those (b) that appear
either clustered closely together or a bounded number of times. This substep
is done in Section 4 and Section 5.

Let us mark all hexagons which contain flowers of type (b). By imitating a
technique developed by Kawarabayashi, Thomas, and Wollan [39] in their new
proof of (7) we now gather all marked hexagons in a small number of disks
within the drawing of $G^{(0)}$ and then further refine our distinction
between abundant and scarce flowers until each of the disks that still
contains marked hexagons can be seen as a vortex of bounded depth itself. This
step is done in Section 6.

#### Step 3: Harvesting the flowers of a “thicket”.

The vortices created in the previous steps are all equipped with additional
infrastructure. This allows us to route anything “of value” we might find
inside, back to $W^{*}.$ We call these objects thickets. The second purpose of
Section 7 and Section 8 is to apply a vast generalization of the “vortex
killing” argument of Thilikos and Wiederrecht [76]. The outcome of this
argument is, for any possible flower $F$ of any $M$ we have to consider, to
either find many disjoint copies of $F$ pasted along a single face of
$G^{(0)}$ and highly connected to $W^{*},$ or find a small hitting set for all
occurrences of $F$ within this thicket. Let $S$ be the union of all of these
hitting sets for all thickets. Finally, we prove that whenever some $M$ avoids
the set $S,$ then this must mean that there is an equivalent $M^{\prime}$
whose flowers have been found in abundance in Step 2 and this one, and thus we
are able to produce the corresponding member of
$\mathfrak{W}_{\mathsf{excl(Z)}}$ (see Subsection 9.1).

The proof of Theorem 1.6, or its more technical incarnation Theorem 9.1, is
now only a matter of carefully combining the previous steps.

###  1.5 Defining the families
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ and
$\mathfrak{W}_{\mathcal{H}}$: A constructive description of
$\mathfrak{C}_{\mathcal{H}}$

In order to state Theorem 1.1 in full formality, we first need to make our
definitions of the graphs $M$ that appear in Step 1 of Subsection 1.4 and then
describe how the families $\mathfrak{W}_{\mathcal{H}}$ and ultimately
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ are defined. Once this is
done, the collection $\mathfrak{C}_{\mathcal{H}}$ of counterexamples is fully
described, in accordance with Theorem 1.1, as the collection of every graph
class generated through the minor closure of a single member of
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}.$ Some definitions presented
in this section still hide further technicalities which are expanded upon in
Section 2.

As a first step, we make the $0$-almost embeddings of our “minor
models”131313Later we will call these graphs the extensions of $Z.$ explicit.

#### Hypergraphs from graph partitions.

A _subgraph partition_ of a graph $Z$ is a collection $\mathcal{P}$ of
subgraphs of $Z$ such that141414Given a set $\mathcal{S}$ of objects where
$\cup$ has been defined, we use ${\boldsymbol{\bigcup}}\mathcal{S}$ as a
shorthand for $\bigcup_{S\in\mathcal{S}}S.$ Here the union of two graphs
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ is defined as $G_{1}\cup
G_{2}=(V_{1}\cup V_{2},E_{1}\cup E_{2}).$
${\boldsymbol{\bigcup}}\mathcal{P}=Z$ and $\\{E(P)\mid P\in\mathcal{P}\\}$ is
a partition of $E(Z).$ Given a subgraph $P\in\mathcal{P},$ we define the
_boundary_ of $P$ in $Z$ to be the set $\partial_{Z}(P)$ containing every
vertex of $V(P)$ that is also a vertex of some other member of
$\mathcal{P}\setminus\\{P\\}.$ We define $\mathcal{P}(Z)$ to be the set
containing all subgraph partitions $\mathcal{P}$ of $Z$ such that for every
$P\in\mathcal{P},$ $\partial_{Z}(P)\neq\emptyset.$

Given a subgraph partition $\mathcal{P}\in\mathcal{P}(Z),$ we define the
hypergraph
$\mathcal{K}_{\mathcal{P}}=(V_{\mathcal{P}},\mathcal{E}_{\mathcal{P}})$ where
$\mathcal{E}_{\mathcal{P}}=\\{\partial_{Z}(P)\mid P\in\mathcal{P}\\}$ and
$V_{\mathcal{P}}={\boldsymbol{\bigcup}}\mathcal{E}_{\mathcal{P}}.$ It follows
that each hyperedge $e$ of $\mathcal{K}_{\mathcal{P}}$ is the boundary of some
member, say $G_{e},$ of the graph partition (notice that
$\mathcal{E}_{\mathcal{P}}$ may be a multi-set, as in the case of the example
of Figure 5).

In Subsection 1.4 we spoke a lot about “pasting graphs along the vertices of a
face” of “confining” parts of a graph within a disk. The following provides a
formal framework to deal with notions like those in a way that is, at first,
independent of topology.

#### Linear societies and their decompositions.

A _linear society_ is a pair $\langle H,\Lambda\rangle$ where $H$ is a non-
empty graph and $\Lambda$ is a linear ordering of some non-empty subset of
vertices of $H.$ We use $V(\Lambda)$ to denote the set of vertices of
$\Lambda$ and we refer to $V(\Lambda)$ as the _boundary_ of the linear society
$\langle H,\Lambda\rangle.$ Moreover, we always demand that every connected
component of $H$ contains some vertex of $V(\Lambda).$

Let $\langle H,\Lambda\rangle$ be a linear society where $\Lambda=\langle
y_{1},\ldots,y_{r}\rangle.$ Consider a drawing, possibly with crossings, of
$H$ in a closed disk $\Delta$ such that the vertices drawn on the boundary,
denoted by ${\sf bd}(\Delta),$ are exactly the vertices of $\Lambda$ drawn
with respect to the order $\Lambda.$ We also demand that all edges of $H$ are
drawn in the interior of $\Delta.$ For simplicity, we do not distinguish
between the vertices of $V(\Lambda)$ and the points of ${\sf bd}(\Delta)$
where these vertices are drawn.

Whenever different components of $H$ are drawn within $\Delta$ in the way
above such that there exists a curve $\gamma$ in $\Delta$ with exactly its
endpoints in ${\sf bd}(\Delta)$ where $\gamma$ does not intersect the drawing
of $H$ in any way, we are able to “split” $\langle H,\Lambda\rangle$ into
smaller linear societies using $\gamma$ while also respecting the original
linear ordering $\Lambda$ up to shifts. We formalize this intuition with the
definition below to obtain a notion of “components” of a linear society.

We see the set ${\sf bd}(\Delta)\setminus V(\Lambda)$ as a set of open lines
between consecutive vertices in $\Lambda.$ For each $i\in[r],$ let $p_{i}$ be
a point of the line with endpoints $y_{i-1}$ and $y_{i}$ (where
$y_{0}=y_{r}$). A closed subdisk $\Delta^{\prime}\subseteq\Delta$ is
_splitting_ for $\Delta$ if

  * •

$H$ can be drawn (possibly with crossings) inside
$\Delta\setminus\Delta^{\prime},$

  * •

$\\{p_{1}\\}\subseteq{\sf bd}(\Delta)\cap{\sf
bd}(\Delta^{\prime})\subseteq\\{p_{1},\ldots,p_{r}\\},$ and

  * •

the cardinality of $|{\sf bd}(\Delta)\cap{\sf bd}(\Delta^{\prime})|$ is
maximized.

Let ${\sf bd}(\Delta)\cap{\sf bd}(\Delta^{\prime})=\\{p_{i}\mid i\in I\\}$ for
some $[1]\subseteq I\subseteq[r]$ where $I=\\{i_{1}=1,i_{2},\ldots,i_{q}\\}$
and observe that $I$ is the same for every choice of a splitting subdisk
$\Delta^{\prime}$ for $\Delta.$ For each $j\in[q],$ let
$\Lambda_{j}\coloneqq\langle y_{i_{j}},\ldots,y_{i_{j+1}-1}\rangle$ and let
$H_{j}$ be the union of all connected components of $H$ that contain vertices
of $\Lambda_{j}.$ We denote the _decomposition_ of $\langle H,\Lambda\rangle$
into the linear societies $\langle H_{i},\Lambda_{i}\rangle$ as above by
$\mathsf{dec}({H,\Lambda})\coloneqq\langle\langle
H_{1},\Lambda_{1}\rangle,\ldots,\langle H_{q},\Lambda_{q}\rangle\rangle.$

Next, we reintroduce the topology to fully understand how linear societies may
be used to encode the “almost” part of our embeddings.

#### Surfaces and linear societies.

By _surface_ we mean a two-dimensional manifold (possibly with boundary). We
say that a surface $\Sigma$ is _contained_ in some surface $\Sigma^{\prime}$
if $\Sigma^{\prime}$ can be obtained from $\Sigma$ by adding handles and
crosscaps. Given a pair $(\mathsf{h},\mathsf{c})\in\mathbb{N}\times[0,2]$ we
define $\Sigma^{(\mathsf{h},\mathsf{c})}$ to be the surface without boundary
created from the sphere by adding $\mathsf{h}$ handles and $\mathsf{c}$
crosscaps. If $\mathsf{c}=0,$ the surface $\Sigma^{(\mathsf{h},\mathsf{c})}$
is _orientable_ , otherwise it is _non-orientable_. By Dyck’s theorem [17,
23], two crosscaps are equivalent (via homeomorphisms) to a handle in the
presence of a (third) crosscap. This implies that the notation
$\Sigma^{(\mathsf{h},\mathsf{c})}$ is sufficient to capture all surfaces
without boundary.

Given a graph $Z$ we denote by $\mathbb{S}^{Z}$ the set containing all
surfaces without boundary where $Z$ cannot be embedded. We define ${\sf
sobs}(\mathbb{S}^{Z})$ to be the set of all containment-wise minimal surfaces
not in $\mathbb{S}^{Z}.$ It follows that ${\sf sobs}(\mathbb{S}^{Z})$ contains
one or two surfaces, see [77]. We define $\mathbb{S}^{(Z)}$ as the set
containing every surface that is contained in some surface of ${\sf
sobs}(\mathbb{S}^{Z}).$

Let now $\Sigma$ be some surface and let $M$ be a graph, let
$\mathcal{P}\in\mathcal{P}(M)$ be a subgraph partition of $M,$ and assume that
$\Gamma$ is a $\Sigma$-embedding. In such an embedding all vertices of a
hyperedge $e\in\mathcal{E}_{\mathcal{P}}$ are drawn on the boundary of some
closed disk $\Delta_{e}$ of $\Sigma$ and two disks $\Delta_{e}$ and
$\Delta_{e^{\prime}}$ intersect only on the common vertices of $e$ and
$e^{\prime}.$ Given a choice of starting vertex $y\in e$ and some rotation of
the boundary of $\Delta_{e},$ we obtain a linear ordering $\Lambda_{e,y}$ of
the vertices of $e$ starting from $y.$ The rotation of each hyperedge is
chosen to be counterclockwise (that is, it has $\Delta_{e}$ on the left) in
case $\Sigma$ orientable, and it is chosen to be an arbitrary rotation if
$\Sigma$ is non-orientable. Each $\langle G_{e},\Lambda_{e,y}\rangle,$ for
$y\in e,$ can now be seen as a linear society. We say that the linear society
$\langle G_{e},\Lambda_{e,y}\rangle$ is _disk embeddable_ if the graph $G_{e}$
can be embedded in a closed disk $\Delta$ such that exactly the vertices of
$\Lambda_{e,y}$ are drawn on its boundary.

We are finally ready to give a definition of those $0$-almost embeddings of
graphs that sit at the core of our description of
$\mathfrak{C}_{\mathcal{H}}.$

#### Embedding pairs.

Let $Z$ be a graph. An _embedding pair_ of $Z$ is a pair
$(\Sigma,\mathbf{B}),$ where $\Sigma\in\mathbb{S}^{(Z)}$ is a surface, and
$\mathbf{B}$ is the set of all linear societies which are generated, as
described below, by a fixed triple of the form $(M,\mathcal{P},\Gamma)$ where

  1. 1.

$M$ is a connected graph containing $Z$ as a minor such that
$|M|\leq\mathsf{ext}(|Z|),$

  2. 2.

$\mathcal{P}\in\mathcal{P}(M),$ and

  3. 3.

$\Gamma$ is a $\Sigma$-embedding of $\mathcal{K}_{\mathcal{P}},$

where $\mathsf{ext}\colon\mathbb{N}\to\mathbb{N}$ is a function of order
$2^{\mathcal{O}(\ell(|Z|^{2}))}$ that will be determined in the proof of
Subsection 9.1 in Section 9 and $\ell(\cdot)$ is the unique linkage function
(see [67, 40, 3, 51, 26]).

Given a triple as above, we further consider some function
$\eta\colon\mathcal{E}_{\mathcal{P}}\to V(M)$ that assigns a starting vertex
$\eta(e)\in e$ to every $e\in\mathcal{E}_{\mathcal{P}}.$ Thereby, $\eta$
generates the following set of linear societies

$\\{\langle G_{e},\Lambda_{e,\eta(e)}\rangle\mid
e\in\mathcal{E}_{\mathcal{P}}\text{\leavevmode\nobreak\ and $\langle
G_{e},\Lambda_{e,\eta(e)}\rangle$ is not disk-embeddable}\\}.$

Notice that ${\bf B}$ may be empty. We denote by
$\mathfrak{P}_{\mathsf{excl}(Z)}$ the set containing all embedding pairs of
$Z.$ Notice that a graph on $h$ vertices has at most
$2^{\mathcal{O}((\mathsf{ext}(|Z|))^{2})}$ many subgraph partitions. Moreover,
there exist at most $2|Z|^{2}+1$ many different surfaces in $\mathbb{S}^{(Z)}$
and for each choice of $\mathcal{P}\in\mathcal{P}(Z)$ we have
$|\mathcal{P}|\leq\mathsf{ext}(|Z|)^{2}$ and $|P|\leq\mathsf{ext}(|Z|)$ for
every $P\in\mathcal{P}$ which implies that there are at most
$\mathsf{ext}(|Z|)^{3}$ many choices for $\eta.$ It follows that
$\mathfrak{P}_{\mathsf{excl}(Z)}$ has $2^{(\mathsf{ext}(|Z|))^{2}}$ elements.
Given a proper minor-closed graph class $\mathcal{H}$ we define
$\mathfrak{P}_{\mathcal{H}}\coloneqq\bigcup_{Z\in\mathsf{obs}(\mathcal{H})}\mathfrak{P}_{\mathsf{excl}(Z)}.$
We now obtain, in particular, that $|\mathfrak{P}_{\mathcal{H}}|$ is finite
for every choice of $\mathcal{H}.$

The walloids that make up our families
$\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}$ and
$\mathfrak{W}_{\mathcal{H}}$ are constructed from several smaller pieces that
can be circularly arranged. Such a modular definition allows for a nicer
presentation, but it also facilitates our proofs as it allows us in many
places to reduce to the analysis of single pieces of the walloid rather than
its entire global structure.

####  $t$-segments.

Each member $\mathscr{W}$ of
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ is a wall-like parametric
graph to which, from now on, we refer as an _elementary_ _guest walloid_.
These parametric graphs $\mathscr{W}$ are built using the embedding pairs from
$\mathfrak{P}_{\mathcal{H}}.$ The main building components of elementary guest
walloids are called _elementary_ _$t$ -segments_. While the formal definitions
are explained in detail in Subsection 2.4. Here, we provide an intuitive
description which will be sufficient to understand the family
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ and the more detailed
summary of the proof of Theorem 1.2.

The three basic components are the elementary $(t^{\prime},t)$-wall segment,
the elementary $t$-handle segment, and the elementary $t$-crosscap segment.
The _elementary $(t^{\prime},t)$-wall segment_ is an elementary
$(t^{\prime},t)$-wall and acts as the starting point of our construction of
all other elementary $t$-segments. The leftmost drawing of Figure 4 depicts an
elementary $(12,3)$-wall segment. We depict the $t$ “leftmost” vertices of an
elementary $(t^{\prime},t)$-wall segment in red and its $t$ “rightmost”
vertices in blue. Later, we will use these vertices in order to glue together
distinct $t$-segments, using new edges depicted in orange. The $t^{\prime}$
“top” vertices of the elementary $(t^{\prime},t)$-wall segment are drawn with
white interiors.

The _elementary $t$-handle segment_ is an elementary $(4t,t)$-wall segment
where we added two collections of $t$ edges, each between the top vertices of
the $(4t,t)$-wall, as indicated in the second drawing of Figure 4. The
_elementary $t$-crosscap segment_ is an elementary $(4t,t)$-wall segment
obtained by adding a collection of $2t$ edges between the top vertices of the
elementary $(4t,t)$-wall in a pairwise crossing manner, as indicated in the
third drawing of Figure 4.

Figure 4: From left to right: an elementary $3$-wall segment, an elementary
$3$-handle segment, an elementary $3$-crosscap segment, and an elementary
$(3,3,K_{3,3}^{-},\langle y_{1},y_{2}\rangle)$-flower segment.

The fourth and most complicated, and somehow central, elementary $t$-segment
is parametrized by an integer $b\in\mathbb{N}_{\geq 1}$ and a linear society
$\langle H,\Lambda\rangle$ where $\mathsf{dec}(H,\Lambda)=\langle\langle
H_{1},\Lambda_{1}\rangle,\ldots,\langle H_{q},\Lambda_{q}\rangle\rangle.$

An _elementary $(t,b,H,\Lambda)$-flower segment_ is constructed by starting
from an elementary $(t+b|\Lambda|+t,t)$-wall segment. As a first step, we add
a collection of $t$ edges joining its $t$ leftmost top and its $t$ rightmost
top vertices, as indicated by the brown edges of the rightmost drawing of
Figure 4. The construction is completed by taking, for every $j\in[q],$ $b$
copies $\langle H^{1}_{j},\Lambda^{1}_{j}\rangle,$…,$\langle
H^{b}_{j},\Lambda^{b}_{j}\rangle$ of $\langle H_{j},\Lambda_{j}\rangle$ and
connecting the $p$-th vertex of $\Lambda^{i}_{j}$ with the
$(t+(\Sigma_{j^{\prime}\in[j-1]}|\Lambda_{j-1}|)b+(i-1)|\Lambda_{j}|+p)$-th
top vertex for every $j\in[q],$ every $i\in[b],$ and every
$p\in|\Lambda_{j}|.$

The rightmost drawing in Figure 4 depicts an elementary
$(3,3,K_{3,3}^{-},\langle y_{1},y_{2}\rangle)$-flower segment, where
$K_{3,3}^{-}$ is the graph obtained from $K_{3,3}$ by deleting the edge
$y_{1}y_{2}.$ The 3 copies of $K_{3,3}^{-}$ are depicted in orange (see also
Figure 5).

#### Cylindrical concatenations and the construction of
$\mathfrak{W}_{\mathcal{H}}.$

Given a sequence $\langle W_{1},\ldots,W_{q^{\prime}}\rangle$ of $t$-segments,
we define their _cylindrical concatenation_ as the graph obtained by adding
edges (depicted in orange) between same-height rightmost (depicted in blue)
vertices of $W_{i}$ and leftmost (depicted in red) vertices of $W_{i+1}$ for
every $i\in[q^{\prime}-1].$ The construction is then completed by adding edges
between same height rightmost vertices of $W_{1}$ and leftmost vertices of
$W_{q^{\prime}}$ (see Figure 5 for an example).

Figure 5: Left: A graph $M=Z$ and a subgraph partition $\mathcal{P}$ of $M$
containing two graphs $H_{1}$ and $H_{2}.$ $H_{1}$ is drawn in the green disk
while $H_{2}$ is drawn in the violet disk. The hypergraph
$\mathcal{K}_{\mathcal{P}}$ contains the vertices $a,b,c,$ and $d$ and two
hyper-edges $e_{1}=e_{2}=\\{a,b,c,d\\}.$ The figure shows an embedding of
$\mathcal{K}_{\mathcal{P}}$ in the sphere. The choices for $Z,$ $M,$
$\mathcal{P},$ and $\eta,$ generate the embedding pair
$\mathbf{p}=(\Sigma,\mathbf{B})$ for the class $\mathsf{excl}(Z)$ where
$\mathbf{B}=\\{\langle H_{1},\langle d,b,a,c\rangle\rangle,\langle
H_{2},\langle c,a,b,d\rangle\rangle\\}.$ Right: The guest walloid
$\mathscr{W}^{\mathbf{p}}_{3}.$

Let now $\mathbf{p}=(\Sigma,\mathbf{B})$ be some embedding pair of
$\mathfrak{P}_{\mathcal{H}},$ where $\Sigma=\Sigma^{(\mathsf{h},\mathsf{c})}$
for some $\mathsf{h}\in\mathbb{N}$ and $\mathsf{c}\in[0,2].$ Let also
$\mathbf{B}=\\{(H_{1},\Lambda_{1}),\ldots,(H_{q},\Lambda_{q})\\}.$ We define
the parametric graph
$\mathscr{W}^{\mathbf{p}}=\langle\mathscr{W}^{\mathbf{p}}_{t}\rangle_{t\in\mathbb{N}},$
where $\mathscr{W}^{\mathbf{p}}_{t}$ is the cylindric concatenation of
$\langle W_{1},\ldots,W_{q^{\prime}}\rangle,$ where
$q^{\prime}=1+\mathsf{h}+\mathsf{c}+q$ and such that $W_{1}$ is the elementary
$(4t,t)$-wall segment, $W_{2},\ldots,W_{1+\mathsf{h}}$ are elementary
$t$-handle segments, $W_{1+\mathsf{h}+1},\ldots,W_{1+\mathsf{h}+\mathsf{c}}$
are elementary $t$-crosscap segments, and for $i\in[q],$
$W_{1+\mathsf{h}+\mathsf{c}+i}$ is the elementary
$(t,t,H_{i},\Lambda_{i})$-flower segment.

Notice that the above construction of $\mathscr{W}^{\mathbf{p}}$ depends on
the ordering of the elements of $\mathbf{B}$ considered. This is not a problem
for our definition as all alternative parametric graphs defined by different
orderings are pairwise equivalent (see for example the proof of Subsection 5.2
and Subsection 6.4). So we may choose an arbitrary ordering for for defining
$\mathscr{W}^{\mathbf{p}}.$

For the purposes of our construction, for every graph $Z,$ we also set up a
special symbol ${\bf p}_{Z}$ (treated as a separate “embedding pair”) and we
set $\mathscr{W}^{{\bf p}_{Z}}=\langle t\cdot Z\mid t\in\mathbb{N}\rangle$ and
$\widehat{\mathfrak{P}}^{(Z)}\coloneqq\mathfrak{P}^{(Z)}\cup\\{{\bf
p}_{Z}\\}.$ Let now $\mathcal{H}$ be a proper minor-closed class. We define
$\mathfrak{F}_{\mathcal{H}}^{\varnothing}\coloneqq\\{\mathscr{W}^{{\bf
p}_{Z}}\mid Z\in{\sf obs}(\mathcal{H})\\}.$

Let $Z_{1},\ldots,Z_{r},$ be the connected components of our graph $Z.$ We
define the following four parametric families.

$\displaystyle\mathfrak{F}^{(Z)}$ $\displaystyle\coloneqq$
$\displaystyle\big{\\{}\mathscr{W}^{\mathbf{p}_{1}}+\cdots+{\mathscr{W}}^{\mathbf{p}_{r}}\mid(\mathbf{p}_{1},\ldots,\mathbf{p}_{r})\in\widehat{\mathfrak{P}}^{(Z_{1})}\times\cdots\times\widehat{\mathfrak{P}}^{(Z_{r})}\big{\\}},$
(8) $\displaystyle\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$
$\displaystyle\coloneqq$
$\displaystyle\big{\\{}\mathscr{W}\in{\boldsymbol{\bigcup}}\\{\mathfrak{F}^{(Z)}\mid{Z\in{\sf
obs}(\mathcal{H})}\\}\mid\text{for every
$\mathscr{W}^{\prime}\in\mathfrak{F}_{\mathcal{H}}^{\varnothing}$ it holds
that $\mathscr{W}^{\prime}\not\lesssim\mathscr{W}$}\big{\\}},$ (9)
$\displaystyle{\mathfrak{F}}_{\mathcal{H}}$ $\displaystyle\coloneqq$
$\displaystyle\mathfrak{F}^{\nicefrac{{1}}{{2}}}_{\mathcal{H}}\cup\mathfrak{F}_{\mathcal{H}}^{\varnothing},\text{\leavevmode\nobreak\
and}$ (10) $\displaystyle{\mathfrak{F}}_{\mathcal{H}}^{\mathsf{min}}$
$\displaystyle\coloneqq$
$\displaystyle\mathsf{min}({\mathfrak{F}}_{\mathcal{H}}).$ (11)

As we already mentioned in the beginning of this section, all parametric
families defined by the minimization in (10) are $\lesssim$-antichains. All of
these minimizations, for a fixed class $\mathcal{H},$ are pairwise equivalent,
and, in particular, they are equivalent to the set that they minimize.
Therefore, the definitions for $\mathfrak{F}_{\mathcal{H}}$ and
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ are unique up to
equivalence and we may take an arbitrary representative.

#### Examples and the obstructing sets for $\mathcal{H}$-treewidth.

An important special case in the construction above is any choice
$\mathcal{H}={\sf excl}(Z)$ where $Z$ is a connected planar graph. Then
$\mathfrak{P}^{(Z)}$ contains (among others) the pair
$(\Sigma^{(0,0)},\emptyset).$ This implies that
$\mathsf{min}(\\{\mathscr{W}^{\mathbf{p}}\mid\mathbf{p}\in\widehat{\mathfrak{P}}^{(Z)})$
(as in (10)) contains only the cylindrical concatenation of the $(4t,t)$-wall
segment. Moroever, the minimization in $\eqref{second_walloid_formula}$ then
“absorbs” this wall into $\mathscr{W}^{{\bf p}_{Z}}=\langle k\cdot
P\rangle_{k\in\mathbb{N}}.$ This means that
$\mathfrak{F}_{\mathcal{H}}=\mathfrak{F}_{\mathcal{H}}^{\varnothing}$ and
therefore $\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}=\emptyset.$

We now define the two new parametric families which act as our obstructing
sets for $\mathcal{H}$-treewidth.

$\displaystyle\mathfrak{W}_{\mathcal{H}}$
$\displaystyle\coloneqq\\{\mathscr{W}^{\mathbf{p}}\mid\mathbf{p}\in\mathfrak{P}^{(Z)}\
\text{and}\ Z\in{\sf obs}(\mathcal{H})\\}\text{ and}$ (12)
$\displaystyle\mathfrak{W}_{\mathcal{H}}^{\mathsf{min}}$
$\displaystyle\coloneqq\mathsf{min}(\mathfrak{W}_{\mathcal{H}})$ (13)

Notice that the definition of $\mathfrak{W}_{\mathcal{H}}$ above and the
definition of ${\mathfrak{F}}_{\mathcal{H}}$ in (8) and (10) differ in two
aspects: The first is that we now use $\mathfrak{P}^{(Z)}$ instead of the more
enhanced $\widehat{\mathfrak{P}}^{(Z)}$ and the second is that we do not have
to go through an additional construction step such as (8). This readily
implies that
$\mathfrak{F}_{\mathcal{H}}\lesssim^{*}\mathfrak{W}_{\mathcal{H}}.$

Let us give another simple, but less trivial, example for the construction of
$\mathfrak{F}_{\mathcal{H}}.$ This time we discuss the case where
$\mathcal{H}={\sf excl}(K_{3,3}).$ Notice that
$\mathbb{S}^{(\\{K_{3,3}\\})}=\\{\Sigma^{(0,0)},\Sigma^{(1,0)},\Sigma^{(0,1)}\\},$
i.e., $\mathbb{S}^{(K_{3,3})}$ contains the sphere, the torus, and the
projective plane. Next, observe that for each
$\Sigma\in\\{\Sigma^{(1,0)},\Sigma^{(0,1)}\\}$ its holds that
$(\Sigma,\emptyset)\in\mathfrak{P}^{(K_{3,3})}$ and that for every other
$(\Sigma,\mathbf{B})\in\mathfrak{P}^{(K_{3,3})}$ we have that
$\mathscr{W}^{{(\Sigma,\emptyset)}}\lesssim\mathscr{W}^{(\Sigma,\mathbf{B})}.$
Therefore $\mathfrak{F}_{\mathsf{excl}(K_{3,3})}$ should contain the
cylindrical concatenation of the elementary $t$-wall segment and the
elementary $t$-handle segment as well as the cylindrical concatenation of the
elementary $t$-wall segment and the elementary $t$-crosscap segment. For
$t=3,$ these graphs are depicted in Figure 1. Let us now examine the
parametric graphs in $\mathfrak{W}_{\mathcal{H}}$ that are generated by
choosing the sphere as the surface $\Sigma.$ As $K_{3,3}$ cannot be embedded
in $\Sigma^{(0,0)}$ we have to consider some non-trivial subgraph partition
$\mathcal{P}$ of $K_{3,3}.$ It is easy to observe that for every
$(\Sigma^{(0,0)},\mathbf{B})\in\mathfrak{P}^{(K_{3,3})}$ it holds that
$\mathscr{W}^{{(\Sigma^{(0,0)},\mathbf{B}^{\prime})}}\lesssim\mathscr{W}^{(\Sigma^{(0,0)},\mathbf{B})}$
where $\mathbf{B}^{\prime}=\\{(K_{3,3},\langle y\rangle)\\}$ and $y$ is an
arbitrary vertex of $K_{3,3}.$

Thus, $\mathscr{W}^{{(\Sigma^{(0,0)},\mathbf{B}^{\prime})}}$ is the only
parametric graph that has some chance of surviving in
$\mathfrak{F}^{\mathsf{min}}_{\mathsf{excl}(K_{3,3})}$ among those generated
by the sphere. But this chance is further lost because $\mathscr{W}^{{\bf
p}_{K_{3,3}}}=\langle t\cdot Z\mid
t\in\mathbb{N}\rangle\lesssim\mathscr{W}^{{(\Sigma^{(0,0)},\mathbf{B}^{\prime})}}.$
So all parametric graphs generated by the sphere are absorbed by
$\mathfrak{F}_{\mathsf{excl}(K_{3,3})}^{\varnothing}.$ Therefore
$\mathfrak{F}_{\mathsf{excl}(K_{3,3})}^{\nicefrac{{1}}{{2}}}$ is as announced
in Figure 1. The same analysis holds if, instead of $K_{3,3},$ we consider any
minor-closed graph class excluding some single-crossing minor.

As asserted by our main result, Theorem 1.1,
$\mathfrak{F}_{\mathcal{H}}^{\nicefrac{{1}}{{2}}}$ provides a precise and
finite delineation of the half-integrality for $\mathcal{H}.$ In the next
subsection, we give some further intuition why this is the case.

###  1.6 A (more) detailed outline of the proof of Theorem 1.2.

The proof of Theorem 1.1 we presented at the end of Subsection 1.2 utilized as
a core tool Theorem 1.5 which, in turn, can be obtained from Theorem 1.4. Let
us begin by giving a short description of how we obtain Theorem 1.4 from the
local structure theorem Theorem 1.2.

#### Balanced $\mathcal{H}$-separators and wall(oid)s.

A core concept from the (algorithmic) theory of tree decompositions is the
notion of “well-linked” sets and balanced separators [60]. We define analogues
of these concepts with respect to a graph class $\mathcal{H}.$ A similar
concept has been used by Jansen, de Kroon, and Włodarczyk [32] in their
approximation algorithm for $\mathcal{H}$-treewidth.

A set $X\subseteq V(G)$ is $k$-$\mathcal{H}$-linked if for every set
$S\subseteq V(G)$ of size at most $k-1$ there exists a component $K$ of $G-S$
such that $|V(K)\cap X|\geq\frac{2}{3}|X|,$ and $K\notin\mathcal{H}.$ This
means that whenever we delete few vertices, most of $X$ still belongs to some
subgraph of $G$ which contains an obstruction of $\mathcal{H}.$ It is
straightforward to verify that any graph with a $k$-$\mathcal{H}$-linked set
must have $\mathcal{H}$-treewidth at least $k.$ Moreover, under the assumption
that there are no $k$-$\mathcal{H}$-linked sets in $G$ one can construct a
tree-decomposition that witnesses small $\mathcal{H}$-treewidth using standard
arguments.

Since the existence of a highly $\mathcal{H}$-linked set $X$ implies large
$\mathcal{H}$-treewidth, it, in particular, implies large treewidth. By using
the Grid Theorem [62, 12] together with some arguments from [39] we are able
to find a large wall which is “associated”151515Formally speaking and to help
a reader familiar with the terminology of graph minors, the tangle of the wall
agrees with the tangle of the highly linked set. with our highly
$\mathcal{H}$-linked set. This wall may now be used as the input for an
application of Theorem 1.2. Finally, since the wall and $X$ are “associated”,
it is impossible that the second outcome of Theorem 1.2 holds. Therefore,
Theorem 1.4 follows from the parametric equivalence between the largest number
$k$ for which a graph has a $k$-$\mathcal{H}$-linked set and
$\mathcal{H}$-treewidth together with Theorem 1.2.

In the remainder of this section, we give a more detailed overview of our
proof for Theorem 1.2 and the techniques involved. As mentioned earlier, we
prove a more general theorem, that is Theorem 1.6, which yields the outcome of
Theorem 1.2 for all proper minor-closed graph classes $\mathcal{H}$ with
$h(\mathcal{H})\leq h$ simultaneously. In most of the discussion that follows,
we focus on a single graph $Z$ on at most $h$ vertices for ease of
presentation.

Let $\Sigma=\Sigma^{(\mathsf{h},\mathsf{c})}$ be some surface. We define the
parametric graph
$\mathscr{W}^{(\mathsf{h},\mathsf{c})}=\langle\mathscr{W}^{(\mathsf{h},\mathsf{c})}_{t}\rangle_{t\in\mathbb{N}}$
where $\mathscr{W}^{(\mathsf{h},\mathsf{c})}_{t}$ is obtained from the
cylindrical concatenation of a single $t$-wall segment, $\mathsf{h}$
$t$-handle segments, and $\mathsf{c}$ $t$-crosscap segments. A key tool we
borrow from [77] is an algorithm that takes as an input some graph $G$ and a
large wall $W$ together with integers $t,$ $k,$ and $g.$ This algorithm then
returns one of three things.

  1. 1.

a $K_{k}$-minor,

  2. 2.

a subdivision of $\mathscr{W}_{t}^{(\mathsf{h},\mathsf{c})}$ where
$g=2\mathsf{h}+\mathsf{c},$ or

  3. 3.

a small “apex” set $A\subseteq V(G)$ together with a so-called
$\Sigma$-decomposition $\delta$ of $G-A$ which “respects” the wall $W,$ where
the Euler-genus of the surface $\Sigma$ is
$2\mathsf{h}^{\prime}+\mathsf{c}^{\prime}<g$ for appropriate choices of
$\mathsf{h}^{\prime}$ and $\mathsf{c}^{\prime},$ and a subdivision $W_{1}$ of
$\mathscr{W}_{t}^{(\mathsf{h}^{\prime},\mathsf{c}^{\prime})}$ which is also
“respected” by $\delta.$ Moreover, the number and depth of the vortices of
$\delta$ is bounded in some function in $t$ and $k.$

For most intents and purposes, one may think of a $\Sigma$-decomposition as an
almost-embedding where the depth of the vortices is not bounded. The way
$\delta$ “respects” $W$ and $W_{1}$ may be understood as: they appear as
subdivisions in $G^{(0)}$ when $\delta$ is understood as a $0$-almost
embedding. See Subsection 2.2 for a full definition of
$\Sigma$-decompositions.

An alternative way to understand a $\Sigma$-decomposition $\delta$ is through
subgraph partitions and their hypergraphs as follows. On an intuitive level,
one may see $\delta$ as an embedding of the hypergraph
$\mathcal{K}_{\mathcal{P}}=(V_{\mathcal{P}},\mathcal{E}_{\mathcal{P}})$ in
$\Sigma^{(\mathsf{h}^{\prime},\mathsf{c}^{\prime})}$ where
$\mathcal{P}\in\mathcal{P}(G)$ is a subgraph partition of $G$ where only a
bounded number of hyperedges have size $\geq 4.$ Moreover, each hyperedge
$e\in\mathcal{E}_{\mathcal{P}}$ is seen as a disk $c,$ called _cell_ of
$\delta$ where the graph $G_{c}\coloneqq G_{e}$ is drawn (possibly with
crossings) inside $c$ and the vertices of $e$ are drawn on the boundary $c$ in
some liner ordering $\Lambda_{c}.$ We call a cell with at least $4$ vertices
drawn on their boundary a _vortex_ while we call the others _flaps_. This
defines a linear society $(G_{c},\Lambda_{c})$ that has bounded depth in the
sense that there is no big flow in $G_{c}$ from some set $Q\subseteq e$ of
vertices appearing consecutively on ${\sf bd}(\Delta)$ to $e\setminus Q$ (we
call such a flow a _transaction_ of the linear society $(G_{c},\Lambda_{c})$).
Part of the outcome of the algorithm from [77] (originally proven in [39])
ensures also that all vortices are situated “inside” the biggest cycle of
$W_{1}.$ We refer to this cycle as the _exceptional cycle_ of $W_{1}$ (see
Figure 6 for a visualization). We refer to the set $V_{\delta}\coloneqq
V(V_{\mathcal{P}})$ as the set of _ground vertices_ of $\delta.$

By editing the $\Sigma$-decomposition $\delta$ and collecting everything that
is drawn in the unique disk defined by the exceptional cycle of $W_{1}$ which
avoids all of the other cycles of $W_{1}$ into a single cell, we obtain a new
$\Sigma$-decomposition $\delta_{1}$ of $G_{1}\coloneqq G-A.$ This produces a
triple $(G_{1},\delta_{1},W_{1})$ which represents the arable land mapped out
by $W_{1}.$ At this stage, we call the triple $(G_{1},\delta_{1},W_{1})$ a
_$(t,\Sigma)$ -meadow_.

From here on, we begin a sequence of cultivation steps that turn the wildly
grown meadow into a neatly organized orchard whose “flowers” are ready for the
harvest. Below we provide a description of the individual steps and provide a
sketch of how these ultimately lead to Theorem 1.2.

For the purpose of our proofs, it is helpful to consider a specific type of
witness for the existence of a graph $Z$ as a minor. We call these objects
extensions of $Z$ and they are defined in Subsection 7.5. For the purpose of
this introduction, it suffices to think of an extension as a subgraph $M$ of
$G$ which is minimal with respect to the following properties: 1) $M$ contains
$Z$ as a minor, 2) $M$ is connected, 3) $M$ contains a vertex of $W_{1},$ and
4) the total number of vertices of $M$ whose degree is different from two is
bounded by some function in $|Z|$ which will be determined later. In our
proofs we do not actually require property 3), but our arguments are tailored
to specifically deal with extensions of this type. Moreover, 4) is not part of
the actual definition of an extension of $Z,$ but an integral part of the
content of Section 7 and Section 8 is to prove that it suffices to only
consider extensions of this type.

#### Plowing the meadow.

Notice that all but one cell of $\delta_{1}$ are flaps. For each flap we
define a set $\mathsf{folio}(G_{c},\Delta_{c})$ that encodes all possible ways
an extension of $Z$ may “invade” the linear society $(G_{c},\Lambda_{c}).$ We
also define the set $\mathsf{folio}(\delta_{1})$ as the union of all possible
folios of the flaps of $\delta_{1}.$ We will show that the size of this set is
bounded by a function in $|Z|.$ We now divide the non-vortex part of
$\Sigma=\Sigma^{(\mathsf{h}^{\prime},\mathsf{c})^{\prime}}$ into
$2\mathsf{h}^{\prime}+\mathsf{c}^{\prime}+1$ _enclosures_ , which are areas
that may be treated separately throughout our cultivation process. In Figure 6
we provide an example of such a division. Each face $F,$ with respect to
$\delta_{1},$ of an enclosure is called a _brick_ and we define
$\mathsf{folio}(F)$ to be the union of all folios of the flaps that are either
fully inside or on its boundary.

Our first step is to plow the meadow and thereby prepare it for further
cultivation. That is we homogenize it by updating the triple
$(G_{1},\delta_{1},W_{1})$ to a new triple $(G_{1},\delta_{2},W_{2})$ such
that for every enclosure $C$ of the new walloid $W_{2},$ all bricks of $C$
have the same folio. This is done by both “merging” bricks of
$(G_{1},\delta_{1},W_{1})$ and by “pushing” some of the flaps of $\delta_{1}$
into the exceptional face of $W_{2}.$ Notice that such a process comes at a
great price in terms of the order of the walloid $W_{1}$ and thus $W_{1}$ must
be chosen to be enormous from the beginning. This completes the plowing
procedure.

Figure 6: A $(t,\Sigma^{(2,2)})$-meadow with two handle segments and two
crosscap segments. The black line is the boundary of the exceptional face and
the red line is the boundary of the simple face. The colored territories are
the enclosures of $W.$ The vortices are represented by the gray polygons and
are all inside the exceptional face.

#### Sowing a garden.

So far we have prepared our meadow and turned it into a field ready to receive
the seeds that will eventually grow into the flowers and trees of our orchard.
Towards this goal, the next step on our agenda is to plant the first flowers.
This means that we are going to represent every linear society $(H,\Lambda)$
in $\mathsf{folio}(\delta_{2})$ by “planting” a sequence of $h\coloneqq|Z|$
many consecutive $(t,b,H,\Lambda)$-flower segments in our meadow. We refer to
the newly created “super segment” consisting of all these flower segments as a
$(t,b,h,H,\Lambda)$-_parterre segment_ where $b$ is a function in $k.$ The key
feature of our plowed meadow $(G_{1},\delta_{2},W_{2})$ that allows for this
procedure is the homogeneity of its enclosures which implies that every
society in $\mathsf{folio}(\delta_{2})$ appears in abundance. This allows us
to rearrange $W_{2}$ in a way that such parterre appears on the boundary of
the exceptional face. Once this process is complete, we have obtained a new
triple $(G_{1},\delta_{2},W_{3})$ called a (blooming) _$(t,b,h,\Sigma)$
-garden_. This garden now contains, for each member $F$ of
$\mathsf{folio}(\delta_{2})$ a parterre segment whose flowers represent this
particular $F.$ Notice that $\delta_{2}$ still has only one vortex of
(possibly) unbounded depth which sits in the exceptional face of $W_{3}.$

Figure 7: A $(t,b,h,\Sigma^{(2,2)})$-garden with two handle segments, two
crosscap segments, two parterre segments each containing three flower segments
of two distinct linear societies (depicted in red and green). Each society
appears 4 times inside each flower.

#### Growing an orchard.

With $(G_{1},\delta_{2},W_{3})$ we have reached a first milestone in the
cultivation of our farmland. What is left is the wilderness in the form of the
huge vortex that has been created in the exceptional face of $W_{3}$ during
the previous steps. The time has come to conquer this jungle and expand the
arable land until the remaining wilderness is confined to a small number of
rich biotopes that allow for other means of exploration.

To put our plan for the next step into more technical terms: In the previous
steps, we have given up on our vortices of bounded depth in order to achieve a
form of homogenization with respect to the folio of the enclosures of $W_{3}.$
We now want to expand the homogeneous area and recreate (a possibly larger
number of) the vortices of bounded depth. This might create a new type of
vortex: Before a vortex was a cell that could not be embedded in a disk in a
way that agrees with our $\Sigma$-decomposition $\delta_{2}.$ Now, some
vortices might actually have such a “flat rendition”, but for every such
rendition we choose, the folio of one of its flaps will contain a linear
society $\langle H,\Lambda\rangle$ that is not abundant. This means that,
apriori, we do not have enough copies of $\langle H,\Lambda\rangle$ available
to create a large enough parterre segment for this kind of flower.

To fully formalize the new target structure, we need to introduce a new type
of $t$-segment: a $(t,s)$-thicket segment. While before we always attached
flowers or edges in a very structured manner to the top vertices of a $t$-wall
segment, now we have to be a bit more lax. We select a collection of $s$
concentric cycles $\mathcal{C}=\\{C_{1},\dots,C_{s}\\},$ called the nest, all
of which are drawn in $\delta_{2},$ and extend the vertical paths of our
$t$-wall segment beyond the top vertices, letting the resulting paths traverse
the cycles of $\mathcal{C}$ and reaching the “inner” area, that is the disk
$\Delta$ of $\Sigma$ which is enclosed by the closed curve that represents
$C_{1}$ in $\delta_{2}.$ These paths are called the rails of the thicket. We
then require that within this disk $\Delta$ there exists a single vortex of
$\delta_{2}.$ A triple $(G^{\prime},\delta^{\prime},W^{\prime})$ is now called
a $(t,b,h,s,\Sigma)$-orchard if it can be seen as a $(t,b,h,\Sigma)$-garden
when pushing all of its thicket segments back into a single vortex, and there
exists a $(t,s)$-thicket segment for every vortex of $\delta^{\prime}.$ See
Figure 8 for an illustration. Notice that each thicket segment induces its own
linear society based on the outer-most cycle $C_{s}$ of its nest. This allows
us to define the depth of a thicket in the same way we defined the depth of a
vortex above. Our goal now is to create more and more thicket segments, until
all thickets are of bounded depth or we have created a parterre segment for
each possible flower (recall that there are only finitely many possible
flowers because we are only interested in flowers of bounded “detail”).

Since $\delta_{2}$ has a single vortex, we may immediately interpret
$(G_{1},\delta_{2},W_{3})$ as an $(t,s)$-orchard with a single
thicket161616This transformation actually requires to sacrifice a bit of the
infrastructure of $W_{3}$ as observed in Section 6 but for ease of
presentation we skip this very minor transformation step.. Before we describe
the process of “splitting” a single thicket segment let us quickly discuss why
there exists an upper bound on the total number of thicket we have to consider
at any point in time. For this, observe first that the original
$\Sigma$-decomposition $\delta_{1}$ had a bounded number, say $x,$ of vortices
that contained an actual obstruction to disk-embeddability. Let us call these
vortices the real vortices for now. These vortices were already of bounded
depth and we may use this fact to show that there can never be more than $x$
real vortices at any point in time. A parterre segment requires us to have
$h\cdot b$ many isomorphic flowers. Moreover, since the “detail” of the
flowers we are interested in is bounded by some number, say $d,$ there are at
most $\mathsf{d}=2^{2^{\mathcal{O}(d^{2})}}$ many possible folios (see
Subsection 2.3). This means, if we ever have more than $h\cdot
b\cdot\mathsf{d}^{2}$ thicket segments whose vortices are not real, then there
must be $h\cdot b\cdot\mathsf{d}$ many, all with the same folio. Let
$\mathcal{F}$ be this folio. This gives us the right, using the infrastructure
provided by the rails and the nests of these thickets, to extract a large
enough parterre segment for each member of $\mathcal{F}$ and afterward, the
thicket segments with folio $\mathcal{F}$ can be discarded. This means that we
have an upper bound on the total number of thickets present at any given point
in time of our procedure.

Figure 8: Left: a $(t,b,h,s,\Sigma^{(2,2)})$-orchard with one $(s,t)$-thicket
and a big transaction traversing it (in black). The black vertices mark the
boundary of the thicket society. Right: the result of splitting a thicket
along this transaction and creating a new parterre. The magenta vertices form
the base of the thicket.

We are now ready to describe the operation of “splitting” a thicket. For this,
we consider a large transaction on the linear society defined by the outer-
most cycle of the nest. We may assume that such a transaction exists since
otherwise the thicket is of bounded depth and there is nothing to be done.
Moreover, since there are at most $x$ real vortices and all of them are of
bounded depth, which is already certified by $\delta_{1},$ we may assume that
the “area” defined by the transaction can be used to extend $\delta_{2}$ by
reintegrating a part of $\delta_{1}$ that was forgotten earlier. Such a
transaction is depicted in the left part of Figure 8. When we have found this
new “flat” area, we may use the same arguments as those used for the plowing
step above to further refine the transaction into a homogenized area with
respect to the folios of its cells. In case we find a linear society in these
folios that has not been represented in a parterre segment of $W_{3},$ we may
now use the infrastructure provided by the rails and the nest of the thicket,
together with the paths of the transaction, in order to extract additional
parterre segments. An illustration of this can be found in the right part of
Figure 8. Finally, the paths of the transaction, together with the cycles of
the nest $\mathcal{C}$ now define up to two new disks in the area that was a
single vortex before. By making use of the paths in the transaction, the nest,
and the rails, this allows to “split’ the thicket into up to two new thicket
segments as depicted in Figure 8. Please notice that all of the operations
described here require the sacrifice of some part of our infrastructure.
However, as discussed above, the total number of thickets and the total number
of folios, and therefore parterre segments, is bounded. This means that any of
these steps can only occur a bounded number of times and thus, by choosing the
infrastructure provided by $(G_{1},\delta_{2},W_{3})$ to be large enough in
the beginning, we make sure to always have enough “space” available.

Eventually, the extraction operations above will not be available anymore. We
might still find more large transactions on the societies of our thickets, but
these transactions can now only create new nests that are increasingly “tight”
around the vortices. Finally, the entire process must come to a halt and when
this happens, all of our thickets are of bounded depth. We call the resulting
triple $(G_{1},\delta_{3},W_{4})$ a ripe $(t,b,h,s,\Sigma)$-orchard. See
Figure 9 for an illustration.

Figure 9: A ripe $(t,b,h,s,\Sigma^{(2,2)})$-orchard: All vortices (one for
each thicket) are of bounded depth together with some extension $Z^{\prime}$
of a graph $Z$ (black) invading (some of) the thickets. This extension goes
through flaps and orchards. Each flap is $k$-fold represented in a flower and
each orchard can also be seen as a flower. In the figure, the red and the blue
linear societies of $Z^{\prime}$ are located inside flaps and are represented
by blue and red flowers inside the corresponding parterre.

#### Harvesting.

We next focus our attention on how the ripe $(t,b,h,s,\Sigma)$-orchard
$(G_{1},\delta_{3},W_{4})$ can be traversed by an extension $M$ of some graph
$Z$ where $|Z|\leq h.$ As we already mentioned, $M$ has a bounded (by some
quadratic function in $|Z|$) number of vertices of degree different from two.
We call these vertices _terminals_ of $M.$ As we argued before, the ways $M$
may visit the flaps of $\delta$ are already represented by the flowers of the
parterres. So we should fix our attention on how $M$ may invade the non-flat
cells of $\delta,$ i.e., its vortices. recall that each vortex sits deep
inside the thickets and consider $\Delta$ to be a disk around each vortex $c$
defined as the are enclosed by the closed curve that is the outermost cycle of
a given thicket segment of $(G_{1},\delta_{3},W_{4}).$ Since
$(G_{1},\delta_{3},W_{4})$ is ripe, there are only few vortices and therefore
few disks as above, and the depth of both the given vortex as well as the
society defined by $\Delta$ is bounded by some function in $h$ and $k.$

Next, we fix our attention to the part of $M$ which is drawn inside the disk
$\Delta.$ Let us denote this part of $M$ by $M_{\Delta}.$ Also, we use
$T_{\Delta}$ for the terminals of $M$ that are drawn inside $\Delta.$ This
defines the notion of a fiber $\mu=(M_{\Delta},T_{\Delta},\widehat{\Lambda})$
where $\widehat{\Lambda}$ is a cyclic ordering of the vertices of $M$ that are
drawn on the boundary of $\Delta$ in the order they appear in
$\widehat{\Lambda}.$ While the number of terminals of any fiber is bounded, we
cannot say the same for its boundary vertices, i.e., for the vertices in
$\widehat{\Lambda}.$ For this, we consider fibers whose boundary has size at
most $b,$ let us call them $b$-fibers, and we prove a local Erdős-Pósa duality
on how they may be covered or packed inside $\Delta$ with respect to the
boundary of $\Delta.$ This is done by the so-called harvesting procedure which
either finds a set that intersects any $b$-fiber or finds a sequence of a big
enough number of copies of such $b$-fibers which are well arranged on the
boundary of $\Delta$ in the form of a “primitive flower” (Section 7).

We see a $b$-fiber as being drawn inside the union of some collection of sub-
disks of $\Delta,$ called _pseudo-disk_. Here, the number of vertices drawn in
the boundary of this pseudo-disk is bounded by some function in the depth of
the vortex $c$ and the depth of the disk $\Delta$ (see Subsection 7.2). While
the depth of both is bounded in a function in $h$ and $k,$ we are able to show
that, for a single $b$-fiber, the “depth” of its drawing now only depends on
$h.$ For the harvesting procedure, we define the notion of a critical pseudo-
disk that “critically” contains a $b$-fiber $\mu$ in the sense that $\mu$ is
not contained in any of its proper pseudo-disks (Subsection 7.3). Then we pick
a $b$-fiber $\mu$ and we detect a packing of critical pseudo-disks containing
$\mu$ (Subsection 7.4). If “enough”, where the value for enough depends on a
specific function in $k$ and $h,$ of them are found we can organize them into
packages each containing many, say $k,$ copies of each of the sub-fibers
corresponding to the elements of $\mathsf{dec}(M_{\Delta},\widehat{\Lambda}).$
This collection of packages will be the primitive form of a flower, parts of
which will constitute some of the flower segments of our parametric graphs. If
only few critical pseudo-disks are found, we may consider the vertices of the
boundaries of their disks in order to find a covering of all $b$-fibers of
$\Delta$ that are isomorphic to $\mu.$ The size of this set is bounded by a
function in $k$ and $h.$ The union of all these covering sets for all possible
fibers of boundary at most $d$ is the $(d,k)$-cover of the disk $\Delta.$
Recall that fibers were defined as ways that an extension $M$ enters the disk
$\Delta$ and thus, this $(d,k)$-cover should now constitute a hitting set for
all such fibers which are not abundant on the boundary of $\Delta.$ We next
prove that we may choose $d$ so that if $S$ is a $(d,k)$-cover of the disk
$\Delta,$ then every restriction $M_{\Delta}$ of an extension $M$ in $\Delta$
that defines a fiber with more than $d$ boundary vertices and which is not
covered by $S$ can be rearranged to one that defines a $d$-fiber and still is
not intersected by $S$ (Subsection 7.5). The proof of this applies a global
rerouting of $M,$ based on the unique linkage theorem and some suitable
adaptation of it to our needs (Subsection 3.2). The proof also uses the fact
that $S$ resides on the union of disk boundaries and strongly uses the
topological properties of these disks as well as the cycle collection
$\mathcal{C}$ insulating the vortex $c$ from $\Delta.$ This means that
whenever $S$ is not a covering of our model $M$ some part of this model, in
the form of a collection of packages of $k$ fibers can be found inside
$\Delta$ as desired. Moreover, the above choice of $d$ is bounded by some
function in $h.$ This implies that it is enough to “pack” or “cover”
$b$-fibers, for his particular value of $b,$ instead of fibers in general.
Therefore, the $(d,k)$-cover of the disk $\Delta$ is bounded by some function
in $k$ and $h.$ We now define $S_{\Delta}$ as the union of all the
$(d,k)$covers of all the disks $\Delta,$ as above, corresponding to the
thickets of the $(t,b,h,s,\Sigma)$-orchard $(G_{1},\delta_{3},W_{4}).$ We
denote this collection of disks by $\mathbf{\Delta}$ and define
$S_{\mathsf{all}}$ to be the union of the (already bounded) apex set $A$ from
the very beginning and $\bigcup_{\Delta\in\mathbf{\Delta}}S_{\Delta}.$
Clearly, $|S_{\mathsf{all}}|$ is bounded by a function in $h$ and $k$ and by
the number of thickets of $(G_{1},\delta_{3},W_{4})$ which is also bounded by
some function in $k$ and $h.$

#### Plowing flowers from thickets.

Our next step is to analyze how the Erdős-Pósa duality for objects “anchored”
on the society of a vortex from the previous step interacts with the overall
way an extension $M$ of $Z$ may be situated within our
$(t,b,h,s,\Sigma)$-orchard $(G_{1},\delta_{3},W_{4})$ and its thickets. It
follows that if $S_{\mathsf{all}}$ intersects every extension of $Z$ that is
“bound” to $\delta$ (i.e., it contains a vertex of $W_{4}$; for the formal
definition, see Subsection 2.2), then the component of $G-S_{\mathsf{all}}$
which contains the majority of $W_{4}-S_{\mathsf{all}}$ is $Z$-minor-free and
this is the second outcome of the (simplified) local structure theorem
(Theorem 1.2).

Figure 10: A subdivision of a walloid in $\mathscr{W}^{\mathbf{p}}$ (in black)
inside an orchard.

Assume now that there is an extension $M$ of $Z$ which is not intersected by
$S_{\mathsf{all}}.$ Then, due to the Erdős-Pósa property above, the parts of
$M$ corresponding to the disks $\Delta\in\mathbf{\Delta^{\prime}}$ are
organized as a sequence
$\mathcal{M}_{1}^{\Delta},\ldots,\mathcal{M}_{p}^{\Delta}$ of consecutive
“packages”, each containing $k$ vertex disjoint and pairwise isomorphic sub-
fibers emerging from the decomposition of some $\Delta$-invading fiber. At
this point, we observe that among these sub-fibers, only those that invade the
corresponding vortices are of interest as all others, being drawn in the flat
parts of $\delta,$ are already represented in the parterre of
$(G_{1},\delta_{3},W_{4}).$ Also, it follows from the results in Subsection
3.2 than the number of disks intersected by $M,$ we denote the set of these
disks by $\mathbf{\Delta}^{\prime}\subseteq\mathbf{\Delta},$ is also bounded
by some function in $h.$ Let $\Sigma^{\mathsf{c}}$ be the closure of
$\Sigma\setminus\bigcup_{\Delta\in\mathbf{\Delta}^{\prime}}\Delta.$ We now
observe that the part of $M,$ call it $M^{\mathsf{c}},$ that is drawn outside
the disks of $\mathbf{\Delta}^{\prime}$ is drawn in $\Sigma$ in a “flat way”
as all invaded vortices are inside the disks. This drawing is encoded as a
$\Sigma^{\mathsf{c}}$-decomposition of $M^{\mathsf{c}}$ and constitutes a
certificate of the flatness of $M$ outside the disks of
$\mathbf{\Delta}^{\prime}.$ In Subsection 8.1 we formalize this flatness
certificate via the concept of a $\Sigma$-flat $Z$-certifying complement of
$\\{\mu_{\Delta}\mid\Delta\in\mathbf{\Delta}^{\prime}\\}.$ Observe now that
the fibers in the packages
$\mathcal{M}_{1}^{\Delta},\ldots,\mathcal{M}^{\Delta}_{p^{\Delta}}$ are close
to the structure of a flower based on $M_{\Delta}.$ However, these fibers are
rooted on the boundary of $\Delta$ and we need their boundaries to be in the
base of the thicket corresponding to $\Delta$ in order to see them as a
flower. For this, we prove a special variant of the combing lemma from [26] in
Subsection 8.3. This lemma permits a rerouting that, after sacrificing a
considerable amount of the fibers, revises
$\mathcal{M}_{1}^{\Delta},\ldots,\mathcal{M}^{\Delta}_{p^{\Delta}}$ so that it
is indeed rooted at the base of the thicket corresponding to $\Delta,$ for
every $\Delta\in\mathbf{\Delta}^{\prime}$ (Subsection 8.4). Later we
additionally use the surrounding infrastructure of the corresponding thickets
in order to interpret all thickets whose vortices are invaded by $M$ as
flowers. All of these transformations have as a starting point a sequence of
packages $\mathcal{M}_{1}^{\Delta},\ldots,\mathcal{M}^{\Delta}_{p^{\Delta}},$
for each $\Delta\in\mathbf{\Delta}^{\prime},$ corresponding to a collection of
fibers that admit some $\Sigma$-flat $Z$-certifying complement. In our proofs,
this flat complement certification property stays invariant for all revised
packages. We now arrived in a situation where all parts of $M$ that are
embedded outside of the vortices of $(G_{1},\delta_{3},W_{4})$ are represented
by the flowers of its parterres while the parts of $M$ that are invading the
vortices, i.e., the vortices of the disks in $\mathbf{\Delta}^{\prime},$ are
fibers corresponding to sequences of packages that permit us see the thickets
as flowers of these fibers. Let $M^{\prime}$ be the graph obtained by
considering all boundary vertices of the fiber $\mu_{\Delta}$ generated by $M$
as terminal vertices. This defines a subdivision of a graph whose size is
bounded by some function in $h$ that contains $Z$ as a minor. As we prove in
Subsection 9.1, this function is the function ext used in the definition of
embedding pairs. Next, using the graph $M^{\prime},$ we interpret the
subgraphs of $M^{\prime}$ drawn in the cells of the flat complement
$\delta^{\mathsf{c}}$ and the graphs drawn in the disks of
$\mathbf{\Delta}^{\prime}$ as a subgraph partition $\mathcal{P}$ of
$M^{\prime}$ and this, in turn, defines an embedding pair
$\mathbf{p}=(\Sigma,\mathbf{B})$ where $\mathbf{B}$ contains societies that
are either the parts of $M^{\prime}$ drawn in the flaps of
$\delta^{\mathsf{c}}$ (which are also flaps of $\delta$) or the parts of
$M^{\prime}$ that are the fibers in
$\\{\mu_{\Delta}\mid\Delta\in\mathbf{\Delta}^{\prime}\\}.$ As we already
noticed, the first category of societies is already present in the parterres
of $(G_{1},\delta_{3},W_{4})$ and the second category of societies is present
as flowers inside the thickets. As a consequence of this, a subdivision of
some big enough walloid in $\mathscr{W}^{\mathbf{p}}$ can be found as a
subgraph of $G$ (see Figure 10). This gives the first outcome of the
(simplified) local structure theorem (Theorem 1.2).

##  2 Preliminaries

In this section, we present the bulk of definitions that will be necessary for
the development of the proofs in the following sections.

###  2.1 Basic concepts

In this first subsection, we present the basic concepts we require about sets,
integers, and graphs.

#### Sets and integers.

We denote by $\mathbb{N}$ the set of non-negative integers, by
$\mathbb{N}_{\geq n},$ $n>1,$ to be the set
$\mathbb{N}\setminus\\{m\in\mathbb{N}\mid m<n\\},$ and by
$\mathbb{N}^{\mathsf{even}}$ the set of even numbers in $\mathbb{N}.$ Given
two integers $p,q,$ where $p\leq q,$ we denote by $[p,q]$ the set
$\\{p,\dots,q\\}.$ For an integer $p\geq 1,$ we set $[p]=[1,p]$ and
$\mathbb{N}_{\geq p}=\mathbb{N}\setminus[0,p-1].$ For a set $S,$ we denote by
$2^{S}$ the set of all subsets of $S$ and by $\binom{S}{2}$ the set of all
subsets of $S$ of size $2.$ If $\mathcal{S}$ is a collection of objects where
the operation $\cup$ is defined, then we denote
${\boldsymbol{\bigcup}}S=\bigcup_{X\in\mathcal{S}}X.$ Also, given a function
$f\colon A\to B$ we always consider its extension $f:2^{A}\to B$ such that for
every $X\subseteq A,$ $f(X)=\\{f(a)\mid a\in X\\}.$

#### Basic concepts on graphs.

A graph $G$ is a pair $(V,E)$ where $V$ is a finite set and
$E\subseteq\binom{V}{2},$ i.e., all graphs in this paper are undirected,
finite, and without loops or multiple edges. When we denote an edge
$\\{x,y\\},$ we use instead the simpler notation $xy$ (or $yx$). We write
$\mathcal{G}_{{\text{\rm{all}}}}$ for the set of all graphs. We also define
$V(G)=V$ and $E(G)=E.$

We say that a pair $(A,B)\in 2^{V(G)}\times 2^{V(G)}$ is a _separation_ of $G$
if $A\cup B=V(G)$ and there is no edge in $G$ between $A\setminus B$ and
$B\setminus A.$ We call $|A\cap B|$ the _order_ of $(A,B).$

If $H$ is a subgraph of $G,$ that is $V(H)\subseteq V(G)$ and $E(H)\subseteq
E(G),$ we denote this by $H\subseteq G.$ Given two graphs $G_{1}$ and $G_{2},$
we denote $G_{1}\cup G_{2}=(V(G_{1})\cup V(G_{2}),E(G_{1})\cup E(G_{2})).$ We
also use $G_{1}+G_{2}$ to denote the disjoint union of $G_{1}$ and $G_{2}.$
Also, given a $t\in\mathbb{N},$ we denote by $t\cdot G$ the disjoint union of
$t$ copies of $G.$

Given a vertex $v\in V(G),$ we denote by $N_{G}(v)$ the set of vertices of $G$
that are adjacent to $v$ in $G.$ Also, given a set $S\subseteq V(G),$ we set
$N_{G}(S)=\bigcup_{v\in S}N_{G}(v)\setminus S.$

For $S\subseteq V(G),$ we set $G[S]=(S,E\cap\binom{S}{2})$ and use $G-S$ to
denote $G[V(G)\setminus S].$ We say that $G[S]$ is an _induced (by $S$)
subgraph_ of $G.$

Given an edge $e=uv\in E(G),$ we define the _subdivision_ of $e$ to be the
operation of deleting $e,$ adding a new vertex $w,$ and making it adjacent to
$u$ and $v.$ Given two graphs $H$ and $G,$ we say that $H$ is _a subdivision_
of $G$ if $H$ can be obtained from $G$ by subdividing edges.

The _contraction_ of an edge $e=uv\in E(G)$ results in a graph $G^{\prime}$
obtained from $G\setminus\\{u,v\\}$ by adding a new vertex $w$ adjacent to all
vertices in the set $(N_{G}(u)\cup N_{G}(v))\setminus\\{u,v\\}.$ A graph $H$
is a _minor_ of a graph $G$ if $H$ can be obtained from a subgraph of $G$
after a series of edge contractions. We denote this relation by $\leq.$ Given
a set $\mathcal{H}$ of graphs, we use $\mathcal{H}\leq G$ in order to denote
that at least one of the graphs in $\mathcal{H}$ is a minor of $G.$ We refer
the reader to [13] for any undefined terminology on graphs.

###  2.2 Surfaces, decompositions, and renditions

In this subsection, we present all definitions we require that are relevant to
drawing and embedding graphs in surfaces as well as more involved definitions
such as surface decompositions, societies, and more.

#### Surfaces.

Given a pair $(\mathsf{h},\mathsf{c})\in\mathbb{N}\times[0,2]$ we define
$\Sigma^{(\mathsf{h},\mathsf{c})}$ to be the two-dimensional surface without
boundary created from the sphere by adding $\mathsf{h}$ handles and
$\mathsf{c}$ crosscaps (for a more detailed definition see [52]). If
$\mathsf{c}=0,$ the surface $\Sigma^{(\mathsf{h},\mathsf{c})}$ is an
_orientable_ surface, otherwise it is a _non-orientable_ one. By Dyck’s
theorem [17, 23], two crosscaps are equivalent to a handle in the presence of
a (third) crosscap. This implies that the notation
$\Sigma^{(\mathsf{h},\mathsf{c})}$ is sufficient to denote all two-dimensional
surfaces without boundary.

#### Societies.

Given a graph $G$ and a set $X=\\{x_{1},\ldots,x_{n}\\}\subseteq V(G),$ we
consider two types of orderings of $X.$

  * •

a _rotation ordering_ $\Omega=(x_{1},\ldots,x_{n})$ where we assume that
$(x_{1},\ldots,x_{n})=(x_{1+i},\ldots,x_{n+i}),$ for every $i\in[0,n-1].$ Note
that $n+i$ is interpreted as $(n-1\mod n)+i+1.$

  * •

a _linear ordering_ $\Lambda=\langle x_{1},\ldots,x_{n}\rangle.$ Given a
linear ordering $\Lambda=\langle x_{1},\ldots,x_{n}\rangle$ we define its _$i$
-position shift_ as the linear ordering $\langle
x_{1+i},\ldots,x_{n+i}\rangle.$ Note that, as before, $n+i$ is interpreted as
$(n-1\mod n)+i+1.$

Given a rotation (resp. linear) ordering $\Omega=(x_{1},\ldots,x_{n})$ (resp.
$\Lambda=\langle x_{1},\ldots,x_{n}\rangle$) we define its reverse as
$\mathsf{rev}(\Omega)\coloneqq(x_{n},\ldots,x_{1})$ (resp.
$\Lambda\coloneqq\langle x_{n},\ldots,x_{1}\rangle$). Given a linear ordering
$\Lambda,$ we define $\mathsf{next}_{\Lambda}(x_{i})=x_{i+1},$ for every
$i\in[n-1]$ and $\mathsf{next}_{\Lambda}(x_{n})\coloneqq x_{1}.$ We also
define
$\mathsf{previous}_{\Lambda}(x_{i})\coloneqq\mathsf{next}_{\mathsf{rev}(\Lambda)}(x_{i}).$
When $\Lambda$ is clear from the context we simply write
$\mathsf{next}(x_{i})$ and $\mathsf{previous}(x_{i}).$ Moreover, given two
distinct linear orderings $\Lambda=\langle x_{1},\ldots,x_{n}\rangle$ and
$\Lambda^{\prime}=\langle y_{1},\ldots,y_{m}\rangle,$ we define their
_concatenation_ as the linear ordering $\Lambda\oplus\Lambda^{\prime}=\langle
x_{1},\ldots,x_{n},y_{1},\ldots,y_{m}\rangle.$

We define the _shifts_ of a linear ordering $\Lambda$ as the set containing
every $i$-position shift of $\Lambda,$ for $i\in[n].$ Observe that, given a
rotation ordering $\Omega=(x_{1},\ldots,x_{n})$ we can extract $n$ different
linear orderings depending on the choice of the first vertex. Let $\Lambda$ be
any of these linear orderings. Then all these linear orderings, which are the
shifts of $\Lambda,$ correspond to a single rotation ordering that we call the
_rotation ordering of $\Lambda$_.

A _linear_ (resp. _rotation_) _society_ is a pair $\langle G,\Lambda\rangle$
(resp. $(G,\Omega)$) where $G$ is a graph and $\Lambda$ (resp. $\Omega$) is a
linear (resp. rotation) ordering of a subset of the vertices of $G.$ The
_rotation society_ of a linear society $\langle G,\Lambda\rangle$ is the
rotation society $(G,\Omega),$ where $\Omega$ is the rotation ordering of
$\Lambda.$ We denote by $V(\Lambda)$ (resp. $V(\Omega)$) the set of vertices
on that correspond to elements of $\Lambda$ (resp. $\Omega$). We also use
$|\Lambda|\coloneqq|V(\Lambda)|$ (resp. $|\Omega|\coloneqq|V(\Omega)|$). From
this point forward we always use the notation $\langle G,\Lambda\rangle$
(resp. $(G,\Omega)$) to denote linear (resp. rotation) societies. Whenever we
use the term _society_ we will be referring to a linear society. On the other
hand, we will explicitly mention when we are dealing with a rotation society.

A _subdivision_ of a linear (resp. rotation) society $\langle
G,\Lambda\rangle$ (resp. $(G,\Omega)$) is every linear (resp. rotation)
society $\langle M,\Lambda\rangle$ (resp. $(M,\Omega)$) where $M$ is a
subdivision of $G.$

Two societies $\langle G,\Lambda\rangle$ and $\langle
G^{\prime},\Lambda^{\prime}\rangle$ are _isomorphic_ if there is an
isomorphism $\psi\coloneqq V(G)\to V(G^{\prime})$ from $G$ to $G^{\prime}$
such that $\psi(\Lambda)=\Lambda^{\prime},$ i.e., if $\Lambda=\langle
x_{1},\ldots,x_{r}\rangle,$ it holds that
$\Lambda^{\prime}=\langle\psi(x_{1}),\ldots,\psi(x_{r})\rangle.$