theoremdummy theorem propositiondummy proposition corollarydummy corollary
lemmadummy lemma definitiondummy definition sublemmadummy sublemma claimdummy
claim remarkdummy remark factdummy fact conjecturedummy conjecture
questiondummy question observationdummy observation problemdummy problem
notedummy note

# Killing a Vortex

Dimitrios M. Thilikos , LIRMM, Université de Montpellier, CNRS, Montpellier,
France. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>by the ANR projects DEMOGRAPH
(ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), and the French-German
Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027). Sebastian
Wiederrecht11footnotemark: 1 , Supported by the ANR project ESIGMA
(ANR-17-CE23-0010).

###### Abstract

The Structural Theorem of the Graph Minors series of Robertson and Seymour
asserts that, for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t\in\mathbb{N},$
there exists some constant
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{t}$
such that every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{t}$-minor-
free graph admits a tree decomposition whose torsos can be transformed, by the
removal of at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{t}$
vertices, to graphs that can be seen as the union of some graph that is
embeddable to some surface of Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{t}$
and “at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{t}$
vortices of depth
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{t}$”.
Our main combinatorial result is a “vortex-free” refinement of the above
structural theorem as follows: we identify a (parameterized) graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{t}$,
called _shallow vortex grid_ , and we prove that if in the above structural
theorem we replace
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{t}$
by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{t},$
then the resulting decomposition becomes “vortex-free”. Up to now, the most
general classes of graphs admitting such a result were either bounded Euler
genus graphs or the so called single-crossing minor-free graphs. Our result is
tight in the sense that, whenever we minor-exclude a graph that is not a minor
of some
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{t},$
the appearance of vortices is unavoidable. Using the above decomposition
theorem, we design an algorithm that, given an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{t}$-minor-
free graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$,
computes the generating function of all perfect matchings of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
in polynomial time. This algorithm yields, on
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{t}$-minor-
free graphs, polynomial algorithms for computational problems such as the
dimer problem, the exact matching problem, and the computation of the
permanent. Our results, combined with known complexity results, imply a
complete characterization of minor-closed graphs classes where the number of
perfect matchings is polynomially computable: They are exactly those graph
classes that do not contain every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{t}$
as a minor. This provides a sharp complexity dichotomy for the problem of
counting perfect matchings in minor-closed classes.

Keywords: Perfect Matchings, Permanent, Pfaffian Orientations, Graph Minors,
Counting Algorithms, Graph Parameters.

###### Contents

  1. 1 Introduction
    1. 1.1 Some history
    2. 1.2 Counting matchings in minor-closed graph classes
    3. 1.3 Our main result
    4. 1.4 The vga-hierarchy
    5. 1.5 Our approach
  2. 2 Definitions and preliminary results
    1. 2.1 The Graph Minors Structure Theorem
    2. 2.2 A refined version of
  3. 3 Combinatorial results
    1. 3.1 Advancing through a nest
    2. 3.2 The death of a vortex
    3. 3.3 Excluding a shallow vortex minor
    4. 3.4 Proof of the combinatorial lower bound
  4. 4 Algorithmic consequences
    1. 4.1 Dynamic programming for the generating function
    2. 4.2 The complexity lower bound
  5. 5 Conclusion

##  1 Introduction

We consider the problem
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}},$ asking for the number of perfect matchings, on minor-closed graph
classes. The first polynomial algorithm for this problem was given for the
class of planar graphs by Kasteleyn in 1961 [24], motivated by the dimer
problem in Theoretical Physics [25, 24, 46, 23] (see also the results by
Temperley and Fisher [46]). For this algorithm, Kasteleyn introduced the
celebrated FKT-method and the concept of Pfaffian orientations.

Using these concepts as a departure point, the tractability horizon has been
extended to several minor-closed graph classes, further than planar graphs,
and it was an open problem whether this horizon contained all minor-closed
graph classes. A negative answer to this question was given by Curticapean and
Xia who proved that the classic result of Valiant on the
#$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{P}$-completeness
of #Perfect Matching holds even when restricted to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{8}$-minor
free graphs.

In this paper, we completely resolve the complexity of #Perfect Matching on
minor-closed graph classes by providing a sharp characterization of the
classes for which the problem is tractable.

###  1.1 Some history

Given a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n\\!\times\\!n$
matrix
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\\!=\\!(a_{i,j})$
the _permanent_ and the _determinant_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
are defined as

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\displaystyle\mathsf{perm}(A)=\sum_{\in
S_{n}}\prod_{i=1}^{n}a_{i,(i)}$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\displaystyle\mathsf{det}(A)=\sum_{\in
S_{n}}\Big{(}\mathsf{sgn}()\cdot\prod_{i=1}^{n}a_{i,(i)}\Big{)}$

respectively, where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S_{n}$
is the set of all possible permutations of the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}[n]=\\{1,\ldots,n\\}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{sgn}()$
is the sign of the permutation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\in
S_{n}.$ The permanent is closely related to the #Perfect Matching problem as
the number of perfect matchings of a bipartite graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
is equal to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{perm}(A^{\prime}_{B})$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A^{\prime}_{B}$
is the biadjacency matrix111The _biadjacency matrix_ of a bipartite graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B=(X\dot{\cup}Y,E)$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X=\\{x_{1},\ldots,x_{n}\\}$,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y=\\{y_{1},\ldots,y_{n}\\}$,
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E\subseteq
X\times Y,$ is the binary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n\times
n$ matrix
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A=(a_{i,j})$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}a_{i,j}=1$
iff
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\{x_{i},y_{i}\\}\in
E(B)$. of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B.$

In 1913 György Pólya [33] asked when it is possible to change the sings of the
entries of a binary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n\times
n$ matrix
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A=(a_{i,j})$
and obtain a new matrix
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A^{\prime}$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{perm}(A)=\mathsf{det}(A^{\prime}).$
Notice that, in such cases, the computation of the permanent is reduced to the
computation of the determinant that, in turn, can be computed in polynomial
time (see [1] for an exposition on the permanent versus determinant problem).

Kasteleyn in 1961, in an attempt to solve the dimer problem (originated from
Statistical Physics [25, 24, 46]) introduced the concept of a Pfaffian graph:
a matchable1 graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is _Pfaffian_ if it admits an orientation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\overrightarrow{G}$
such that every conformal222A graph is _matchable_ if it contains at least one
perfect matching. A cycle
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C$
of a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is _conformal_ if it is even and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-C$
is matchable. cycle
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
has an odd number of directed edges in agreement to the orientation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\overrightarrow{G}$,
when traversed clockwise. Such an orientation of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is called _Pfaffian_.

A Pfaffian orientation of a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
implies a scheme to change the signs of the adjacency matrix
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A(G)$
such that the determinant of the resulting matrix still yields the number of
perfect matchings of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$.
As a special case of Kasteleyn’s approach, Pólya’s question can be answered
affirmatively for a matrix
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
if and only if the bipartite graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
that has
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
as its biadjacency matrix is Pfaffian (see [30]). In particular, the requested
change of signs follows directly from a Pfaffian orientation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\overrightarrow{B}$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B.$
Moreover, Kasteleyn proved that planar (matchable) graphs are Pfaffian and
gave a polynomial algorithm for computing a Pfaffian orientation of a planar
graph. This algorithm is widely known as the FKT-method (making also reference
also to the authors of [46]) and implied that #Perfect Matching is
polynomially solvable in planar graphs.

Little in 1972 treated Pólya’s problem by giving a complete combinatorial
condition of when a bipartite graph is Pfaffian. Later, McCuaig, Robertson,
Seymour, and Thomas gave a structural characterization of Little’s condition
that permitted the design of a polynomial algorithm checking whether a
bipartite graph is Pfaffian [34, 31]. This immediately implied a polynomial
algorithm for #Perfect Matching on Pfaffian bipartite graphs. On the negative
side (motivated by the permanent vs determinant problem) Valiant introduced
the counting complexity class
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\#P$
and proved that #Perfect Matching is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\#P$-complete
[49].

See Figure 1 for a timeline of the known results on the #Perfect Matching
problem.

###  1.2 Counting matchings in minor-closed graph classes

In what concerns general (i.e., non-bipartite) graphs, Kasteleyn claimed in
[24, 25] that his algorithm for #Perfect Matching on planar graphs can be
extended to graphs of bounded Euler genus. This was proved by Galluccio and
Loebl [15] for orientable surfaces and by Tesler [47] for non-orientable
surfaces. The later results were based on a reduction of the problem to the
computation of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2^{g}$
orientations333The original result suggested by Kasteleyn used
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4^{g}$
many orientations. This was since Kasteleyn worked with orientable genus,
hence the number
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h$
of handles, while the result we present here refers to the Euler genus which
is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2h+c$,
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
is the number of crosscaps involved., where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}g$
is the Euler genus of the input graph. A unified algorithm for counting the
number of perfect matchings on graphs of bounded Euler genus without the use
of orientations was given by Curticapean and Xia in [8].

Notice that graphs of bounded Euler genus are minor-closed. The emerging
question is whether #Perfect Matching is polynomially solvable for all minor-
closed graph classes. For this, given a finite set of graphs
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F},$
we introduce the notation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\mathcal{F})$ for the #Perfect Matching problem restricted to
graphs excluding all graphs in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F}$
as minors. We stress that every minor-closed graph class can be characterized
by the minor-exclusion of some _finite_
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F},$
because of Robertson and Seymour’s theorem [41]. Observe also that #Perfect
Matching is the same as
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\emptyset),$ while #Perfect Matching on planar graphs is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\\{K_{5},K_{3,3}\\}).$ Using this notation, advances on the
#Perfect Matching problem can be described as follows: Valiant proved in [51]
that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\\{K_{3,3}\\})$ is polynomially solvable, Straub, Thierauf, and
Wagner proved in [45] that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\\{K_{5}\\})$ is polynomially solvable and later Curticapean in [6]
and Eppstein and Vazirani in [14] proved that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\mathcal{F})$ is polynomially solvable for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F}$
containing a minor of a graph that admits a drawing in the plane with at most
one crossing.

The results in blue concern (weighted) bipartite graphs, corresponding to
general matrices. All other of the results concern algorithmic (green) and
hardness (red) results on general (weighted) graphs and their adjacency
matrices. Pólyá’s Permanenet Problem [33]Temperley & Fisher
[46]Kasteleyn [24]PlanarLittle [28]Valiant
[49]$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\#$P-hardnessStraub,
ThieraufWagner
[45]$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{3,3}$-minor
free$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{8}$-minor
freeRobertson, Seymour,Thomas (& McCuaig) [34] ([31])Galluccio & Loebl
[15]bounded orientable genussingle-crossing minor freeTesler [47]bounded Euler
genusEppstein & Vazirani [14]Curticapean [6]CurticapeanXia
[9]Valiant [51]

Figure 1: Timeline of the results on the complexity of the #Perfect Matching
problem.

Recently, Curticapean and Xia in [9] strengthened Valiant’s original hardness
result by proving that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\\{K_{8}\\})$ is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\#P$-complete.
This means that the tractability horizon of #Perfect Matching does not include
all minor-closed graph classes and it lies somewhere “above” single-crossing
minor free graphs and “below”
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{8}$-minor
free graphs. In this paper we completely determine this tractability horizon.

###  1.3 Our main result

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathbf{w}}:E(G)\rightarrow\mathbb{Z}$
be a function assigning weights to the edges of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\max\\{|{\mathbf{w}}(e)|\mid
e\in E(G)\\}$ is bounded by some polynomial function of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|G|$
(that is the number of vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$).
We refer to such a pair
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,{\mathbf{w}})$
as an _edge-weighted graph_ (or simply _weighted graph_). We use
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{M}(G)$
for the set of all matchings of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
We define the _generating function of perfect matchings_ of the weighted graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,{\mathbf{w}})$
as

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{PerfMatch}(G,{\mathbf{w}}):=\sum_{M\in\mathcal{M}(G)}\prod_{e\in
M}x^{{\mathbf{w}}(e)}.$

Notice that if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathbf{1}}$
is the weighing function assigning unit weights on the edges of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{perm}(A_{G})=\mathsf{PerfMatch}(G,{\mathbf{1}})=c\cdot
x^{|G|/2}$ where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c=|\mathcal{M}(G)|$
is the number of perfect matchings of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Therefore, any algorithm computing
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{PerfMatch}$
in polynomial time can also serve as a polynomial algorithm for the #Perfect
Matching problem. Moreover, the computation of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{PerfMatch}(G,{\mathbf{w}})$
also permits to solve the Exact Perfect Matching problem: given an edge-
weighted graph and some non-negative integer
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$,
decide whether there is a perfect matching of total weight exactly
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$.
Exact Perfect Matching was defined by Papadimitriou and Yannakakis in [32],
has been extensively studied [19, 52], with applications on DNA sequencing [2]
and storage load balancing in blockchain networks [29].

Figure 2: The shallow vortex grid
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{6}.$

######  Definition  (Shallow vortex grids).

The _shallow vortex grid_ of order
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
is the graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{k}$
such that there exists a family of cycles
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{C}=\left\\{C_{1},C_{2},\dots,C_{t}\right\\}$
with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(C_{i})=\left\\{c_{1}^{i},c_{2}^{i},\dots,c_{2k}^{i}\right\\},$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E(C_{i})=\left\\{c_{1}^{i}c_{2k}^{i}\right\\}\cup\left\\{c_{j}^{i}c_{j+1}^{i}\mid
j\in[2k-1]\right\\},$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(H_{k})=\bigcup_{i\in[k]}V(C_{i}),$
and

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\displaystyle
E(H_{k})$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\displaystyle=$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\displaystyle\left\\{c_{i}^{1}c_{i+2}^{1}\mid
i\in[2k-2]\right\\}\cup\left\\{c_{2t-1}^{1}c_{1}^{1},c_{2k}^{1}c_{2}^{1}\right\\}$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\displaystyle\cup\left\\{c_{i}^{j}c_{i}^{j+1}\mid
i\in[2k],j\in[k-1]\right\\}\cup(\bigcup_{i\in[2k]}E(C_{i})).$

To get a fairly good idea of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{k},$
see Figure 2 for a drawing of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{6}.$
We also define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{H}}$
as the graph class consisting of all minors of shallow vortex grids. Our main
result is a complexity dichotomy for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\mathcal{F}),$ based on the class
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{H}}.$

######  Theorem .

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F}$
be some finite set of graphs. Then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#\emph{Perfect
Matching}}}(\mathcal{F})$ can be solved in polynomial time if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F}\cap{\mathcal{H}}\neq\emptyset$;
otherwise it is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\#\mathsf{P}$-complete.

As an example of an application of Subsection 1.3,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{7}$
is a minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{18}$
(see Subsection 3.4), therefore
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{7}\in\mathcal{H}.$
This implies that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}(\\{K_{r}\\})$ is polynomially solvable for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r\leq
7$ (which already answers the open question in [9]) and, as proved in [9], is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\\#P$-complete
for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r\geq
8.$ For the general minor-exclusion of a finite set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F},$
containing graphs of size at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h,$
one needs to check whether some graph in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{F}$
is one of the graphs in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{H}$
with at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h$
vertices.

In order to give some intuition why the minors of graphs as the one in Figure
2 provide the correct dichotomy criterion, we need a brief introduction to the
Graph Minors Structure Theorem, proven by Robertson and Seymour in [40] (in
this paper we use the notation used in the simpler proof of this theorem that
appeared recently in [21] – see also [26]).

###  1.4 The vga-hierarchy

A _graph parameter_ is a function mapping graphs to non-negative integers. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}^{\prime}$
be two graph parameters. We write
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}\preceq{\mathsf{p}}^{\prime}$
if there is a function
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}f:\mathbb{N}\to\mathbb{N}$
such that, for every graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
it holds that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}(G)\leq
f({\mathsf{p}}^{\prime}(G)).$ We also say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}^{\prime}$
are _parametrically equivalent_ if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}\preceq{\mathsf{p}}^{\prime}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}^{\prime}\preceq{\mathsf{p}}.$

######  Definition  (Treewidth).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph. A _tree decomposition_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a tuple
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{T}=(T,\beta)$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
is a tree and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\beta\colon
V(T)\rightarrow 2^{V(G)}$ is a function, called the _bags_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{T},$
such that

  1. i)

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\bigcup_{t\in
V(T)}\beta(t)=V(G),$

  2. ii)

for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e\in
E(G)$ there exists
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t\in
V(t)$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e\subseteq\beta(t),$
and

  3. iii)

for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v\in
V(G)$ the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\left\\{t\in
V(T)\mid v\in\beta(t)\right\\}$ induces a subtree of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T.$

The _width_ of a tree decomposition is defined as
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\max_{t\in
V(T)}|\beta(t)|-1$ and the _treewidth_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
denoted by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\operatorname{tw}(G),$
is the minimum width over all tree decompositions for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
The _adhesion_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(T,\beta)$
is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\max_{dt\in
E(T)}|\beta(d)\cap\beta(t)|.$ For a vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t\in
V(T),$ the _torso of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
at
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$_
is the graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}$
obtained from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G[\beta(t)]$
by adding an edge to every non-adjacent pair of vertices
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x,y\in\beta(t)$
for which there eixsts
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}d\in
V(T)$ adjacent to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}T$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\left\\{x,y\right\\}\in\beta(d).$

######  Definition .

Given a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
we define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{p}_{\mbox{\scriptsize{v\\!\\!\\!
g\\!\\!\\! a}}}(G)$ as the minimum
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
has a tree decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{D}}=(T,\beta)$
where, for every torso
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{D}},$
if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|G_{t}|>k,$
then the following holds: There is a set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\subseteq
V(G_{t}),$ called _apex set_ , a surface , and a -decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}-A$
such that:

  * (v)

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
has at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
vortices, each of depth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k,$

  * (g)

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
has Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k,$
and

  * (a)

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|A|\leq
k.$

We postpone to Subsection 2.1 the formal definition of a -decomposition of a
graph as well the definition of a vortex and its depth (see Subsection 2.1 and
Subsection 2.1). Intuitively,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}$
has a -decomposition with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
vortices if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}=G^{(0)}\cup
G^{(1)}\cup\cdots\cup G^{(k)}$ where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G^{(0)}$
is a graph embedded in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
and each vortex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G^{(i)}$
is a graph “attached around” the vertices of some face of the embedding of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G^{(0)}.$

Subsection 1.4 has several variants
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mathsf{w}}$
depending on whether in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{w}}={\texttt{vga}},$
we replace “v”, “g”, or “a” by “-” implying the replacement in the
corresponding item of
“$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$”
by
“$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}0$”.
Also we define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{false}}}$
if, in Subsection 1.4, we replace whatever follows the statement “the
following holds:” by some false statement. This generates nine variants of
parameters whose relation with respect to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\preceq$
is depicted in Figure 3. We refer to this hierarchy of parameters as the vga
_-hierarchy_. We will later fix our attention to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}},$ where vortices disappear and therefore
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}-A$
is just required to be embeddable to a surface of Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k.$

In Figure 3 we depict, relatively to the vga-hierarchy, two more parameters
for which, when bounded, #Perfect Matching can be solved in polynomial time.
The first is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{apex}}$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{apex}}(G)$
is the minimum number of vertices whose removal from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
yields a planar graph and the second is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{genus}}$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{genus}}(G)$
us the minimum Euler genus of a surface where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
can be embedded.

Figure 3: The vga-hierarchy of parameters and the position of the parameters
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{apex}}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{genus}}$
in it. If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}^{\prime}$
are parameters in the above diagram then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}\preceq{\mathsf{p}}^{\prime}$
iff there is a path between
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}^{\prime}$
that is “above”
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}^{\prime}.$
The two green/red-colored areas indicate the complexity of #Perfect Matching
when restricted to graphs where each of the depicted parameters is bounded.
The lower dark green area indicates the current state of the art on polynomial
algorithms for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mbox{{\\#Perfect
Matching}}.$

The _Hadwiger number_ of a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is the maximum size of a clique minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
denoted by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{hw}}(G).$
The Graph Minors Structure Theorem [21, 40] (in short GMST) can be stated as
follows.

######  Proposition .

The graph parameters
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{hw}}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{p}_{\texttt{\emph{vga}}}$
are parametrically equivalent.

(For an alternative (non-parametric) statement of GMST, see Subsection 2.1.)
Notice that all parameters of the vga-hierarchy can be seen as generalizations
of treewidth, starting from the lowest level parameter
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{false}}},$
that is parametrically equivalent to treewidth, to the highest level parameter
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{v\\!\\!\\!
g\\!\\!\\! a}}},$ that is parametrically equivalent to the Hadwiger number.

In [38], Robertson and Seymour proved that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
-\\!\\!\\! -}}}(G)$ is parametrically equivalent to the maximum size of an
internally
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4$-connected444A
graph is _internally
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4$-connected_
if it is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}3$-connected
and for every separation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A,B)$
either
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|A\setminus
B|\leq 1$ or
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|B\setminus
A|\leq 1$. single-crossing555A _single-crossing graph_ is one that can be
drawn in the plane with only one crossing. minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Using this, the results of Eppstein and Vazirani in [14] and Curticapean in
[6] imply an algorithm that, given a weighted graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,{\mathbf{w}}),$
outputs
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{GenPM}}(G,{\mathbf{w}})$
in time666We use the notation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h(k,n)=\mathcal{O}_{k}(g(n))$
to denote that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h(k,n)=\mathcal{O}(f(k)\cdot
g(n)),$ for some function
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}f.$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{O}_{k}(|G|^{\mathcal{O}(1)})$,
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
-\\!\\!\\! -}}}(G).$ This positions the results of [14, 6] to the second lower
level of the vga-hierarchy (just above
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{false}}}$).
Apart from this result, the results in [15, 47, 16] imply that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{PerfMatch}(G,{\mathbf{w}})$
can be computed in time
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{O}_{k}(|G|^{\mathcal{O}(1)})$
when
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k=\mathsf{genus}(G).$
Also, it is easy to see that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{PerfMatch}(G,{\mathbf{w}})$
can be computed in time
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|G|^{\mathcal{O}(k)}$
when
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{apex}}(G)$
[7, 8]. These three results are the best, so far, algorithmic results about
when #Perfect Matching can be solved in polynomial time (corresponding to the
dark green rectangle of the diagram in Figure 3).

###  1.5 Our approach

We define a new parameter
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}$,
based on shallow vortex grids
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{k}$,
as follows

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}(G)=\max\\{k\mid
H_{k}\text{ is a minor of }G\\}.$

Our main combinatorial result is a vortex-free refinement of the GMST
(Subsection 1.4). In particular
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}$
can be seen as the vortex-free analogue of the Hadwinder number.

######  Theorem .

The graph parameters
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{p}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{p}_{\texttt{\emph{-ga}}}$
are parametrically equivalent.

Subsection 1.5 is a min-max theorem indicating that shallow vortex grids can
be seen as “universal obstructions” for the parameter
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}.$ Our proof implies that there is a function
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}f:\mathbb{N}\to\mathbb{N}$
and an algorithm that, given a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
and an integer
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k,$
either finds the shallow vortex grid
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H_{k}$
as a minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
or outputs a tree decomposition of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
certifying that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}(G)\leq f(k).$ Moreover, this algorithm runs in time
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{O}_{k}(|G|^{3})$
(see Subsection 3.3).

The proof of Subsection 1.5 is the main technical part of this paper. The fact
that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{p}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}\preceq{\mathsf{p}}$ follows from the following stronger
result.

######  Theorem .

There exist functions
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\alpha,\gamma\colon\mathbb{N}\rightarrow\mathbb{N}$
such that every graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
excluding some graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H\in\mathcal{H}$
as a minor has a tree decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(T,\beta)$
of adhesion at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4\alpha(|V(H)|)$
such that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t\in
V(T),$ if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}$
is the torso of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
at
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t,$
then there exists a set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\subseteq
V(G_{t})$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|A|\leq\alpha(|V(H)|)$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{t}-A$
has Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\gamma(|V(H)|).$

The proof of Subsection 1.5 is presented in the first three subsections of
Section 3. The proof of Subsection 1.5 is completed in Subsection 3.4, where
we show that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{p}\preceq{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}$ (Subsection 3.4).

Based on Subsection 1.5, we next prove our main algorithmic result.

######  Theorem .

There are an algorithm and a function
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}f:\mathbb{N}\to\mathbb{N}$
that, given a weighted graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,{\mathbf{w}}),$
where the maximum absolute value of w is bounded by some polynomial in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|G|,$
outputs
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{PerfMatch}(G,{\mathbf{w}})$
in time
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{O}(|G|^{f(k)})$,
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{\emph{-\\!\\!\\!
g\\!\\!\\! a}}}}(G).$ Our algorithm assumes that arithmetic operations are
performed in constant time.

The algorithm of Subsection 1.5 is presented in Subsection 4.1. It performs
dynamic programming on the tree decomposition provided by Subsection 1.5 and
combines all the algebraic tools that have been employed so far around
Pfaffian orientations for the #Perfect Matching problem [24, 25, 46, 15, 16,
47].

Notice that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{F}}\cap{\mathcal{H}}\not=\emptyset$
if and only if there is a constant
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{\mathcal{F}}$
such that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{F}}$-minor
free graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
it holds that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}(G)\leq
c_{\mathcal{F}}.$ This fact, combined with Subsection 1.5 and Subsection 1.5
implies the positive part of Subsection 1.3.

On the negative side, in Subsection 4.2, we prove the following using as a
departing point the complexity lower bound of Curticapean and Xia in [10].

######  Theorem .

For every graph class
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{G}}$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{H}}\subseteq{\mathcal{G}},$
#Perfect Matching is #_P_ -complete when its inputs are restricted to the
graphs in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{G}}.$

Notice that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{F}}\cap{\mathcal{H}}=\emptyset$
if and only if all graphs in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{H}}$
are
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathcal{F}}$-minor
free. This, combined with Subsection 1.5, yields the negative part of
Subsection 1.3.

One may ask whether the algorithm of Subsection 1.5 can be improved to a fixed
parameter one, that is an algorithm running in time
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{O}_{k}(|G|^{\mathcal{O}(1)})$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}(G)$ (we already mentioned that this is the case when
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
-\\!\\!\\! -}}}(G)$ [14, 6] or when
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k=\mathsf{genus}(G)$
[15, 47, 16]). Unfortunately, this is not something to expect even for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
-\\!\\!\\! a}}}(G)$ (which is lower than
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}$ in the vga-hierarchy). Indeed, it was proved in [8] that
#Perfect Matching is #W[1]-hard when parameterized by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{apex}}(G).$
As
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}\preceq{\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\! -\\!\\!\\!
a}}}\preceq{\mathsf{apex}},$ this hardness result holds also when the
parameter is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
-\\!\\!\\! a}}}(G)$ or, evenmore,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k={\mathsf{p}}_{\mbox{\scriptsize{-\\!\\!\\!
g\\!\\!\\! a}}}(G).$ This indicates that, under standard computational
complexity assumptions, the algorithm of Subsection 1.5 is asymptotically
optimal from the parameterized complexity point of view.

##  2 Definitions and preliminary results

We denote by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbb{Z}$
the set of integers and by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbb{R}$
the set of reals. Given two integers
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}a,b\in\mathbb{Z}$
we denote the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\left\\{z\in\mathbb{Z}\mid
a\leq z\leq b\right\\}$ by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}[a,b].$
In case
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}a>b$
the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}[a,b]$
is empty. For an integer
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p\geq
1,$ we set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}[p]=[p]$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathbb{N}_{\geq
p}=\mathbb{N}\setminus[0,p-1].$ Whenever we need a closed interval over the
reals we use
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}[x,y]_{\mathbb{R}}$
to avoid ambiguity. Please note that this only happens on rare occasions.

All graphs considered in this paper are undirected, finite, and without loops
or multiple edges. We use standard graph-theoretic notation and we refer the
reader to [11] for any undefined terminology.

###  2.1 The Graph Minors Structure Theorem

We rely heavily on the more refined versions of the GMST from [21] and [12]
instead of the original result proven by Robertson and Seymour in the Graph
Minors series. As the involved definitions and concepts are highly technical
we dedicate this section almost entirely just to their statements and some
explanations. In the proof of our main theorem we actually need a stronger
version of GMST which has, implicitly, already been proven in [21] and which
resembles the main theorem of [12]. However, because of the way our proof
works and since we are also after algorithmic applications, it is more
convenient to derive a synthesis of the results in [12] and those in [21]. The
resulting statement makes the structure of the vortices within the original
structure theorem more accessible and this might be of use to applications
other than our own as well.

#### The Two Paths Theorem.

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{1},s_{2},t_{1},t_{2}\in
V(G).$ The Two Disjoint Paths Problem (TDPP) with _terminals_
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{1},s_{2},t_{1},t_{2}$
is the question for the existence of two paths
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{2}$
such that for both
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i\in[2]$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{i}$
joins
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{i}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t_{i}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{1}$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{2}$
are vertex disjoint. The characterization for the yes-instances of the TDPP
known as the _Two Paths Theorem_ plays an integral role in structural graph
theory. The statement of the Two Paths Theorem we present here makes use of
the concept of the so called “societies” which play a focal role in [21] and
are used extensively in our proofs as well.

######  Definition  (Society).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
be a cyclic permutation of the elements of some set which we denote by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega).$
A _society_ is a pair
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega),$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a graph and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
is a cyclic permutation with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega)\subseteq
V(G).$ A _cross_ in a society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
is a pair
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(P_{1},P_{2})$
of disjoint paths777When we say two paths are _disjoint_ we mean that their
vertex sets are disjoint. in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{i}$
has endpoints
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{i},t_{i}\in
V(\Omega)$ and is otherwise disjoint from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega),$
and the vertices
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{1},s_{2},t_{1},t_{2}$
occur in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
in the order listed.

Hence
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,s_{1},s_{2},t_{1},t_{2})$
is a yes-instance of TDPP if and only if the society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega),$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega)=\left\\{s_{1},s_{2},t_{1},t_{2}\right\\}$
and the vertices occur in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
in the order listed, has a cross.

To fully present the Two Paths Theorem we need to introduce some topological
concepts as well.

By a _surface_ we mean a compact
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2$-dimensional
manifold with or without boundary. By the classification theorem of surfaces,
every surface is homeomorphic to the sphere with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h$
handles and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
cross-caps added, and the interior of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}d$
disjoint closed disks
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{1},\dots,\Delta_{d}$
removed, in which case the _Euler genus_ of the surface is defined to be
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2h+c.$
We call the union of the boundaries of the disks
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{i}$
the _boundary_ of the surface and each such boundary is a _boundary component_
of the surface.

######  Definition .

(Drawing on a surface) A _drawing_ (with crossings) _in a surface
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$_
is a triple
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma=(U,V,E)$
such that

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E$
are finite,

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V\subseteq
U\subseteq\Sigma,$

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V\cup\bigcup_{e\in
E}e=U$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V\cap(\bigcup_{e\in
E}e)=\emptyset,$

  * •

for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e\in
E,$ either
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e=h(0,1),$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h\colon[0,1]_{\mathbb{R}}\rightarrow
U$ is a homeomorphism onto its image with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h(0),h(1)\in
V,$ or
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e=h(\mathbb{S}^{2}-(1,0)),$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h\colon\mathbb{S}^{2}\rightarrow
U$ is a homeomorphism onto its image with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}h(0,1)\in
V,$ and

  * •

if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e,e^{\prime}\in
E$ are distinct, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|e\cap
e^{\prime}|$ is finite.

We call the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V,$
sometime referred to by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Gamma),$
the _vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$_
and the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E,$
referred to by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E(\Gamma),$
the _edges of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$_.
If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is graph and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma=(U,V,E)$
is a drawing with crossings in a surface
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E$
naturally correspond to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(G)$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E(G)$
respectively, we say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$
is a _drawing of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
(possibly with crossings)_. In the case where no two edges in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E()$
have a common point, we say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$
is a _drawing of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
without crossings_. In this last case, the connected components of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\setminus
U,$ are the _faces_ of .

######  Definition
($\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-Decomposition).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
be a surface. A
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
-decomposition_ of a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a pair
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta=(\Gamma,\mathcal{D}),$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$
is a drawing of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
with crossings, and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{D}$
is a collection of closed disks, each a subset of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
such that

  1. i)

the disks in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{D}$
have pairwise disjoint interiors,

  2. ii)

the boundary of each disk in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{D}$
intersects
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$
in vertices only,

  3. iii)

if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{1},\Delta_{2}\in\mathcal{D}$
are distinct, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{1}\cap\Delta_{2}\subseteq
V(\Gamma),$ and

  4. iv)

every edge of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$
belongs to the interior of one of the disks in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{D}.$

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N$
be the set of all vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma$
that do not belong to the interior of any of the disks in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{D}.$
We refer to the elements of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N$
as the _nodes_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta.$
If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta\in\mathcal{D},$
then we refer to the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta-N$
as a _cell_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta.$
We denote the set of nodes of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N(\delta)$
and the set of cells by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C(\delta).$
For a cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ the set of nodes that belong to the closure of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
is denoted by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\widetilde{c}.$
Notice that this means that the cells
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\widetilde{c}\neq\emptyset$
form the edges of a hypergraph with vertex set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N(\delta)$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\widetilde{c}$
is the set of vertices incident with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c.$
For a cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ we define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\sigma_{\delta}(c),$
or
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\sigma(c)$
if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
is clear from the context, to be the subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
consisting of all vertices and edges drawn in the closure of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c.$

We define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi_{\delta}\colon
N(\delta)\rightarrow V(G)$ to be the mapping that assigns to every node in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N(\delta)$
the corresponsing vertex of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$

Isomorphisms between two
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decompositions
are defined in the natural way.

######  Definition  (Vortex).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
be a surface and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta=(\Gamma,\mathcal{D})$
be a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
A cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ is called a _vortex_ if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|\widetilde{c}|\geq
4.$ Moreover, we call
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
_vortex-free_ if no cell in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C(\delta)$
is a vortex.

######  Definition  (Rendition).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
be a society, and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
be a surface with one boundary component
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B.$
A _rendition_ in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
such that the image under
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi_{\rho}$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N(\rho)\cap
B$ is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega),$
mapping one of the two cyclic orders of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
to the order of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega.$

These technical definitions allow us the state the Two Paths Theorem in the
general context of the Graph Minors Structure Theorem as follows.

######  Theorem  (Two Paths Theorem, [22, 42, 44, 48, 36]).

A society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
has no cross if and only if it has a vortex-free rendition in a disk.

#### The Flat Wall Theorem.

This section is dedicated to a weaker version of the structure theorem for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{t}$-minor-
free graphs known as the _Flat Wall Theorem_ [39, 26]. While the Flat Wall
Theorem plays an integral role in the proof of the Graph Minors Structure
Theorem, it is not that important for the proof of the main theorem. However,
it acts as the base of the construction of a rendition with a bounded number
of bounded depth vortices for any
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{t}$-minor-
free graph of large treewidth and as such it is needed for the statements of
the slightly altered versions of lemmas and theorems we extract from [21].

A _separation_ in a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a pair
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A,B)$
of vertex sets such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\cup
B=V(G)$ and there is no edge in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
with one endpoint in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\setminus
B$ and the other in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B\setminus
A.$ The _order_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A,B)$
is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|A\cap
B|.$

An
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(n\times
m)$ -grid_ is the graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{n,m}$
with vertex set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}[n]\times[m]$
and edge set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\left\\{\left\\{(i,j),(i,j+1)\right\\}\mid
i\in[n],j\in[m-1]\right\\}\cup\left\\{\left\\{(i,j),(i+1,j)\right\\}\mid
i\in[n-1],j\in[m]\right\\}.$ We call the paths of the form
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(i,1)(i,2)\dots(i,m)$
the _rows_ and the paths of the form
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(1,j)(2,j)\dots(n,j)$
the _columns_ of the grid. If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L$
is a row (column) of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{n,m}$
of the form
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(i,1)(i,2)\dots(i,m)$
($\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(1,j)(2,j)\dots(n,j)$),
we call it the
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$
th row_
(_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j$
th column_) of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{n,m}$
and the vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(i,j)$
is the
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j$
th vertex of the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$th
row_ and the
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i$
th vertex of the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j$th
column_. The edges of the graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G_{n,m}$
are numbered similarly. An _elementary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$-wall_,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k\geq
3,$ is obtained from a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(k\times
2k)$-grid by deleting every odd edge in every odd column and every even edge
in every even column. An elementary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$-wall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
has a unique face whose boundary contains more than six vertices. The
_perimeter_ of an elementary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$-wall
is defined to be the subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
induced by all vertices that lie on the unique face with more than six
vertices. A
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
-wall_
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}$
is a subdivision of an elementary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$-wall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W.$
In other words,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}$
is obtained by the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$-wall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
after subdividing each edge of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
an arbitrary (possibly zero) number of times. The _perimeter_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime},$
denoted by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Per}(W^{\prime}),$
is the subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}$
induced by the vertices of the perimeter of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
together with the subdivision vertices of the edges of the perimeter of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W.$

Figure 4: A
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}9$-wall.
The subdivision vertices are in yellow and the four corners are in red.

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W\subseteq
G$ be a wall (here the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\subseteq$
denotes subgraph relation). The _compass_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
denoted by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Compass}_{G}(W),$
is the subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
induced by the vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Per}(W)$
together with the vertices of the unique component of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-\mathsf{Per}(W)$
that contains
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W-\mathsf{Per}(W).$
The _corners_ of an elementary
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-wall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
are first and the last vertices of the first and the last raw respectively.
Notice that if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
is an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-wall
its corners are not uniquely determined. However, we assume to always be given
some choice of corners which we identify with the names from above (see for
instance the red vertices in Figure 4). The _corner society_ of an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-wall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
is
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\mathsf{Compass}_{G}(W),\Omega_{W})$
where
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega_{W}$
is a cyclic ordering of the corners that agrees with a cyclic ordering of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Per}(W).$

######  Definition  (Flat Wall).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r\geq
2$ be an integer. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
be an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-wall
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Was say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
is _flat_ if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\mathsf{Compass}_{G}(W),\Omega_{W})$
has a vortex-free rendition in the disk.

We wish to stress that this definition is not exactly the definition of
flatness used in [21]. However, if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
is a flat wall in a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W-\mathsf{Per}(W)$
can be seen to satisfy the stronger requirements for the flatness of
Kawarabayashi et al. and any wall which is flat in this stronger sense also
must be flat in our sense.

To state the Flat Wall Theorem as in [21] we need to define what it means for
a minor to be attached to the infrastructure provided by a given wall.

######  Definition .

(Minor Models) Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
be a wall in a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
be some graph. If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
is a minor of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
then it is possible to find connected subgraphs
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X_{v}$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
for each
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v\in
V(H)$ such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X_{u}\cap
X_{v}=\emptyset$ if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}u\neq
v,$ and if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}uv\in
E(H),$ there exists an edge
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}e$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
with one end in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X_{u}$
and the other in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X_{v}.$
We say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\left\\{X_{v}\mid
v\in V(H)\right\\}$ for a _minor model_ (or simply a _model_) of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
We say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
_grasps an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$
minor_ if there exists a model
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\left\\{X_{v}\mid
v\in V(H)\right\\}$ together with indices
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i_{v},j_{v}$
for each
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v\in
V(H)$ such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X_{v}$
meet the intersection of the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i_{v}$th
row and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}j_{v}$th
column of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W.$

######  Theorem  (Flat Wall Theorem [39, 26]).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r,t\geq
1$ be integers,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}R:=49152t^{24}(40t^{2}+r),$
let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
be an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}R$-wall
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Then either
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
has a model of a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{t}$-minor
grasped by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W,$
or there exist a set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\subseteq
V(G)$ of size at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}12288t^{24}$
and an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-subwall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}\subseteq
W-A$ which is flat in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-A.$

#### Paths, Transactions, and Societies of Bounded Depth.

If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
is a path and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y$
are vertices on
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P,$
we denote by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}xPy$
the subpath of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
with endpoints
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}y.$
Moreover, if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
are the endpoints of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
and we have fixed an order of the vertices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P,$
say
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s$
is the first and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
the last vertex, then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}xP$
denotes the path
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}xPt$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Px$
denotes the path
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}sPx.$
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
be a path from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s$
to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
be a path from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q$
to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p.$
If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}x$
is a vertex in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(P)\cap
V(Q),$ then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}PxQ$
is the path obtained from the union of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Px$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}xQ.$
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X,Y\subseteq
V(G).$ A
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$
-path_ is a path of length at least one with both endpoints in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$
and internally disjoint from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X.$
In a society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega),$
we write
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$-path
as a shorthand for a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega)$-path.
A path is a
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$
-$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$-path_
if it has one endpoint in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$
and the other in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y.$
Whenever we consider
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$-$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y$-paths
we implicitly assume them to be ordered starting in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$
and ending in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Y,$
expect if stated otherwise.

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
be a society. A _segment_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
is a set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S\subseteq
V(\Omega)$ such that there do not exist
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{1},s_{2}\in
S$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t_{1},t_{2}\in
V(\Omega)\setminus S$ such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s_{1},t_{1},s_{2},t_{2}$
occur in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
in the order listed. A vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s\in
S$ is an _endpoint_ of the segment
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}S$
if there is a vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t\in
V(\Omega)\setminus S$ which immediately precedes or immediately succeeds
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s$
in the order
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega.$
For vertices
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s,t\in
V(\Omega)$ we denote by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s\Omega
t$ the uniquely determined segment with first vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s$
and last vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t.$
In case
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
immediately precedes
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s,$
we define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}s\Omega
t$ to be the _trivial segment_
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\Omega).$

######  Definition  (Linkage).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph. A _linkage_ in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
is a set of pairwise vertex disjoint paths. In slight abuse of notation, if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{L}$
is a linkage, we use
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\mathcal{L})$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}E(\mathcal{L})$
to denote
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\bigcup_{L\in\mathcal{L}}V(L)$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\bigcup_{L\in\mathcal{L}}E(L)$
respectively. Given two sets
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
we say that a linkage
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{L}$
is a
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
-$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$_-linkage
if every path in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{L}$
has one endpoint in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
and one endpoint in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B.$

######  Definition  (Transaction and Depth of a Vortex).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
be a society. A _transaction_ in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
is a linkage
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{L}$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$-paths
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
such that there exist disjoint segments
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A,B$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
where the paths in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{L}$
are
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$-$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$-paths.
We define the _depth_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
as the maximum cardinality of a transaction in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega).$

######  Definition  (Planar and Crooked Transactions).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{T}$
be a transaction in a society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega).$
We say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{T}$
is _planar_ if no two members of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{T}$
form a cross in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega).$
An element
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P\in\mathcal{T}$
is _peripheral_ if there exists a segment
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}X$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
containing both endpoints of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P$
and no endpoint of another path in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{T}.$
A transaction is _crooked_ if it has no peripheral element.

Finally we will need the following lemma.

######  Lemma  ([21]).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
be a society and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p\geq
1,$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q\geq
2$ positive integers. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{P}$
be a transaction in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
of order
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p+q-2.$
Then there exists
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{P}^{\prime}\subseteq\mathcal{P}$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{P}^{\prime}$
is either a planar transaction of order
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p$
or a crooked transaction of order
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}q.$

#### The Graph Minors Structure Theorem.

Next we are going to present two different statements, both fit to capture the
global structure of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$-minor-
free graphs. The first one focusses on the structure relative to a wall and
thus can be seen as a local extension of the Flat Wall Theorem, hence we call
this one the _Local Structure Theorem_. The second one is the Graph Minors
Structure Theorem that completely describes the structure of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}H$-minor-
free graphs in terms of graphs of bounded Euler genus with a bounded number of
bounded depth vortices, clique sums and apex vertices.

######  Definition  (Vortex Societies and Breadth and Depth of a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-Decomposition).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
be a surface and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta=(\Gamma,\mathcal{D})$
be a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Every vortex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
defines a society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\sigma(c),\Omega),$
called the _vortex society_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c,$
by saying that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
consists of the vertices
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi_{\delta}(n)$
for
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n\in\widetilde{c}$
in the order given by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Gamma.$
(There are two possible choices of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega,$
namely
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Omega$
and its reversal. Either choice gives a valid vortex society.). The _breadth_
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
is the number of cells
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ which are a vortex and the _depth_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
is the maximum depth of the vortex societies
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\sigma(c),\Omega)$
over all vortex cells
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta).$

Next we need to combine our definition of flat walls with the idea of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decompositions.
This is a necessary step so to be able to relate flat renditions of walls to
the drawings provided by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decompositions
and thus to impose additional structure onto these drawings.

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W\subseteq
W^{\prime}$ be two walls in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
is disjoint from the perimeter of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}.$
We say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
is _flat in a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$_
if there exists a closed disk
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta\subseteq\Sigma$
such that

  * •

the boundary of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta$
does not intersect any cell of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta,$

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi(N(\delta)\cap\mathsf{Boundary}(\Delta))\subseteq
V(\hat{\Omega}),$

  * •

for each degree-three vertex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}$
which belongs to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$,
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v$
is not mapped to a member of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N(\delta)$
by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi$,
let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{v}\in
C(\delta)$ be the cell with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}v\in\sigma(c_{v})$,
then the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{v}$
are pairwise internally disjoint,

  * •

no cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\subseteq\Delta$
is a vortex, and

  * •

$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W-V(\mathsf{Per}(W))$
is a subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\bigcup\left\\{\sigma(c)\mid
c\subseteq\Delta\right\\}.$

######  Definition
($\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$-central
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-Decomposition).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph, let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r\geq
1$ be an integer, let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}$
be an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r+2$-wall
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W\subseteq
W^{\prime}$ be the unique
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-subwall
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}$
disjoint from its perimeter. If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A,B)$
is a separation of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
of order at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r-1,$
then exactly one of the sets
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\setminus
B$ and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B\setminus
A$ includes the vertex set of a column and a row of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W.$
If it is the set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A,$
we say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A$
is the
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
-majority side of the separation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A,B)$_;
otherwise, we say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B$
is the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$-majority
side. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
be a surface and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta=(\Gamma,\mathcal{D})$
be a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
We say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
is
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
-central_ if there is no cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\sigma(c))$
includes the
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$-majority
side of a separation of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
of order at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r-1.$
Similarly, let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Z\subseteq
V(G),$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|Z|\leq
r-1,$ let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma^{\prime}$
be a surface and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta^{\prime}$
be a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma^{\prime}$-decomposition
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-Z.$
Then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta^{\prime}$
is a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$-central
decomposition of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-Z$
is for all separations
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A,B)$
of order at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r-|Z|-1$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B\cup
Z$ is the majority side of the separation
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(A\cup
Z,Z\cup B)$ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G,$
there is no cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta^{\prime})$ such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\sigma_{\delta^{\prime}}(c))$
contains
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}B.$

######  Theorem  (Local Structure Theorem [40, 21]).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r,p\geq
0$ be integers, and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}R:=49152p^{24}r+p^{10^{7}p^{26}}.$
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
be an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}R$-wall
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Then either
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
has a model of a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{p}$-minor
grasped by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W,$
or there exists a set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\subseteq
V(G)$ of size at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p^{10^{7}p^{26}},$
a surface
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
of Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p(p+1),$
a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$-central
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-A$
of depth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p^{10^{7}p^{26}}$
and breadth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2p^{2},$
and an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-subwall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}\subseteq
W-A$ which is flat in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta.$

From the local structure theorem, a global version can be derived.

An
_$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\alpha$
-near embedding_ of a graph
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
in a surface
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
of _depth_
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
and _breadth_
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
is a pair
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\delta,A)$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\subseteq
V(G),$
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|A|\leq\alpha,$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
is a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-A$
of depth888Please note that in [21] there is a difference between the “depth”
of a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
and the “width” of an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\alpha$-near
embedding. This difference arises from the fact that after resolving the
clique sums, each vortex can be decomposed into a path decomposition of
bounded width. This width however is related to the depth of the vortex by a
small constant factor.
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}k$
and breadth
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
such that for every
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ which is not a vortex,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\sigma(c))$
induces a clique in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}V(\sigma(c))\subseteq\pi(N(\delta)).$

######  Theorem  (Global Structure Theorem [40, 21]).

There exists a constant
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c$
that satisfies the following. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p\geq
1$ be a positive integer and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph which does not contain
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{p}$
as a minor. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\alpha:=p^{18\cdot
10^{7}p^{26}+c}.$ Then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
has a tree decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(T,\beta)$
of adhesion at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}4\alpha$
such that for all
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t\in
V(T),$ if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G^{\prime}$
is the torso of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
at
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}t$
then
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G^{\prime}$
has an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\alpha$-near
embedding of breadth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2p^{2}$
and depth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\alpha$
in a surface of Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p(p+1).$

###  2.2 A refined version of Subsection 2.1

The next step is to derive slightly refined versions of Subsection 2.1.
Towards this goal we first introduce additional definitions from [21] and then
describe in some detail how the refined versions follow from the proofs in
[21].

#### Societies and Nests.

The proof of Subsection 2.1 in [21] is based on the systematic study of
societies. We start by introducing further definitions.

######  Definition  (Cylindrical Rendition).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
be a society,
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\rho=(\Gamma,\mathcal{D})$
be a rendition of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
in a disk, and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{0}\in
C(\rho)$ be such that no cell in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C(\rho)\setminus\left\\{c_{0}\right\\}$
is a vortex. In those circumstances we say that the triple
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(\Gamma,\mathcal{D},c_{0})$
is a _cylindrical rendition_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
around
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{0}.$

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\rho=(\Gamma,\mathcal{D})$
be a rendition of a society
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}(G,\Omega)$
in a surface
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma.$
For every cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\rho)$ with
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|\widetilde{c}|=2$
we select one of the components of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Boundary}(c)-\widetilde{c}.$
This selection will be called a _tie-breaker in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\rho$_,
and we will assume that every rendition comes equipped with a tie-breaker. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
be either a cycle or a path in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
that uses no edge of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\sigma(c)$
for every vortex
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\rho).$ We say that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
is _grounded_ in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\rho$
if either
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
is a non-zero length path with both endpoints in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi_{\rho}(N(\rho)),$
or
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
is a cycle and it uses edges of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\sigma(c_{1})$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\sigma(c_{2})$
for two distinct cells
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c_{1},c_{2}\in
C(\rho).$ If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
is grounded we define the _trace_ of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
as follows. Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{1},\dots,P_{k}$
be distinct maximal subpaths of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
such that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{i}$
is a subgraph of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\sigma(c)$
for some cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c.$
Fix an index
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i.$
The maximality of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}P_{i}$
implies that its endpoints are
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi(n_{1})$
and
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\pi(n_{2})$
for distinct nodes
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}n_{1},n_{2}\in
N(\rho).$ If
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|\widetilde{c}|=2,$
define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L_{i}$
to be the component of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Boundary}(c)-\left\\{n_{1},n_{2}\right\\}$
selected by the tie-breaker, and if
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}|\widetilde{c}|=3,$
define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L_{i}$
to be the component of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathsf{Boundary}(c)-\left\\{n_{1},n_{2}\right\\}$
that is disjoint from
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\widetilde{c}.$
Finally, we define
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L_{i}^{\prime}$
by pushing
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L_{i}$
slightly so that it is disjoint from all cells in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C(\rho).$
We define such a curve
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}L_{i}^{\prime}$
for all
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}i,$
maintaining that the curves intersect only at a common endpoint. The _trace_
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}Q$
is defined to be
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\bigcup_{i\in[k]}L_{i}^{\prime}.$
So the trace of a cycle is the homeomorphic image of the unit circle, and the
trace of a path is an arc in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta$
with both endpoints in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}N(\rho).$

######  Definition  (Nest).

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

We are finally ready to state the refined version of Subsection 2.1. The
purpose of this refinement is to establish the nest structure around the
vortices in Subsection 2.1 in such a way that we are able to guarantee large
nests for all vortices while also keeping these nests disjoint. A similar
statement can be found in [12] presented there in different terminology
without explicit bounds, and with a slightly different definition for the
depth of a vortex.

######  Theorem  (Local Structure Theorem (with vortex infrastructure)[40,
21]).

Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r,p\geq
0$ be integers, and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}R:=49152p^{24}r+p^{10^{7}p^{26}}.$
Let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
be a graph and let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$
be an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}R$-wall
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G.$
Then either
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G$
has a model of a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}K_{p}$-minor
grasped by
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W,$
or there exists

  1. i)

a set
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}A\subseteq
V(G)$ of size at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p^{10^{7}p^{26}},$

  2. ii)

a surface
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$
of Euler genus at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p(p+1),$

  3. iii)

a
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W$-central
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Sigma$-decomposition
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta=(\Gamma,\mathcal{D})$
of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}G-A$
of depth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}p^{10^{7}p^{26}}$
and breadth at most
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}2p^{2},$

  4. iv)

an
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}r$-subwall
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}W^{\prime}\subseteq
W-A$ which is flat in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta,$

  5. v)

for each vortex cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ there exists a nest
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\mathcal{C}_{c}$
of order
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}10^{21}p^{100}$
in
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\delta$
around the unique disk
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta\in\mathcal{D}$
corresponding to
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c,$
and

  6. vi)

for each vortex cell
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c\in
C(\delta)$ let
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{c}\subseteq\Sigma$
be the disk bounded by the trace of
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}C_{10^{21}p^{100}}\in\mathcal{C}_{c},$
then for each pair of distinct vortex cells
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}c,c^{\prime}\in
C(\delta)$ we have that
$\color[rgb]{0.1,0.1,.34}\definecolor[named]{pgfstrokecolor}{rgb}{0.1,0.1,.34}\Delta_{c}\cap\Delta_{c^{\prime}}=\emptyset.$

The reason why Subsection 2.2 is more convenient to work with than the main
theorem of [12] lies in the fact that the later was formulated for graphs of
high treewidth only, while the above theorem only requires the existence of a
large wall. While high treewidth and the existence of large walls are famously
parametrically equivalent, it is much easier to derive a global version for