# Well-quasi-orders on embedded planar graphs

Corentin Lunel, Clément Maria

► To cite this version:

Corentin Lunel, Clément Maria. Well-quasi-orders on embedded planar graphs. 2025. hal-05400339

HAL Id: hal-05400339

https://hal.science/hal-05400339v1

Preprint submitted on 5 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Well-quasi-orders on embedded planar graphs

Corentin Lunel*

Clément Maria†

## Abstract

The central theorem of topological graph theory states that the graph minor relation is a well-quasi-order on graphs. It has far-reaching consequences, in particular in the study of graph structures and the design of (parameterized) algorithms. In this article, we study two embedded versions of classical minor relations from structural graph theory and prove that they are also well-quasi-orders on general or restricted classes of embedded planar graphs. These embedded minor relations appear naturally for intrinsically embedded objects, such as knot diagrams and surfaces in $\mathbb{R}^3$.

Handling the extra topological constraints of the embeddings requires careful analysis and extensions of classical methods for the more constrained embedded minor relations. We prove that the embedded version of immersion induces a well-quasi-order on bounded carving-width plane graphs by exhibiting particularly well-structured tree-decompositions and leveraging a classical argument on well-quasi-orders on forests. We deduce that the embedded graph minor relation defines a well-quasi-order on plane graphs via their directed medial graphs, when their branch-width is bounded. We conclude that the embedded graph minor relation is a well-quasi-order on all plane graphs, using classical grids theorems in the unbounded branch-width case.

## 1 Introduction

An abstract graph $H$ is a **minor** of an abstract graph $G$ if a graph isomorphic to $H$ can be obtained from $G$ by a sequence of edge contractions and edge or vertex deletions. Equivalently, $H$ is a minor of $G$ if the vertices of $H$ can be sent to disjoint subgraphs of $G$, and the edges of $H$ sent to *vertex-disjoint* paths connecting the images of their endpoints. In a series of twenty papers, written over the course of twenty years, Robertson and Seymour proved the *graph minor theorem*, stating that the minor relation is a *well-quasi-order* on the set of graphs. It implies that any class of graph that is closed under taking minors can be characterized by a finite set of excluded minors. This exceptional achievement has had vast consequences in mathematics and computer science, and in particular for our understanding of graph structures and the design of algorithms.

The theory has close ties with topology. Notably, for a graph to be embeddable on a surface of genus $g$ is a property closed under taking minors, which implies that the family of genus $g$ graphs is characterized by a finite set of excluded minors. For example, planar graphs are exactly those graphs which exclude the clique $K_5$ and the complete bipartite graph $K_{3,3}$ as minors. In a somehow opposite direction, a byproduct of Robertson-Seymour theory is the *graph structure theorem*, which

<footnote>*Charles University, Prague, Czechia, corentin.lunel@kam.mff.cuni.cz</footnote>

<footnote>†INRIA UniCA, clement.maria@inria.fr</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Two plane graphs $G$ and $G'$ that are isomorphic but not equivalent as plane graphs. The graph $H$ is a minor of both $G$ and $G'$, an embedded minor of $G$ obtained by contracting the embedding of $e$. But it is not an embedded minor of $G'$: no embedded edge contraction or deletion in $G'$ results in a plane graph with 2 faces, one of which contains edges in its inside.</figcaption></figure>

roughly states that any graph excluding a fixed minor $H$ can be reconstructed by combining pieces nearly embeddable on a surface where $H$ cannot be embedded.

The theory concerns *abstract graphs*. For example, the characterization of planar graphs with excluded minors concerns graphs that can be embedded in the plane, as opposed to *plane graphs*, which are planar graphs together with one (of possibly many distinct) planar embedding. Two plane graphs are *equivalent* if there is a self-homeomorphism of the plane taking the image of one graph onto the image of the other. This is a stronger notion of equivalence than graph isomorphism; see Figure 1.

The notion of a minor naturally adapts to the embedded context. More precisely, edge and vertex deletions can be defined on embedded graphs, and an *embedded contraction* of an embedded edge $e$ consists of taking a closed disk $D$ in the plane containing $e$ and not intersecting the graph otherwise, and contracting $D$ into a point. In consequence, a plane graph $H$ is an *embedded minor* of a plane graph $G$ if a plane graph equivalent to $H$ can be obtained from $G$ by a sequence of embedded edge contractions and edge and vertex deletions. This notion is not equivalent to the (abstract) minor relation, as illustrated in Figure 1.

The concept of *embedded minor* is a natural one, and notably the question whether the embedded minor relation defines a well-quasi-order on embedded graphs. This *embedded* version of the graph minor theorem has already found applications for intrinsically embedded objects found in knot theory [17] or surface theory [1]. However, the embedded graph minor theorem has an ambiguous status. While some consider it folklore, as a natural extension of the tools designed by Robertson and Seymour in their vast Graph Minors series, proofs have also been claimed [1, 17] then withdrawn and/or contain gaps. To the best of our knowledge, we are not aware of a complete written proof of the result.

**Our results** The goal of this paper is to prove that *embedded* counterparts of the minor relation, and related concepts such as *immersion*, do define well-quasi-orders on graphs *embedded* in the plane. We strive to offer a self-contained and accessible proof for the bounded width case which is the main contribution of this work. Our main result is the following general theorem:

**Theorem 1.1.** *Graphs embedded in $\mathbb{R}^2$ are well-quasi-ordered by embedded minors.*

To prove it, we first study the relation of embedded immersion on plane graphs. The concept of *immersion* is related to the minor relation. An immersion of a graph $H$ in a graph $G$ is a function that sends vertices of $H$ to vertices of $G$ injectively, and edges of $H$ to *edge-disjoint* paths in $G$
connecting the images of their endpoints. It is related to the *carving-width* parameter of a graph, which measures the size of optimal edge-cuts, organized in a *tree-decomposition*, decomposing a graph. We study the embedded version of graph immersion. We prove that:

**Theorem 1.2.** *Graphs embedded in $\mathbb{R}^2$ with bounded carving-width are well-quasi-ordered by embedded immersion.*

This theorem relies on the construction of particular well-structured tree decompositions for (abstract) graphs, that are of independent interest. A *bond* carving-decomposition of a graph $G$ is a carving-decomposition whose system of cuts split $G$ into *connected* subgraphs. A carving-decomposition is *linked* if the cut-sets carried by the edges of the tree decomposition satisfy a global minimality condition. We prove the existence of carving-decompositions that are both bond and linked:

**Theorem 1.3.** *Let $G$ be a 2-vertex-connected graph. Then, there exists a bond-linked carving-decomposition of $G$ of width $cw(G)$.*

We also introduce a topological relaxation of bond decompositions, called *disc*, and prove there
existence on general plane graphs:

**Proposition 1.4.** *Let $G$ be a graph embedded in $\mathbb{S}^2$. Then, there exists a disc carving-decomposition of $G$ of width $cw(G)$.*

Finally, by leveraging on a classical argument by Nash-Williams [19] for well-quasi-orders on
trees, we prove Theorem 1.2.

By exploiting the correspondence between embedded minors in a plane graph $G$, and embedded
(directed) immersions in its *medial graph* $DM(G)$, we prove that plane graphs with bounded branch-
width are well-quasi-ordered by embedded minors. The idea of exploiting the graph-medial graph
correspondence in this context was used in [17], but the correspondence minor-immersion was not
proved in the embedded context. We prove that a plane graph $H$ is an embedded minor of a
plane graph $G$ iff the (plane) medial digraph of $H$ is an embedded immersion of the (plane) medial
digraph of $G$. Finally, with a similar approach as for Theorem 1.2, we prove that plane medial
digraphs of plane graphs are well-quasi-ordered by embedded immersion, which conclude the proof
of Theorem 1.1 in the case of bounded branch-width plane graphs. Finally, we conclude the proof
of Theorem 1.1 by proving embedded versions of the classical grid theorems for unbounded branch-
width graphs ; these constructions are adaptations of existing results from the literature.

**Related work and proof techniques** The Nash-Williams conjecture is the counterpart of the graph minor theorem for immersions (on abstract graphs), and was established using the tools developed in the graph minor series in [25]. In this article, they mention that a stronger notion of immersion is left unproven: *strong immersion*, where vertices in the image of edges should be distinct from the images of vertices. Since then, establishing structural results about strong immersions has been of interest [5, 7, 8, 16]. The following is a direct corollary of Theorem 1.2, which can be of independent interest:

**Corollary 1.5.** *Planar graphs of bounded carving-width are well-quasi-ordered by strong immersions.*
The structure of graphs embeddable on surfaces is a wide field of research; see for example [2] for recent results on immersion and well-quasi-orders in this context. However, enforcing the embedding is relatively new, and may be put in perspective with the growing interest for structural approaches in low dimensional topology [1, 11, 4, 14, 12, 15, 17].

We claim to fix former contributions pertaining to computational topology [1, 17].

**Organization of this paper** We first provide wide standard background on graphs, topology, and orders in Section 2. We then provide formal definitions for the embedded minors relation in Section 3. Then, we establish the existence of bond-linked carving decompositions, Theorem 1.3, in Section 4, and disc-linked carving decomposition, Theorem 1.4, in Section 5.1. We then use these decompositions to prove Theorem 1.2 in the bounded carving-width case in Section 5, by building on an argument of Nash-Williams for well-quasi-orders on trees (Section 5.2 and 5.3). We then prove that plane graphs are well-quasi-ordered by embedded minor in Section 6 by first applying our methods to medial graphs when initial graphs have bounded branch-width, in Section 6.1. The case of unbounded branch-width is then treated by studying embedded versions of grid theorems, in Section 6.2.

# 2 Preliminaries

To ensure accessibility to both graph theory and topology communities, we introduce basic and more advanced notions from both fields. We invite the reader to skip any non necessary background section.

## 2.1 Background on graphs

We refer the reader to [6] for concepts in graph theory that we do not reintroduce here.

**Graphs.** Let $G$ be a graph, whose set of vertices is denoted by $V(G)$, and multi-set of edges denoted by $E(G)$. Graphs may have **self-loops** (edges with identical endpoints) and **multi-edges** (a set with several identical edges, we do not give here a formal framework for this as they will be introduced in the relevant sections).

The **neighbors** $N_G(v)$ of a vertex $v$ of $G$ is the subset of vertices of $G$ sharing an edge with $v$, i.e., $u \in N_G(v) \Leftrightarrow (u, v) \in E(G)$. Let $A, B \subseteq V(G)$ be two disjoint subsets of vertices of $G$; the **cut** between $A$ and $B$ in $G$, denoted by $E_G(A, B)$, is the set of edges with exactly one endpoint in $A$ and one endpoint in $B$, i.e., $E_G(A, B) := \{(u, v) \in E(G) | u \in A, v \in B\}$. When $B = V(G) \setminus A$, we simply write $E_G(A) = E_G(A, B)$ for the cut induced by $A$.

The **subgraph induced** by $A \subseteq V(G)$, denoted by $G[A]$, is the subgraph of $G$ on vertices $A$ where only edges with both endpoints in $A$ remain: $G[A] = (A, \{e \in E(G) \cap A \times A\})$. The cut between two vertex-disjoint subgraphs is defined to be the cut between their vertex sets. A graph is said to be **$k$-vertex-connected** if removing any $k-1$ vertices leaves the graph connected. A connected graph which is not 2-vertex-connected admits at least a **cut-vertex**: a vertex whose removal renders $G$ disconnected. The **degree** of a vertex is the number of edges incident to it, counted with multiplicity: self-loops count as two-edges. A graph is said to be **$k$-regular** if all vertices have degree $k$.
When there is no ambiguity, we drop $G$ from the notations, and write $V$ and $E$ for the vertices and edges, $E(A, B)$ for a cut between $A$ and $B$, etc.

A **path** $P$ of size $k \le 1$ in $G$, between vertices $u, v \in V(G)$, is a sequence $v_0, e_0, v_1, e_1, \dots, e_{k-1}, v_k$, where $u = v_0$, $v_k = v$, and for each $i \in [0, k-1]$, $v_i$ and $v_{i+1}$ are endpoints of $e_i$ and the $v_i$'s are distinct. A **cycle** of $G$ is a path of $G$, except on its endpoints which are the same.

A **diagraph** or directed graph is a graph where edges have a direction, i.e., a head and a tail. A path in a diagraph has the additional restriction that the head of $e_i$ must be tail of $e_{i+1}$.

An **edge subdivision** in $G$ is the operation of removing edge $(u, v)$ from $G$ and replacing it by $(u, w)$ and $(w, v)$ where $w$ is a new vertex. If the edge is embedded, it can be realized by choosing a point in the relative interior of the edge to be the image of the new vertex $w$.

**Width invariants** Introduced by Seymour and Thomas in 1994 [27], the carving-width is another graph parameter aiming at quantifying how close a graph is to a tree.

A tree is **binary** if its vertices have either degree 3, called **inner vertices**, or degree 1, called **leaves**. Denote by $L(T)$ the set of leaves of a tree $T$. Let $G$ be a graph. A **carving-decomposition** of $G$ is a pair $(T, \phi)$ where $T$ is a binary tree and $\phi$ is an injective map from the vertices of $G$ to the leaves of $T$: $\phi: V(G) \to L(T)$. Note that in this definition, some leaves of $T$ may be unlabelled. However it is always possible to remove these edges by recursively removing unlabelled leaves, and merging edges incident to a vertex of degree 2. On the contrary, one can add an unlabelled leaf by subdividing any edge into two, and adding an edge incident to an unlabelled leaf at the vertex of degree 2.

Let $a \in E(T)$ be an edge in the tree $T$ of a tree decomposition of $G$. Removing $a$ from $T$ yields two subtrees $T_1^a, T_2^a$ of $T$. In this paper, to ease notations, we will indicate substructures obtained from a tree edge $a$ by using the notation $\cdot^a$, while sets of vertices and edges related to $a$ will be denoted using $\cdot(a)$.

The sets of vertices **displayed** by $a$ are the vertices falling on either side of $a$ in $T$, i.e., $V_1(a) = \phi^{-1}(L(T_1^a))$ and $V_2(a) = \phi^{-1}(L(T_2^a))$, and the graph cut associated to $a$ is defined by $T(a) = E(V_1(a), V_2(a))$. We also call the subgraphs $G[V_1(a)]$ and $G[V_2(a)]$ of $G$ the subgraphs **displayed** by $a$, and write for short $G_1^a$ and $G_2^a$. The **width** $w(a)$ of $a$ is the size of the associated cut $|T(a)|$, and the width of a **carving-decomposition** $D = (T, \phi)$ is the maximal width of an edge of $T$: $w(D) = \max_{a \in E(T)} w(a)$. Finally, the **carving-width** $cw(G)$ of $G$ is the minimal width of all of its carving-decompositions:

$$cw(G) = \min_{(T, \phi) \text{ carving-dec.}} \max_{a \in E(T)} |E_G(V_1(a), V_2(a))|.$$

A **branch-decomposition** a similar concept, where edges of a graph $G$ are injectively sent to the leaves of a binary tree. In this context, any edge of the tree partition $E(G) = E_1 \sqcup E_2$ into two parts ; the width of such tree edge is the number of vertices appearing as endpoints of both edges in $E_1$ and $E_2$. The **branch-width** is the minimum width of such a decomposition.

**Minor relations** To avoid redundancy with Section 3, where we introduce formally the embedded minor relation and the embedded immersion relation we study in this article, we only give informal notions of the more classical minor and immersion relations. We refer to [6, Chapter 1.7, 12] for a thorough introduction. An abstract graph $H$ is a **minor** of an abstract graph $G$, if a graph equivalent to $H$ can be obtained from $G$ by a sequence of edge contractions, and vertex and
edge deletions. An abstract graph $H$ is an **immersion minor** of an abstract graph $G$, if a graph equivalent to $H$ can be obtained from $G$ by a sequence of **lifts**, and vertex and edge deletions. A lift in a graph $G$ consists of replacing a pair of incident edges $\{(u, v), (v, w)\}$ by the single edge $\{(u, w)\}$.

## 2.2 Background on embedded graphs

We refer to [6, Chapter 4] for a broad presentation of planar graphs and related concepts.

Let $\Sigma$ be a surface, a **Jordan curve** of $\Sigma$ is the image $\gamma$ of a continuous injective map from $S^1 \to \Sigma$. By the Jordan-Schoenflies theorem [13], if $\Sigmaigma = S^2$ such a curve splits $S^2$ into two connected components which are homeomorphic to open discs.

Let $G$ be a graph. An embedding of $G$ into $\Sigma$, if it exists, is a drawing of $G$ on $\Sigma$ without crossings. More precisely, for each $e \in E(G)$ define $I_e = [0, 1]$, then an embedding of $G$ on $\Sigma$ is a PL map $f: V(G) \cup (\cup_{e \in E(G)} I_e) \to \Sigma$ such that:

* $f$ restricted to $V(G) \cup (\cup_{e \in E(G)} \mathring{I_e})$ is injective.

* $f$ restricted to each $I_e$ is continuous

* For each $e = (u, v)$, on $I_e$, $f|_{I_e}(0) = f(u)$, and $f|_{I_e}(1) = f(v)$.

Two embedded graphs $G_1$ and $G_2$ are **equivalent** if there exists an ambient isotopy, i.e., a continuous family of homeomorphism $f_t: \Sigma \to \Sigma$, taking the embedding of $G_1$ to the embedding of $G_2$. We consider embedded graphs up to this equivalence.

This formally indicates that one can draw $G$ on $\Sigma$ such that each edge is drawn continuously and no two drawn edges cross in their interior (they can meet at the end if they share the same endpoint). In the following sections, we will consider embedded graphs. However, to ease notations, we will denote by $G$ both the embedded graph and the abstract graph (where we forget about the embedding). A **plane graph** is a graph together with an embedding in $S^2$.

For $G$ an embedded graph, the set of **faces** $F(G)$ are the connected components of $\Sigma \setminus G$. The **dual** $G^*$ of $G$ is the abstract graph with set of vertices $F(G)$, and two vertices $F, F'$ of $G^*$ are adjacent if they share an edge of $G$. If $G$ is planar, there is a unique embedding of $G^*$ in $S^2$, however this embedding is not unique in $\mathbb{R}^2$. The **cut-cycle duality** is a bijection between the minimal cuts of $G$ and cycles of $G^*$ which can then be realized as Jordan curves.

## 2.3 Background on order theory

A **quasi-order** on a set $X$ is a binary relation $R$ satisfying reflexivity ($\forall x \in X, xRx$) and transitivity ($\forall x, y, z \in X^3, xRy$ and $yRz \Rightarrow xRz$). The relation $R$ is an **order** if it additionally satisfies antisymmetry ($\forall x, y \in X^2, xRy$ and $yRx \Rightarrow x = y$). A **strict quasi-order** satisfies irreflexivity ($\forall x \in X, \neg xRx$), asymmetry ($\forall x, y \in X^2, xRy \Rightarrow \neg yRx$) and transitivity. An order $R$ is said to be **linear** or **total** if all pairs of elements are comparable ($\forall x, y \in X^2, xRy$ or $yRx$). A **minimal element** for a quasi-order or strict quasi-order is an element $m$ with no other element of $X$ in relation with it: $\forall x \in X, \neg xRm$.

A **circular order** $C$ on $X$ is a ternary relation satisfying cyclicity ($\forall x, y, z \in X^3, C(x, y, z) \Rightarrow C(z, x, y)$), asymmetry ($\forall x, y, z \in X^3, C(x, y, z) \Rightarrow \neg C(x, z, y)$), transitivity ($\forall w, x, y, z \in X^3, C(x, y, z) \Rightarrow C(x, z, w) \Rightarrow C(x, y, w)$), and connectedness ($\forall x, y, z \in X^3, x \neq y \neq z \Rightarrow C(x, y, z) \text{ or } C(x, z, y)$).
One can think of $C(x, y, z)$ as $x$ meets $y$ before $z$. Any linear order $\le$ induces a circular one defined as $C_\le(x, y, z)$ if one of $x \le y \le z$, $z \le x \le y$, $y \le z \le x$ is satisfied. Similarly, choosing any $x \in X$ which is circularly ordered by $C$ defines a linear order $\le_x$ defined as $y \le_x z$ if $C(x, y, z)$, and $x \le_x y$ and $y \le_x z$ for all $y \in X$. Notice that the circular order induced by $\le_x$ is then $C$.

A well-quasi-order $R$ or w.q.o. on $X$ is a quasi-order for which every infinite sequence of elements admits an increasing pair, i.e., for all $(x_n)_{n \in \mathbb{N}} \in X^{\mathbb{N}}$, there exist $i < j$ such that $x_i R x_j$.

# 3 Embedded relations

In this section, we define the embedded minor relations as well as a characterization that we will often use for the embedded immersion. Embedded graph minor has been defined in [17], and to the best of our knowledge, we are not aware of a definition of embedded immersion or our characterization in the literature.

## 3.1 Embedded graph minor

In this section, we define the embedded minor relation, which has already been defined in [17]. This extension is quite natural, the abstract operations are turned into their embedded equivalents.

Let $H$ and $G$ be two plane graphs. The graph $H$ is said to be a plane minor of $G$ if $H$ can be obtained from $G$ by a sequence of vertex deletions, edge deletions, and embedded edge contractions. Deleting an edge is done on the embedding by removing its interior and formally by restricting the embedding to $V(G) \cup_{e \in E(G) \setminus \{e\}} I_e$. Deleting the vertex $v$ on the embedding is performed by removing the vertex and all its incident edges; formally the initial embedding is restricted to $(V(G) \setminus \{v\}) \cup_{e \in E(G) \setminus \{v \times V(G)\}} I_e$.

Abstractly, contracting the edge $e$ of $G$ consists in removing an edge and identifying its endpoints, which yields the graph $G/e$. To perform an embedded edge contraction on $e$ which is not a self-loop, choose a disc $D_e$ of $\mathbb{S}^2$ intersecting $G$ exactly on $e$ and contract this disc to a point by a homotopy $\psi: \mathbb{S}^2 \to \mathbb{S}^2$. It follows that $\psi \circ f$ is a continuous map from $V(G)$ to $\mathbb{S}^2$ which sends $I_e$ to a single point as well as its endpoints and is injective otherwise. Hence, $\psi \circ f = f'$ naturally translates to an embedding of $G/e$. These embedded operations are depicted on Figure 2.

<figure><img src="image_3.png" /><figcaption>Figure 2: Left: edge deletion of $e$. Right: vertex deletion of $v$. Below: edge contraction of $e$.</figcaption></figure>
## 3.2 Embedded immersion

Let $G$ be a plane graph. An **embedded lift** of the embedded edges $e = (u, v)$ and $e' = (v, w)$ of $G$ at $v$ in $\Sigma$, is the operation consisting of choosing a closed disc $D$ of $\Sigma$ such that $D \cap V(G) = \{v\}$, and $\forall e \in N(v) : |\{e \cap \partial(D)\}| = 1$ and $0$ if $e \notin N(v)$. Then, replacing $D \cap (e \cup e')$ by one of the two arcs of $\partial D$ between $e \cap \partial D$ and $e' \cap \partial D$ such that the obtained graph is still embedded (see Figure 3 for example). If $v$ is of degree 2, the remaining vertex is deleted since we consider connected graphs and the choice of arcs does not matter since they are isotopic. Otherwise, there is at least one additional incident edge to $v$ which will intersect $\partial D$ and determine the proper arc for the operation. An **embedded immersion** is an immersion that can be realized by a sequence of vertex deletions, edge deletions, and embedded lifts.

<figure><img src="image_4.png" /><figcaption>Figure 3: Left: illustration for an embedded lift of two edges $e, e'$ incident to $v$ yielding a merged edge $e''$. Right: Other edges determine which arc is valid for a planar embedding.</figcaption></figure>

We will work with an equivalent more combinatorial notion, ordered immersion and tangent paths. An **ordered graph** $G$ is the data of a set of vertices $V(G)$, an edge set $E(G)$, and for each vertex $v$, a circular order $C_v$ on the set of edges incident to $v$.

**Definition 3.1.** Let $H$ and $G$ be two ordered graphs. An ordered immersion of $H$ into $G$, also denoted $H$ is an ordered immersion of $G$, is a map $\phi$ defined on $V(H)$ and $E(H)$ such that:

1. $\phi|_{V(H)}$ is injective

2. for each pair of distinct edges $e, e'$, the paths $\phi(e)$ and $\phi(e')$ are edge-disjoint.

3. for each vertex $v \in V(H)$: for each edge $e \in E(H)$ incident to $v$ denote by $e'$ the edge of $\phi(e)$ incident to $\phi(v)$, then for all $e_1, e_2, e_3$ incident to $v$, $C_v(e_1, e_2, e_3) \Rightarrow C_{\phi(v)}(e'_1, e'_2, e'_3)$.

Applying properly Theorem 1.6 of [25] allows to prove that ordered immersion forms a well-quasi-order on ordered graphs of bounded degree. However, ordered immersion minor does not imply embedded immersion minor. Indeed, Figure 4 depicts two embedded graphs $G_1, G_2$ where $G_1$ is an ordered minor of $G_2$ (orders around vertices are induced by the embedding) but is not an embedded minor of $G_2$. Indeed, one can see $G_2$ as a drawing of $G_1$ in the plane except that each edge of two pairs of edges intersects. The ordered immersion is the natural identity on the whole graph, except on the two aforementioned pairs of parallel edges, which are mapped to 4 transverse paths which cross at the intersections. This immersion pattern is unique, and it enforces transversal paths that cannot be realized by embedded lifts in an embedded immersion.
<figure><img src="image_5.png" /><figcaption>Figure 4: Two embedded graphs, the order around each vertex is induced by the embedding. $G_1$ is an ordered minor of $G_2$ but not an embedded minor of $G_2$.</figcaption></figure>

This phenomenon motivates the following definition: a family of paths $(c_i)_{i \in I}$ in an ordered graph $G$ is said to be **transverse** if there exists a vertex $v \in V(G)$ such that $v$ is an inner vertex of a path $p_i$ and an endpoint of another, or if the incident edges to $v$ are **interlaced**, i.e., if around $v$ edges $e, e'$ of a path $p_i$ and edges $f, f'$ of path $p_j$ are met in the order $efe'f'$ for $i \neq j$. In that case $v$ is called a **transverse vertex**. A family of paths is **tangent** if all of its vertices are tangent vertices. For such a family, the embedded immersion can be realized by embedded lifts as illustrated by Figure 5. Note that forbidding inner vertex from a path to be the starting point of another correspond to the hypothesis of strong immersion as defined on abstract graphs.

<figure><img src="image_6.png" /><figcaption>Figure 5: Diverse paths of a family of paths (red, blue, and green paths) around a vertex. Left: tangent paths around a vertex and the associated embedded lift. Right: transverse paths around a vertex and the associated lift which is not an embedded lift.</figcaption></figure>

In the planar framework, embedded immersions are exactly captured by ordered immersion for which images of edges are tangent paths, and where the order around vertices is induced by the embedding.
**Lemma 3.2.** Let $H$ and $G$ be two plane graphs. Then $H$ is an embedded immersion of $G$ if and only if $H$ is an ordered immersion of $G$ for the circular order induced by the embedding on the plane sphere, with the additional property that the family of paths defined by images of edges is tangent.

*Proof.* Suppose that there exists an embedded immersion $\phi$ of $H$ in $G$. Without loss of generality, we first perform all edge deletions. Afterwards, each embedded lift of two edges $e$ and $e'$ at a common vertex $v$ yields a new embedded edge $e''$, where the embedded edges $\phi|_{I_e}$ and $\phi|_{I'_e}$ have been replaced by their merger $\phi|_{I''_e}$, i.e. their concatenation with a small perturbation near $v$; see Figure 3. The set $P$ of edges of $G$ which take part in embedded lifts is a set of edge-disjoint paths and cycles (for lifts creating a self-loop). By definition of embedded lift, $P$ is a family of tangent paths. In addition, the edges at the beginning and end of these paths are unchanged at their starts and ends, respectively, so that the ordering condition around vertices is satisfied and we have an ordered immersion from $H$ in $G$.

Reciprocally, if $H$ is an ordered immersion of $G$ where the family of paths $P$, which are images of edges, is a tangent family of paths, we first delete all edges of $H$ not part of $P$ and follow by deleting all isolated vertices. Let $v$ be an inner vertex of a path of $P$. At this point, all edges around $v$ are edges of $P$. Since $P$ is a family of tangent paths, there exist two edges $e, e'$ of the same path incident to $v$ and on the boundary of a common face $F$ (hence they are consecutive around $v$). An embedded lift can be performed at $v$ on $e, e'$ by choosing the arc on $F$ so that $e, e'$ are replaced by their merger in $P$. We perform this lift and repeat as long as there remain inner vertices in $P$. We suppress the remaining isolated vertex, by construction, the resulting graph is $H$ and was obtained by the sequence described above. $\square$

In Section 6.1, we consider embedded directed regular graphs, a plane digraph $H$ is an embedded immersion of a plane digraph $G$ if this is an embedded immersion with the additional constraint that path that are images of edges as expressed in Lemma 3.2 are directed paths. In term of embedded lift it means that we can only merge edges that follow themselves: the head of the first one is the tail of the second one as illustrated in Figure 6.

<figure><img src="image_7.png" /><figcaption>Figure 6: Embedded directed lifts.</figcaption></figure>

The same proof as Lemma 3.2 with directed paths allows us to prove its equivalent in the directed setting:

**Lemma 3.3.** Let $H$ and $G$ be two plane digraphs. Then $H$ is an embedded directed immersion of $G$ if and only if $H$ is an ordered immersion of $G$ for the circular order induced by the embedding on the plane sphere, with the additional property that the family of directed paths defined by images of edges is tangent.
# 4 Bond-linked decomposition

The aim of this section is to establish the existence of well-structured decompositions on 2-vertex connected abstract graphs: These decompositions will be used as primary blocks for decompositions used in Section 5: the bond property is very useful for embeddings, while the linked property is a cornerstone of Nash-Williams’ argument. The existence of decompositions satisfying the linked property has been established in the graph minor series from Robertson and Seymour [22] and improvements to the methods used there were later developed by Geelen, Gerards, and Whittle [9]. The existence of bond carving-decomposition was established in [27]. The novelty of this section is to enforce both properties at the same time. To do so we first consider a linked carving-decomposition, and then refine it into being bond by following a direct version of the existence proof of a bond decomposition from [27] and checking that the linked property of the decomposition is preserved. The existence of such decompositions might be of independent interest.

## 4.1 Linked decomposition.

Let $A, B \subseteq V(G)$ be two disjoint sets of vertices of $G$; denote m-cut$(A, B) = \min_{A \subset X \subset B^c} |E(X)|$ as the minimum size of a cut separating $A$ and $B$. Let $(T, \phi)$ be a carving-decomposition of a graph $G$. Let $a, b$ be two edges of $T$, and let $P$ be the minimal path in $T$ containing both $a$ and $b$. Denote by $T_i^a$ the subtree of $T \setminus \{a\}$ that does not contain $b$, and denote by $A \subseteq V(G)$ the vertices of $G$ displayed by $a$ and associated to $T_i^a$. Denote similarly the set of vertices $B \subseteq V(G)$ displayed by $b$ and associated to the tree of $T \setminus \{b\}$ not containing $a$; see Figure 7. The edges $a$ and $b$ are said to be **linked** if the minimal width of an edge of $P$ is equal to the minimal cut separating $A$ and $B$, i.e., if m-cut$(A, B) = \min_{e \in P} w(e)$. A carving decomposition is said to be **linked** if all its pairs of edges are linked. Note that any edge on $P$ displays a set of vertices separating $A$ and $B$, so that by definition m-cut$(A, B) > \min_{e \in P} w(e)$ is impossible

<figure><img src="image_8.png" /><figcaption>Figure 7: Definition of the sets $F$ and $G$ from the edges $f, h$, and the path $P$.</figcaption></figure>

The existence of linked carving-decomposition is non-trivial; in fact, this was a critical point of [22] and the following Theorem 4.1 is mentioned as one of the main contributions of [9] (described as linked branch decomposition there, as they work in the broader framework of matroids and submodular functions). For the sake of completeness we include their proof here.
**Theorem 4.1.** [9, Theorem 2.1] Let $G$ be a graph of carving-width $k \in \mathbb{N}$. Then, there exists a linked carving-decomposition of $G$ of width $k$.

Intuitively, a linked carving-decomposition is a carving-decomposition where an edge should have a width as low as possible since for each path joining two edges, an edge should achieve the minimal possible cut. Hence, to find one, it is natural to try to minimise the width of each edge of a decomposition.

Let $(T, \phi)$ be a carving-decomposition of $G$. We denote by $T_k$ the subforest of $T$ induced by the union of edges of width $\ge k$, and write $C(T_k)$ for the set of connected components of $T_k$. Let us consider a strict partial order $<_w$ on carving-decompositions of $G$, such that $(T, \phi) <_w (T', \phi')$ if there exists $k \in \mathbb{N}$ such that:

$$ \text{at weight } k: \begin{cases} \text{either} & |E(T_k)| < |E(T'_k)| \\ \text{or} & |E(T_k)| = |E(T'_k)| \text{ and } |C(T_k)| > |C(T'_k)| \end{cases} \\ \text{and for all } \ell > k: |E(T_\ell)| = |E(T'_\ell)| \text{ and } |C(T_\ell)| = |C(T'_\ell)|. $$

When there is no ambiguity, we simply write $T <_w T'$. On a high level, $<_w$ is a refinement of a colexicographic order on the tuples $(|w^{-1}(k)|)_{0 \le k \le |E(G)|}$.

**Lemma 4.2.** Let $G$ be a graph and $(T, \phi)$ be a carving-decomposition of $G$. If $(T, \phi)$ is not linked, then there exists a carving-decomposition $(\hat{T}, \hat{\phi})$ of $G$ such that $\hat{T} <_w T$.

*Proof.* Let $(T, \phi)$ be a carving decomposition of $G$ that is not linked, and let $a$ and $b$ be edges of $T$ which are not linked. Let $A$ be the set of displayed vertices by the tree of $T \setminus a$ not containing $b$, $B$ be the set of displayed vertices by the tree of $T \setminus b$ not containing $a$, and $P$ be the minimal path of $T$ containing both $a$ and $b$. Up to re-indexing, write $A = V_1(a) = \phi^{-1}(L(T_1(a)))$ and $B = V_1(b)$.

For two sets of vertices $X, Y \subseteq V(G)$, we say that $X$ splits $Y$ if $Y \setminus X \ne \emptyset$ and $X \cap Y \ne \emptyset$ (this relation is not reflexive). Pick $X \subseteq V(G)$ such that $A \subseteq X \subseteq B^c$, $|E(X)| = \text{m-cut}(A, B)$, and such that $X$ that splits a minimum number of sets of vertices displayed by edges of $T$, i.e., that splits a minimum number of sets $V_i(c)$ for $c \in E(T)$ and $i \in \{1, 2\}$.

We now define a new carving-decomposition $(\hat{T}, \hat{\phi})$ of $G$. The subtrees $T_2(b)$ and $T_2(a)$ both have exactly 1 vertex of degree 2, the ones incident to $b$ and $a$ in $T$ respectively; see Figure 8. We define $\hat{T}$ by taking a copy of $T_2(b)$ and a copy of $T_2(a)$, and connecting their vertices of degree 2 by a new edge. Then, we (partially) define the function $\hat{\phi}$ on $L(\hat{T})$ by $\hat{\phi}(v) = \phi(v)$ if $v$ belongs to the copy of $T_2(b)$ and $\phi(v) \in X$, or if $v$ belongs to the copy of $T_2(a)$ and $\phi(v) \in X^c$, and $\hat{\phi}(v)$ is undefined otherwise (see Figure 8).

Let $\hat{e}$ be an edge of $\hat{T}$ that is the copy of an edge $e$ in $T$ (note that there might be a second copy of $e$ in $\hat{T}$). If $\hat{e} \in T_2(b)$, let us assume by symmetry that $W = V_1(e)$ is the set of vertices of $G$ displayed by the tree of $T \setminus e$ not containing $b$. By definition, $w(e) = |E(W)|$ and $w(\hat{e}) = |E(X \cap W)|$. Note that for any set of vertices $X, Y$ of $V(G)$, a double counting argument on $E(X)$ and $E(Y)$ yields $|E(X \cap Y)| + |E(X \cup Y)| = |E(X)| + |E(Y)|$ (submodularity of $|E(\cdot)|$ is in fact enough). Then, $w(\hat{e}) + |E(X \cup W)| = |E(X \cap W)| + |E(X \cup W)| = |E(X)| + |E(W)| = \text{m-cut}(A, B) + w(e)$. Since $W \subseteq B^c$ by definition of $W$, $A \subseteq X \cup W \subseteq B^c$ so that $\text{m-cut}(A, B) \le |E(X \cup W)|$. Hence, $w(\hat{e}) \le w(e)$ with equality if and only if $\text{m-cut}(A, B) = |E(X \cup W)|$.

Now let us assume that $w(\hat{e}) = w(e)$ and that there is a second copy $e^*$ of $e$ in $T_2(a)$. We saw that $\text{m-cut}(A, B) = |E(X \cup W)|$ so that by definition of $X, W \cup X$ splits at least as many displayed sets as $X$. Let us assume by contradiction that $X$ splits $W$. Let $Y$ be a set of vertices
<figure><img src="image_9.png" /><figcaption>Figure 8: Construction of $\hat{T}$ from $T$. Green leaves are labelled by elements of $X$ while black ones belong to $X^c$. Leaves with no points are unlabelled.</figcaption></figure>

of $G$ displayed by some edge of $T$. If $W \cup X$ splits $Y$, then $Y \smallsetminus (W \cup X) \neq \emptyset$, which implies that $Y \smallsetminus X \neq \emptyset$. It also follows that $Y$ is not contained in $X$. Since displayed sets are either disjoint or satisfy a containment relation, either $W \subset Y$, which involves that $\emptyset \subset W \cap X \subset Y$, or $W$ and $Y$ are disjoint, which involves that $Y \cap (W \cup X) = Y \cap X \neq \emptyset$. In both cases, $X$ splits $Y$ and $X$ splits all displayed sets split by $W$, but this is absurd since $X$ splits in addition $W$. Hence $X$ does not split $W$: either $W \smallsetminus X = \emptyset$ or $W \cap X = \emptyset$, the former is true since $w(\hat{e}) = |E(W \cap X)| = w(e)$. If $e$ is in $P$, then $w(e^*) = |E(W \cup X)| = \text{m-cut}(A, B)$, otherwise $w(e^*) = |E(W \smallsetminus X)| = |E(\emptyset)| = 0$. Hence, at most one copy of $e$ has width greater than m-cut$(A, B)$ if $w(\hat{e}) = w(e)$.

If $\hat{e} \in T_2(a)$, the arguments above apply to conclude that $w(\hat{e}) \le w(e)$ if and only if m-cut$(A, B) = |E(X^c \cup W)|$ where $W = V_2(e)$. Then, noticing that $Y \smallsetminus X \neq \emptyset \Leftrightarrow Y \cap X^c \neq \emptyset$ and $Y \cap X \neq \emptyset \Leftrightarrow Y \smallsetminus X^c \neq \emptyset$, $X^c$ splits as many sets as $X$, and we reach the same conclusion: $w(\hat{e}) \le w(e)$ and at most one copy of $e$ has width greater than m-cut$(A, B)$ if $w(\hat{e}) = w(e)$.

The results above imply that for $i > \text{m-cut}(A, B)$, $|E(\hat{T}_i)| < |E(T_i)|$. By construction of $\hat{T}$, each connected component of $T_i$ is copied as at least a component of $T$, which can be separated into several ones in $\hat{T}_i$ since the weight of these edges cannot increase (or disappear entirely if all edges have small enough weight). At this point either there exists $i > \text{m-cut}(A, B)$ allowing us to conclude that $\hat{T} <_w T$ or for all $i > \text{m-cut}(A, B)$, $|E(\hat{T}_i)| = |E(T_i)|$ and $|C(\hat{T}_i)| = |C(T_i)|$. Let us see that this latter option leads to a contradiction. Set $j = \text{m-cut}(A, B) + 1$, we know that $|C(\hat{T}_j)| = |C(T_j)|$ and $|E(\hat{T}_j)| = |E(T_j)|$. Hence, every component $C_j \in C(T_j)$ has a copy $\hat{C}_j$ in $\hat{T}$, where each edge of $C_j \in C(T_j)$ is present in $\hat{C}_j$. In particular the component $C$ of $T_j$ containing $P$ is copied as $\hat{C}$ in $\hat{T}_j$, which contains the copy of $P$ and the copies of $a$ and $b$. This is absurd: $w(n) = j - 1$, the copies of $a$ and $b$ cannot lie in the same component of $\hat{T}_j$. Hence, $\hat{T} <_w T$. $\square$

*Proof of Theorem 4.1.* By definition of $<_w$, if $T' <_w T$, then $w(T') \le w(T)$. As mentioned in Section 2.1, one can remove unlabelled edges of a carving-decomposition $T$. Doing so yields a carving-decomposition $T'$ with less edges than $T$ without increasing the weight of each edge so that $T' <_w T$ if any edge is removed. Furthermore all carving-decompositions with no unlabelled edges have the same number of edges, there is a finite number of such decomposition. Consequently, applying iteratively Lemma 4.2 and suppressing unlabelled edges to a carving-decomposition of $G$ of minimal width $cw(G)$ eventually yields a minimal element of $<_w$. This minimal element has width $cw(G)$, and is linked by Lemma 4.2. $\square$
## 4.2 Bond decomposition.

Let $G$ be a connected graph, a carving-decomposition $(T, \phi)$ of $G$ is **bond** if for all edges $a \in E(T)$, the subgraphs of $G$ displayed by $a$, $G_1^a$ and $G_2^a$, are connected. An edge not satisfying this condition in a carving-decomposition is said to **produce a non-bond cut**. Hence, we need to restrict ourselves to 2-vertex-connected graphs since edges labeling cut-vertices produce non-bond-cuts.

In the following, we consider only carving decompositions with no unlabelled edges, this is always possible as explained in Section 2.1. We will constructively modify carving-decompositions one edge at a time, while updating the labeling $\phi$. We keep the notation $T$ for all updated trees.

Notice that, for two disjoint sets of vertices $A, B \subseteq (G)$ inducing connected subgraphs $G[A]$ and $G[B]$, the subgraph $G[A \cup B]$ induced by $A \cup B$ is connected if and only if the cut between $A$ and $B$ is non-empty, i.e., $E(A, B) \neq \emptyset$.

Let $v$ be an inner vertex of $T$, and denote by $(T_i^v)_{i \in \{1,2,3\}}$ the subtrees of $T$ rooted at the 3 neighbors of $v$. These subtrees partition vertices of $G$ into 3 sets $V_i^v = \phi^{-1}(L(T_i))$, and splits $G$ into 3 subgraphs $G_i^v = G[V_i^v]$ for $i \in \{1,2,3\}$; see Figure 9.

<figure><img src="image_10.png" /><figcaption>Figure 9: Subgraphs of $G$ induced by edges and vertices of $T$.</figcaption></figure>

Because $G$ is connected, we have the property that, for all $v \in V(T)$, at most one of the cuts $E(G_1^v, G_2^v)$, $E(G_2^v, G_3^v)$, and $E(G_1^v, G_3^v)$ is empty. Otherwise, one of the $G_i^v$'s would have $E(G_i) = \emptyset$ and thus be a disconnected component of $G$ (notice that none of the $G_i^v$'s are empty since there is at least a leaf in each $T_i^v$). This implies that the following quantity is well defined for all inner vertex $v$ of $T$ where $\{X, Y, Z\} = \{V_1^v, V_2^v, V_3^v\}$:

$$ \mu(v) = \begin{cases} |X| - 1 & \text{where } E(Y, Z) = \emptyset \\ 0 & \text{otherwise.} \end{cases} $$

The map $\mu$ defines a potential on the whole carving-decomposition by summing over all inner vertices of $T$: $\mu(T) = \sum_{v \in V(T) \setminus L(T)} \mu(v)$.

First, let us show that for a carving-decomposition of $G$, in which there is some edge yielding a non-bond cut of $T$, it is possible to decrease the potential of the carving-decomposition by modifying the branching of $T$ if $G$ is connected enough. Such an edge cut can only take place on edges not incident to leaves of $T$, as a single edge is always bond.

We describe the following local **rebranching** operation in a tree $T$ (see Figure 10 for a visual description). Let $a = (u, v)$ be a tree-edge connecting two inner vertices $u$ and $v$.
<figure><img src="image_11.png" /><figcaption>Figure 10: Rebranching on a where $E(A_1, A_2) = \emptyset$.</figcaption></figure>

Aside from $a$, the vertex $u$ is incident to two edges $(u, u_1)$, $(u, u_2)$, and the vertex $v$ is incident to two edges $(v, v_1)$, $(v, v_2)$. Let $A_1, A_2, B_1, B_2 \subseteq V(G)$ be the vertices associated to the subtrees $T^{u_1}, T^{u_2}, T^{v_1}, T^{v_2}$ rooted at $u_1, u_2, v_1, v_2$ respectively, and not containing the edge $a$. A rebranching of $T$ at $a$, as pictured in Figure 10, consists of connecting trees $T^{u_1}$ and $T^{v_1}$ with a new vertex $u'$ adjacent to $u_1$ and $v_1$, connecting trees $T^{u_2}$ and $T^{v_2}$ with a new vertex $v'$ adjacent to $u_2$ and $v_2$, and finally connecting $u'$ and $v'$ with an edge $a'$. If $(T, \phi)$ is a carving-decomposition of a graph $G$, and $T'$ is a tree obtained by rebranching an edge of $T$, then $(T', \phi)$ is a carving-decomposition of $G$ (using the same $\phi$ and the direct bijection between the leaves of $T$ and the leaves of $T'$). We now use rebranching to decrease the potential $\mu$ of a tree decomposition.

**Lemma 4.3.** [27, (5.3)] Let $G$ be a connected graph, $D = (T, \phi)$ a carving-decomposition of $G$, and an edge partitioning $V(G)$ into $A_1, A_2, B_1, B_2$, as in Figure 10, such that: $E(A_1, A_2) = \emptyset$ and both $E(A_1, B_1)$ and $E(A_2, B_2)$ are not empty. Then $\mu(T') < \mu(T)$ where $T'$ is a rebranching of $T$ at $a$.

This lemma is visually summarized by:

<figure><img src="image_12.png" /><figcaption>Figure 11: A — link between $X$ and $Y$ means $E(X, Y) \neq \emptyset$.</figcaption></figure>

*Proof.* We use the notations of Figure 10. Let us assume by contradiction that $\mu(T') \ge \mu(T)$ after rebranching at edge $a = (u, v)$. The potential $\mu$ being of integral value, this is equivalent to $\mu(T') + 1 - \mu(T) > 0$. Rebranching modifies trees locally, therefore there is a natural map between vertices of $T$ and $T'$ that are away from the rebranching, i.e., $V(T) \setminus \{u, v\} = V(T') \setminus \{u', v'\}$.
Additionally, note that for a vertex $x \in V(T) \setminus \{u, v\} = V(T') \setminus \{u', v'\}$, the partitions of vertices of $G$ induced by the subtrees $(T_i^x)_{i \in \{1,2,3\}}$ in $T$, or induced by the subtrees $(T_i^{x'})_{i \in \{1,2,3\}}$ in $T'$, are the same. In consequence, by definition the potential value $\mu(x)$ in $T$ or $T'$ is unchanged for $x \notin \{u, v\}$. It follows that:

$$\mu(T') + 1 - \mu(T) = \mu(u') + \mu(v') - \mu(u) - \mu(v) + 1 > 0,$$

where $\mu(u), \mu(v)$ are defined in $T$, and $\mu(u'), \mu(v')$ are defined in $T'$.

Now, with the hypothesis $E(A_1, A_2) = \emptyset$, we have that $\mu(u) = |B_1 \cup B_2| - 1 = |B_1| + |B_2| - 1$, and therefore,

$$(\mu(v') - |B_2| + 1) + (\mu(u') - |B_1| + 1) - \mu(v) > 0 \quad (1)$$

This inequality implies that at least one of $\mu(v') - |B_2| + 1$ and $\mu(u') - |B_1| + 1$ is (strictly) positive. Without loss of generality, suppose that:

$$\mu(v') - |B_2| + 1 > 0, \quad (2)$$

the other case being similar by symmetry.

From the hypothesis $E(A_2, B_2) \neq \emptyset$, we deduce that $\mu(v') \in \{|A_2| - 1, |B_2| - 1, 0\}$. With the inequality (2) and $B_2 \neq \emptyset$, we conclude that $\mu(v') = |A_2| - 1$, with $|A_2| > |B_1| > 0$, which implies, by definition of $\mu$, that $E(A_1 \cup B_1, B_2) = \emptyset$.

In consequence, we also have that $E(B_1, B_2) = \emptyset$, because $E(B_1, B_2) \subset E(A_1 \cup B_1, B_2)$. This in turn involves that $\mu(v) = |A_1| + |A_2| - 1$. Transposing these values of $\mu(v)$ and $\mu(v')$ into Equation (1), we get:

$$\mu(u') + 1 - |B_2| - |B_1| - |A_1| + 1 > 0. \quad (3)$$

The sets $A_1, B_1, B_2$ are non empty, hence $\mu(u') > 0$ and from the hypothesis $E(A_1, B_1) \neq \emptyset$, we deduce that $\mu(u') \in \{|B_1| - 1, |A_1| - 1\}$. However, we reach a contradiction since Inequality (3) implies that $\mu(u') - (|B_1| - 1) > 0$ and $\mu(u') - (|A_1| - 1) > 0$. Therefore, we prove $\mu(T) > \mu(T')$. $\square$

**Lemma 4.4.** Let $G$ be a connected graph, and $D = (T, \phi)$ be a linked carving-decomposition. Consider an edge $s = (u, v)$, yielding a non-bond cut, which is turned into an edge $s' = (u', v')$ by a rebranching: if $w(s) < w(s')$ then rebranching at $s$ yields a linked carving-decomposition.

*Proof.* Each path $P'$ in $T'$ is obtained from a path $P$ in $T$ by either replacing $s$ by $s'$ (e.g., from $A_1$ to $B_2$), suppressing $s$ (e.g., from $A_1$ to $B_1$), adding $s'$ (e.g., from $A_1$ to $A_2$), or doing nothing at all (e.g., a path $P'$ not using $s'$ and edges incident to it). Hence the linked property is already satisfied in $T'$ for all paths that are identical in $T$ and $T'$. For the other one, we know that they use $s$ or $s'$ and at least one edge incident to them. We name edges incident to $s$ by the lower-case version of the set that they induce, as summarized in Figure 12:

Let $f, h \in E(T)^2$ be such that $P$, the minimal path of $T$ containing $f$ and $h$, is different from $P'$. Recall the notations $F = V(G_i^f)$ and $H = V(G_j^h)$ where $i$ is such that $T_i^f$ is the unique tree of $T \setminus f$ not containing $h$ and vice versa for $H$ and $j$.

* If $P'$ was obtained from $P$ by suppressing $s$, then we can assume by symmetry that $F \subset A_i$ and $H \subset B_i$ with $i \in \{1, 2\}$, and it follows that $a_i$ is in $P'$. Since $A_i \subset A_1 \cup A_2$ and $E(A_1, A_2) = \emptyset$, then $|E(A_i)| = w(a_i) \le w(s) = |E(A_1 \cup A_2)|$ so that there exists $y \in P \setminus \{s\}$ such that m-cut($F, H$) = $y$. Thus, m-cut($F, H$) = $\min_{p \in P'} w(p) = w(y)$.
<figure><img src="image_13.png" /><figcaption>Figure 12: Notations</figcaption></figure>

• If $s$ in $P$ was replaced by $s'$ in order to obtain $P'$, then we can assume by symmetry that $F \subset A_i$ and $H \subset B_j$ where $i \neq j$. Because $(T, \phi)$ is a linked carving-decomposition and $w(s) \ge w(a_i)$, there exists $y \in P \setminus \{s\}$ such that $\mathrm{m-cut}(F, H) = y$. It follows that $w(s') \ge \mathrm{m-cut}(F, H) = w(y)$ where $y$ is also in $P'$.

• If $P'$ was obtained from $P$ by adding $s'$, then we can assume by symmetry that $F \subset X_1$ and $H \subset X_2$, where $X \in \{A, B\}$. Since $(T, \phi)$ is a linked carving-decomposition, there exists $y \in P$ such that $\mathrm{m-cut}(F, H) = y$ and $y$ also belongs to $P'$: $\mathrm{m-cut}(F, H) = \min_{p \in P'} w(p) = w(y)$.

There remains to deal with paths having $s'$ as an extremal edge. Let us assume, by contradiction, that $s'$ is not linked with an edge $f$, and let us call $P$ the minimal path of $T$ containing $s'$ and $f$. First, let us notice that because $w(s') > w(s)$ we have that:

$$ \left\{ \begin{array}{l} w(s') = |E(A_1 \cup B_1)| = |E(B_1, B_2)| + |E(A_1, B_2)| + |E(B_1, A_2)| \\ w(s) = |E(A_1)| + |E(A_2)| = |E(A_1, B_1)| + |E(A_1, B_2)| + |E(A_2, B_1)| + |E(A_2, B_2)| \end{array} \right. \qquad (4) $$

• If $F = A_i$, by symmetry let us assume that $i = 2$. Then, there exists $M$ such that $A_2 \subsetneq M \subsetneq A_2 \cup B_2$ and $|E(M)| < \min_{y \in P} w(y) = \min(w(s'), w(a_2))$. Intuitively, the set $M$ allows us to shorten the cut between $A_2$ and $B_2$ (which corresponds to $m_b < b$ and $m_a = c$ on Figure 13). This will lead to a contradiction on $a_2$ and $b_1$ being linked in $T$.

Now notice that $|E(B_1)| = |E(B_1, A_2)| + |E(B_1, B_2)| + |E(B_1, A_1)|$. With Inequality (4), we conclude that $|E(B_1)| - |E(A_2)| = |E(B_1, A_1)| + |E(B_1, B_2)| - |E(A_2, B_2)| > 0$. Hence, $\mathrm{m-cut}(B_1, A_2) \le |E(M)| < w(a_2) < w(s)$ in not reached on $b_1$ either. Thus, $a_2$ and $b_1$ are not linked in $T$, a contradiction.

• If $F = B_i$, by symmetry let us assume that $i = 2$. Then, there exists $M$ such that $B_2 \subsetneq M \subsetneq A_2 \cup B_2$ and $|E(M)| < \min_{y \in P} w(y) = \min(w(s'), w(b_2))$. Intuitively, we are able to shorten the cuts between $B_2$ and $A_2$ and between $B_1$ and $A_2$, hence they will not be linked in $T$. We have that $|E(M)| < |E(A_1 \cup B_1)|$ and:

$$ \left\{ \begin{array}{l} |E(A_1 \cup B_1)| = |E(B_1, B_2)| + |E(A_1, B_2)| + |E(B_1, A_2)| \\ |E(M)| = |E(B_1, B_2)| + |E(A_1, B_2)| + |E(M, A_2 \setminus M)| + |E(M \cap A_2, B_1)| \end{array} \right. \qquad (5) $$
With Inequality (5):

$$|E(B_1 \cup A_2 \setminus M)| = |E(M, A_2 \setminus M)| + |E(B_1, A_1 \cup B_2)| + |E(M \cap A_2, B_1)| \\ < |E(B_1, A_2)| + |E(B_1, A_1 \cup B_2)| = |E(B_1)|$$

Thus, m-cut($B_1, B_2$) $\le |E(M)| < \min(w(b_1), w(b_2))$: $b_1$ and $b_2$ are not linked in $T$ which is a contradiction.

•If $f$ is non-incident to $s'$, denote $X_i$ with $x \in \{A, B\}$ such that $F \subset X_i$. Then, there exists $M$ such that $X_i \subsetneq M \subsetneq A_i \cup B_i$ and $|E(M)| < \min_{y \in P} w(y)$ (Figure 13). However, since $s'$ and $x_i$ are linked in $T$, $M \subset X_i$ is impossible: $E(M)$ would separate $F$ and $X_i^c$ and $|E(M)|$ would be reached on an edge of both $P$ and $P'$. Hence, $M \cap Y_i \neq \emptyset$ where $\{X, Y\} = \{A, B\}$.

<figure><img src="image_14.png" /><figcaption>Figure 13: Visualisation of $M$ and the associated cuts.</figcaption></figure>

Intuitively, in Figure 13, we have that $m_a + m_b < c + d$ so that at least one of $m_a < c$ and $m_b < d$ is true, and the latter is necessarily true because $f$ and $x_i$ are linked in $T$. Then, $|E(M \cup X_i)| < |E(X_i)|$ and it boils down to the points above.

Formally, we have that:

$$\left\{ \begin{array}{l} |E(X_i)| = |E(M \setminus X_i, M \cap X_i)| + |E(X_i \setminus M, X_i^c)| + |E(M \cap X_i, (M \cup X_i)^c)| \\ |E(M)| = |E(X_i \setminus M, M \cap X_i)| + |E(M \setminus X_i, M^c)| + |E(M \cap X_i, (M \cup X_i)^c)| \\ |E(X_i \cap M)| = |E(X_i \setminus M, M \cap X_i)| + |E(M \setminus X_i, M \cap X_i)| + |E(M \cap X_i, (M \cup X_i)^c)| \\ |E(X_i \cup M)| = |E(X_i \setminus M, X_i^c)| + |E(M \setminus X_i, M^c)| + |E(M \cap X_i, (M \cup X_i)^c)| \end{array} \right.$$

By definition of $M$, and since $f$ and $x_i$ are linked in $T$, $|E(X_i \cap M)| > |E(M)| \Leftrightarrow |E(M \setminus X_i, M \cap X_i)| > |E(M \setminus X_i, M^c)|$. By adding $|E(X_i \setminus M, X_i^c)| + |E(M \cap X_i, (M \cup X_i)^c)|$ to both sides of the inequality, we obtain $|E(X_i \cup M)| < |E(X_i)|$ and we follow the previous point to show that this is a contradiction.

Thus, $T'$ is linked.

<figure><img src="image_15.png" /></figure>

By applying Lemma 4.3 and Lemma 4.4 consecutively on the tree of a linked carving-decomposition of minimal width provided by Theorem 4.1, we prove Theorem 1.3. Note that we need to restrict ourselves to 2-vertex-connected graphs since a vertex whose deletion would render the graph disconnected necessarily creates a non-bond cut on the edge incident to the leaf labeling it.

*Proof of Theorem 1.3.* Let $G$ be a 2-vertex-connected graph and $(T, \phi)$ a carving-decomposition of $G$. A vertex $u$ of $T$ is incident to an edge that produces a non-bond cut of $G$ if and only if $u$ is an inner vertex of $T$ such that $\mu(u) > 0$ (it cannot be a leaf).
Let $(T, \phi)$ be a carving-decomposition of $G$ of width $k$ that we can assume to be linked thanks to Theorem 4.1. Among them, we take a minimum one for the relation $<_w$ defined in Section 4.1; there exists some by Lemma 4.2 and furthermore among them, we minimise $\mu$.

Let us assume that $\mu(T) > 0$ and let $u$ be an inner vertex of $T$ incident to $e = (u, v)$ such that $G_1^e$ is disconnected and such that $\mu(u)$ is minimum and non-zero. We claim that we locally are in the situation of the left picture of Figure 10 and will use the associated notations. As $u$ is an inner vertex of $G$, we set $G_1^u = A_1$, $G_2^u = A_2$, and $G_3^u = B$, where $E(A_1, A_2) = \emptyset$ (see Figure below). Since $e$ is not incident to a leaf, we can further refine the splitting around $v$: we set $G_1^v = B_1$, $G_2^v = B_2$, and $G_3^v = A_1 \cup A_2$.

<figure><img src="image_16.png" /></figure>

Then, the assumption of minimality corresponds to $\mu(u) = |B| - 1$ being minimal among inner vertices of $T$ with non-zero $\mu$ value. Thus, we can assume that both $E(B_1, A_1 \cup A_2)$ and $E(B_2, A_1 \cup A_2)$ are non-empty. Indeed, if $E(B_1, A_1 \cup A_2) = \emptyset$, then $\mu(u) = |B| - 1 = |B_1| + |B_2| - 1 > |B_2| - 1 = \mu(v) > 0$, which is a contradiction. Hence, up to switching $B_1$ and $B_2$, we can assume that $E(A_1, B_1) \neq \emptyset$ and $E(A_2, B_2) \neq \emptyset$. Additionally, recall that the case $E(A_i, B) = \emptyset$ is not possible because $G$ is connected.

We now need to check that the current rebranching would yield by Lemma 4.3 a carving-decomposition $(T', \phi)$ with a width less or equal to $k$. Since $T$ and $T'$ would only differ by one edge, we need not check the width of all edges of $T'$ except $s'$. For $s'$, there are in fact two cases, with one of them that may require switching $B_1$ and $B_2$ before applying Lemma 4.3. However, by definition of $(T, \phi)$, at each inner vertex $v$ such that $\mu(v) > 0$, rebranching at $s = (u, v)$ yields a new edge $s' = (u', v')$ such that $w(s') > w(s)$: indeed, we chose the decomposition minimum for $<_w$ and then for $\mu$. Hence, Lemma 4.4 can be applied since each edge is modified at most once.

* If $E(A_1, B_2) = \emptyset$ or $E(A_2, B_1) = \emptyset$: let say, by symmetry, that $E(A_1, B_2) = \emptyset$; then $E(A_1 \cup B_1) \subset E(B_1)$ so that $w(e') = |E(A_1 \cup B_1)| \le |E(B_1)| < k$.

* If $E(A_1, B_2) \neq \emptyset$ and $E(A_2, B_1) \neq \emptyset$. We will show that up to switching $B_1$ and $B_2$, the modification of branching will yield $|w(e')| < k$ (notice that in that case, even with the switching, we can still apply Lemma 4.3).

As $T$ has width less than $k$, each edge incident to $e$ has width less than $k$:

$$ \begin{cases} |E(A_1, B_1)| + |E(A_2, B_1)| + |E(B_1, B_2)| < k \\ |E(A_1, B_2)| + |E(A_2, B_2)| + |E(B_1, B_2)| < k \end{cases} $$

Summing these inequalities yields: $(|E(A_1, B_2)| + |E(B_1, B_2)| + |E(A_2, B_1)|) + (|E(A_1, B_1)| + |E(A_2, B_2)| + |E(B_1, B_2)|) < 2k$. Hence, at least one of $E(A_1 \cup B_1)$ and $E(A_1 \cup B_2)$ has size less than $k$: we chose the minimal one. We may swap $B_1$ and $B_2$ so that $E(A_1 \cup B_1) < k$ is minimum.
As said in the first paragraph, as $G$ is 2-vertex-connected, $T$ is non-bond as long as $\mu(T) > 0$. However, we can always apply Lemma 4.3 and Lemma 4.4 to modify $T$ so that $w(T) < k$, $T$ is linked, and decrease $\mu(T)$ in the meantime. Furthermore $\mu(T)$ is an integer; hence this process will eventually yield a bond-linked carving-decomposition of width less than $k$. $\square$

# 5 Planar graphs with bounded carving-width

The aim of this section is to prove that connected plane graphs of bounded degree are well-quasi-ordered by embedded immersion, i.e., Theorem 1.2.

Since carving-width is bounded, we follow the classical approach of exploiting tree-like decomposition and then leverage an argument of Nash-Williams to exhibit a well-quasi-order. However, to handle properly embedded graphs, we require extra properties from their decompositions: being both linked and *almost bond*. Indeed removing edges of a bond decomposition separates the graph into two subgraphs embedded on two disjoint discs by cut-cycle duality which is a well-suited property for our purpose. However by definition of bond, only graph that are at least 2-vertex-connected can satisfy it. Hence we first define and establish the existence of decompositions satisfying the property of being nicely embeddable on discs and linked. Then, we will apply Nash-Williams' arguments to our framework to prove Theorem 1.2.

This last definition needs graphs to be embedded in $\mathbb{S}^2$, however since their carving-width is bounded, the result on graphs embedded in $\mathbb{S}^2$ implies the theorem for graphs embedded in $\mathbb{R}^2$ so that we will focus only on graphs embedded in $\mathbb{S}^2$, in the remaining of the section.

**Lemma 5.1.** If embedded graphs in $\mathbb{S}^2$ with bounded carving-width are well-quasi-ordered by embedded immersion, then embedded graphs in $\mathbb{R}^2$ with bounded carving-width are well-quasi-ordered by embedded immersion.

*Proof.* An embedding in $\mathbb{S}^2$ is an embedding in $\mathbb{R}^2$ where a face is chosen to be the unbounded one. We show how to mark such a face in this context using a graph with high carving-width.

Let $G_n$ be a family of embedded graphs in $\mathbb{R}^2$ with carving-width bounded by $k \in \mathbb{N}$. Choose $U$, a connected embedded graph in $\mathbb{R}^2$ such that $cw(U) > 1$. Set $G'_n = G_n \cup U$ where $U$ is embedded on the unbounded face of $G'_n$. Then, if $G'_i$ is an embedded immersion of $G'_j$, it follows that $G_i$ is an embedded immersion of $G_j$. Indeed the component $U$ of $G'_i$ is necessarily mapped to a component of $G'_j$ with carving-width at least $cw(U)$, by construction there is only one such component, which is the copy of $U$ in $G'_j$. Furthermore, no vertices of $G_i$ are mapped to vertices of $U$ in $G'_j$, because embedded immersion map vertices injectively. Then $G_i$ is an embedded immersion of $G_j$.

Every embedding in $\mathbb{R}^2$ induces an embedding in $\mathbb{S}^2$ by stereographic projection, for example. Let us denote $G_n^S$ such embedding of $G_n$ in $\mathbb{S}^2$. Let us assume that $G_i^S$ is an embedded immersion of $G_j^S$. An edge $e$ of $G_i$ is incident to the unbounded face of $G_i$ if and only if the associated edge in $G_i^S$ is incident to the face containing $U$ by construction. Hence, the embedded immersion of $G_i^S$ to $G_j^S$ directly translate to an embedded immersion from $G_i$ to $G_j$. $\square$

## 5.1 Handling cut-vertices and connected components.

Let us consider $G$ a plane graph and $T$ a carving-decomposition of $G$. As seen earlier, if $G$ has a cut-vertex, it cannot have a bond carving-decomposition. However, we need only a weaker version of bond which can be enforced even on graphs admitting cut-vertices. A carving decomposition $T$
has the **disc property** if for all $e \in E(T)$, there exists a Jordan curve $\gamma_e$ such that $G_1^e$ and $G_2^e$ lie on different sides of $\gamma_e$. Equivalently, there exists a disc $D_e$ such that $D_e$ is disjoint from $G_2^e$ and contains $G_1^e$. We call a carving-decomposition which is both linked and has the disc property: a **disc carving-decomposition**.

Note that contrary to bond and linked carving-decomposition, the disc property depends on the embedding. Furthermore, by cut-cycle duality, every bond decomposition of a planar connected graph satisfies the disc property for any embedding of the graph. Hence, we already established the existence of disc carving-decomposition for 2-vertex-connected graphs. To establish the existence of disc carving-decompositions in general, we will first prove the following technical but simple lemmas, allowing us to merge disc carving-decompositions and providing disc carving-decompositions for components of $G$ that are not 2-vertex-connected.

**Lemma 5.2.** Let $G$ be a plane connected graph and $v$ be a cut-vertex of $G$ such that $G = G_1 \cup G_2$ where $V(G_1) \cap V(G_2) = \{v\}$. If there exist two disc carving-decompositions $(T_1, \phi_1), (T_2, \phi_2)$ of width $k_1, k_2$ of $G_1, G_2$ respectively and a Jordan curve $\gamma$ intersecting only $v$ such that vertices of $G_1 \setminus v$ and $G_2 \setminus v$ lie on different sides of $\gamma$, then there exists a disc carving-decomposition of $G$ of width $\max\{k_1, k_2, |E_G(\{v\})|\}$.

*Proof.* We define a carving-decomposition of $G$ by merging $(T_1, \phi_1)$ and $(T_2, \phi_2)$ at their leaves $\ell_1, \ell_2$ labelled by $v$ (see Figure 14). To do so, we identify these leaves to create a new tree $T$ in which these merged leaves become an inner vertex $\ell$. We then add a new edge incident to $\ell$ and connect it to a newly created leaf $\ell'$ of $T$. We define $\phi$ to be equal to $\phi_1$ on $L(T_1) \setminus \{\ell_1\}$, equal to $\phi_2$ on $L(T_2) \setminus \{\ell_2\}$, and equal to $v$ on $\ell$.

<figure><img src="image_17.png" /><figcaption>Figure 14: Merging two disc carving-decompositions.</figcaption></figure>

Let $e'$ be the edge incident to $\ell'$, we associate to it a Jordan curve $\gamma_{e'}$, which is the boundary of a disc around $v$. We also associate to each edge incident to $e'$ a small perturbation of $\gamma$ so that $\gamma$ does not intersect $v$, but intersects $G$ exactly once on each edge of either $E_G(G_1)$ or $E_G(G_2)$.

Let $e$ be any other edge of $T$ and $\gamma_e$ be the associated Jordan curve for the disc property in the stemming $T_i$. By symmetry, let us assume that $e \in E(T_1)$. The curve $\gamma_e$ separates the vertices of $G$ into two sets, $A$ and $B$, that can be different from the sets of vertices that $T(e)$ separates. Indeed, this curve was defined only with respect to one $G_i$; it can contain vertices of the other subgraph. In this case, we isotope $\gamma_e$ by pushing it on the side of $\gamma$ containing $G_1$ so that $\gamma_e$ and $\gamma$ are disjoint, without modifying its intersection with $G_1$ (see Figure 15). This is possible since, by the disc property, no parts of $G_1$ one the side of $\gamma$ where we need to push. The result is a curve satisfying the disc property for $e$. By repeating these modifications, we prove that $(T, \phi)$ satisfies the disc property.

We now want to prove that the carving-decomposition is linked. In this proof, we will be
<figure><img src="image_18.png" /><figcaption>Figure 15: Modification of $\gamma_e$.</figcaption></figure>

considering cuts and their sizes in $G, G_1$, and $G_2$. For clarity, for $H \in \{G, G_1, G_2\}$, we will denote by m-cut($A, B; H$), m-cut($A, B$) with respect to the graph $H$.

-Now, let $a, b$ be two edges of $T$ that were both in $T_1$ or $T_2$, say $T_1$ by symmetry, and $A, B$ their associated set of vertices displayed in $T_1$. First notice that, for any set of vertices of $X$, $E_{G_1}(X \cap V(G_1)) \subset E_G(X)$. Indeed, $e \in E_{G_1}(X \cap V(G_1))$ means that $e$ has an endpoint in $X \cap V(G_1)$ and another in $V(G_1) \setminus X$, thus $e \in E_G(X)$. Furthermore, each edge $x$ of $T$ distinct from $e'$ has an equivalent $x_1$ in either $T_1$ or $T_2$, and by construction of the curves, $\gamma_x \cap G = \gamma_{x_1} \cap G_1$ so that $|T_1(x_1)| = |T(x)|$.

* If $v$ is in neither $A$ nor $B$ and $X$ is a set of vertices of $G_1$ such that $A \subset X \subset V(G_1) \setminus B$, then either $|E_G(X)| = |E_{G_1}(X)|$ or $|E_G(X \cup V(G_2))| = |E_G(X)|$ depending on whether or not $v$ is in $X$. Hence, $\min_{A \subset X \subset V(G) \setminus B} |E_G(X)| \le \min_{A \subset X \subset V(G_1) \setminus B} |E_{G_1}(X)|$. Now let $X \in \mathcal{P}(V(G))$ be a set of vertices of $G$ containing $A$ but disjoint from $B$: $A \subset X \subset V(G) \setminus B$. Set $X' = X \cap V(G_1)$, then $A \subset X' \subset V(G_1) \setminus B$, hence by the remark above, $|E_{G_1}(X')| \le |E_G(X)|$ so that m-cut($A, B; G_1$) = m-cut($A, B; G$).

* Otherwise, let assume by symmetry that $v \in A$. Then, the associated set of vertices to $a$ in $T$ is $A' = A \cup V(G_2)$ by construction of $T$. It follows that sets of vertices $X$ of $G$ satisfying $A' \subset X \subset V(G) \setminus B$ are in bijection by $X \mapsto X \cap V(G_1)$ with sets of vertices $X'$ of $G_1$ satisfying $A \subset X' \subset V(G_1) \setminus B$. It follows that m-cut($A, B; G_1$) = m-cut($A, B; G$).

Since $(T_1, \phi_1)$ is linked, there is one edge $p_1$ in $P_1$, the minimal path of $T_1$ containing both $a$ and $b$, such that $T_1(p) = \text{m-cut}(A, B; G_1)$. The path $P_1$ has a natural equivalent $P$ in $T$, and $p_1$ has an equivalent $p$ in $P$. Hence, m-cut($A, B; G$) = $|T(p)| = \min_{x \in P} |T(x)|$ (no edge has a smaller associated cut on the path $P$ according to the remark preceding this point).

-Let $a$ be an edge of either $T_1$ or $T_2$, say $T_1$ by symmetry, and set $b = e'$. Let $b'$ be the edge incident to $e'$ in the subtree of $T$ stemming from $T_1$. Notice that the edges $e'$ and $b'$ are linked since m-cut($A, B; G$) = $|E_G(G_2)| = |T(b')| = \min_{x \in P=\{e', b'\}} |T(x)| \le |E_G(\{v\})||T(e)|$. If $a \ne b'$, then, since $(T_1, \phi_1)$ is linked, there is one edge $p_1$ in $P_1$, the minimal path of $T_1$ containing both $a$ and $b'$, such that $T_1(p) = \text{m-cut}(A, V(G_2); G_1)$. The path $P_1$ has a natural equivalent $P$ in $T$, and $p_1$ has an equivalent $p$ in $P$.

Let $X \in \mathcal{P}(V(G))$ be a set of vertices containing $A$ but not $v$. Let us assume that there exists a vertex $y \in X \cap V(G_2)$. Then, there is a path $Y$ from $y$ to $v$ in $G_2$ and $Y \cap E_G(X) \ne \emptyset$. Hence,
$E_G(X) > E_{G_1}(X \cap V(G_1))$. Thus, m-cut($A, V(G_2)$; $G$) = m-cut($A, \{v\}$; $G$) = $\min_{x \in (P \cup e')}|T(x)|$ and this is achieved on the edge $p$.

-Let $a$ be an edge of $T_1$, $b$ be an edge of $T_2$, and $A, B$ be their associated vertex sets with respect to $T$. The minimal cut separating $A$ and $B$ contains only edges of either $G_1$ or $G_2$. Indeed, $v$ belongs to neither $A$ or $B$ since $e'$ is, by construction of $T$ on the tree of $T \setminus a$ containing $b$, and on the tree of $T \setminus b$ containing $a$. If $v$ is not separated by a cut $C$ from both $A$ and $B$, then $A$ and $B$ are not disconnected by $C$. Hence, $v$ needs to be separated from at least one of them, and separating $v$ from either $A$ or $B$ is enough to separate $A$ and $B$ since $v$ is a cut-vertex. Let $C$ be a cut separating $A$ and $B$; then one of $C \cap E(G_1)$ is $C \cap E(G_2)$ separates $A$ and $B$ and is at most as big as $C$. Hence m-cut($A, B$; $G$) = $\min(\text{m-cut}(A, \{v\}; G_1), \text{m-cut}(B, \{v\}; G_2))$. For reasons mentioned above, one edge $p$ of either the path from $e'$ to $a$ or the path from $e'$ to $b$ will realize this minimum. And this edge is not $e'$ since the following edge in each path has a smaller width. Hence the edge $p$ belongs to the path from $a$ to $b$ in $T$, and $a$ and $b$ are linked, and it follows that $(T, \phi)$ is a disc carving-decomposition of $G$.

Recall that the width of edges in $T$ is the same as their corresponding edge in $T_2$ or $T_1$. Since the width of $e'$ is $|E_G(\{v\})|$, it follows that the width of $(T, \phi)$ is $\max\{\text{cw}(G_1), \text{cw}(G_2), E_G(\{v\})\}$. $\square$

**Lemma 5.3.** Let $G$ be a 1-vertex-connected plane graph without non-trivial 2-vertex-connected component with at least one edge, then $G$ admits a disc carving-decomposition of width $\text{cw}(G) = \max_{v \in V(G)} |E(\{v\})|$.

*Proof.* If $G$ is a non-trivial 1-vertex-connected component but its only 2-vertex-connected components are singletons of $V(G)$, then $G$ is a tree with self-loops. Let us prove the result by induction on the size of the tree.

*If $G$ is reduced to a single edge, then $T$, also a tree with a single edge, is a disc carving-decomposition of $G$ of width $\text{cw}(G) = 1$.*

*Suppose by induction that our property is verified on any non-trivial embedded tree with less than $n > 2$ vertices. Let $G$ be an embedded tree with $n$ vertices and $\ell$ be a leaf of $G$ when self-loops are removed. $G' = G \setminus \ell$ admits a disc-carving decomposition $(T', \phi')$ of size $\text{cw}(G')$. Let $v$ be the leaf of $T$ labeling the neighboring vertex $f$ of $\ell$ in $G$, and $e' = (u, v)$ the edge of $T$ incident to $v$. To obtain a new tree $T$, let us subdivide $e'$ into two edges $(u, u')$ and $(u', v)$ and add the new edge $(u', l)$ to $T'$. Let us set $\phi(x) = \phi'(x)$ if $x \in L(T')$ and $\phi(l) = \ell$ (see Figure 16 for a visual summary). Then, $(T, \phi)$ is a carving-decomposition of $G$.*

<figure><img src="image_19.png" /><figcaption>Figure 16: Subdivision of $(u, v)$.</figcaption></figure>

It is possible to isotope each curve $\gamma_e$ for $e \in E(T')$ so that $\ell$ lies on the proper side without modifying the intersections with $G'$ by pushing along the edge incident to it in $G$ if needed. In that case either $f$ and $v$ lie on different sides, or the edge is $(w, v)$ and we can shrink $\gamma_e$ around $f$. Then,
we define $\gamma_\ell$ as a small circle around $\ell$ intersecting its incident edge once. Hence, $(T, \phi)$ satisfies the disc property.

For $a, b$, two edges of $T$, if none of them is $(w, l)$, it is clear that they are linked since they are linked in $T'$. Otherwise, let us assume that $a = (w, l)$. Then the minimal cut separating $\ell$ from any subset of $V(G')$ is the edge incident to $\ell$, which is reached at $a$. Hence $(T, \phi)$ is linked.

The carving-width of $G$ is lower bounded by the maximal degree among its vertices. Let $e$ be an edge of $T' \setminus (u, v)$, by construction of $T$, $T(e) = T'(e)$. In addition, $w((u', l)) = 1 \le w((u, u')) = |E_G(\{v\})| - 1 < w((u', v)) = |E_G(\{v\})|$. If $v$ is a vertex of maximal degree of $G$, then $cw(G) = |E_G(\{v\})|$. Otherwise, $cw(G) = \max_{x \in V(G')} |E_{G'}(\{x\})| = \max_{x \in V(G)} |E_G(\{x\})|$, which concludes this proof. $\square$

We now have a disc carving decompositions of 2-vertex-connected components, and the 1-vertex connected one in-between them that we can merge using Lemma 5.2.

**Proposition 5.4.** Let $G$ be a connected plane graph. Then, there exists a disc carving-decomposition of $G$ of width $cw(G)$.

*Proof of Proposition 5.4.* Let $D_1, \dots, D_k$ be the 2-vertex-connected components of $G$, and $D_{k+1}, \dots, D_n$ the remaining 1-vertex-connected non-trivial components of $G$ not containing 2-vertex-connected components of $G$. By definition, $D_1, \dots, D_n$ is a family of connected components of $G$, covering $G$, where $D_i \cap D_j$ is either empty or a single cut-vertex if $i \neq j$. By Theorem 1.3 and Lemma 5.3, there exists a family of disc carving-decompositions $(T_1, \phi_1), \dots, (T_n, \phi_n)$ where $(T_i, \phi_i)$ is a disc carving-decomposition of $D_i$ of width $cw(D_i)$.

We now iteratively merge these decompositions using Lemma 5.2: as long as our family of decompositions has two or more elements, there exists a pair of components $D_i, D_j$ intersecting on a cut-vertex $v$, since $G$ is connected. As $G$ is embedded, $D_j \setminus v$ lies entirely on a face of $D_i$. By pushing slightly the boundary of this face within itself, except at vertex $v$, we obtain a Jordan curve satisfying the condition of Lemma 5.2. We apply this lemma to obtain a new disc carving-decomposition $(T', \phi')$ of the merged component $D = D_i \cup D_j$ by which we replace $D_i, D_j$ and $(T_i, \phi_i), (T_j, \phi_j)$ in their respective families. We iterate this process until the remaining component is $G$ and we have a disc carving-decomposition $(T, \phi)$ of $G$.

A direct induction on this process yields that $w(T, \phi) = \max\{\max_{v \in G} |E_G(v)|, \max_{1 \le i \le n} cw(D_i)\}$. However, any carving-decomposition $(T', \phi')$ of $G$ can be turned into a carving-decomposition of any $D_i$ by unlabeling leaves of $T'$: we define $\psi$ such that $\psi(x) = \phi'(x)$ if $\phi'(x) \in V(D_i)$ and undefined otherwise. Every vertex removed from the labeling this way only decreases the width of the edges by definition. Hence, $w(T', \phi') \ge w(T', \psi) \ge cw(D_i)$. It follows that $cw(G) \ge \max_{1 \le i \le n} cw(D_i)$. Furthermore, $cw(G) \ge \max_{x \in V(G)} |E_G(\{x\})|$. Thus $w(T, \phi) \le cw(G)$, which implies by definition of carving-width that $w(T, \phi) = cw(G)$, which concludes the proof. $\square$

Similarly to Proposition 5.4, we consider disc carving-decompositions for each connected components and merge them, and prove the existence of disc carving-decomposition for general plane graphs (Proposition 1.4).

*Proof of Proposition 1.4.* Let $G_1, \dots, G_k$ be the connected components of $G$. By Proposition 5.4, there exists a family $\mathcal{T}$ of disc carving-decomposition $\mathcal{T} = (T_i, \phi_i)_{1 \le i \le k}$ such that $(T_i, G_i)$ is a disc carving-decomposition of $G_i$.

We now merge the carving-decompositions of $\mathcal{T}$. Let us illustrate the merging of two carving-decompositions $(T_1, \phi_1)$ and $(T_2, \phi_2)$ where the graphs $G_1$ and $G_2$ share a face of $G$. First choose a
vertex $v_i$ in each $V(G_i)$ such that the vertices $v_i$ are incident to the face shared by the two graphs $G_1$ and $G_2$, and let $e_i$ be the edge of $G_i$ incident to the leaf of $T_i$ whose label is $v_i$. We subdivide each $e_i$ and connect the vertices of degree 2 in each $T_i$ by a new edge $e'$ (see Figure 17) and define $\phi$ on $T$ by $\phi(v) = \phi_i(v)$ if $v$ is a leaf of $T_i$. This yields a carving-decomposition $(T, \phi)$ of $G_1 \cup G_2$ and replace $(T_1, \phi_1)$ and $(T_2, \phi_2)$ by $(T, \phi)$ in $\mathcal{T}$. Note that the width of $e'$ is 0 and that the width of other edges is the same as the one they stem from in each $T_i$. They are separated by a Jordan curve $\gamma$ that we use to modify curves $\gamma_e$ associated to edges of $T$ as in Proposition 5.2.

<figure><img src="image_20.png" /><figcaption>Figure 17: Merging of two disc carving-decompositions of a non-connected graph.</figcaption></figure>

We iteratively merge decompositions $(T_i, \phi_i)$ and $(T_j, \phi_j)$ whenever it is possible, i.e., when the graphs that label share a face. Note that there always exist a pair satisfying this property as long as there are two decompositions in $\mathcal{T}$.

Let $a, b$ be a pair of edges of $T$. If $a, b$ comes from the same $T_i$ then there is a natural bijection between cuts separating $A$ and $B$ in $G$ and those in $G_i$. It follows that they are linked in $T$ since they are linked in the original $T_i$. If they are not from the same $T_i$, their corresponding $A$ and $B$ are in two distinct connected components and the minimal cut separating them is empty. Furthermore, by construction, an edge merging two trees $T_i$ and $T_j$ is on the minimal path connecting them, its width is 0. Hence, $T$ is a disc carving-decomposition. $\square$

## 5.2 Order on edges.

Let $(G_n)_{n \in \mathbb{N}}$ be a family of plane graphs. Thanks to Proposition 1.4 we can define, for all $n \in \mathbb{N}$, a disc carving-decomposition $T_n$ of $G_n$. Furthermore, we assume that each tree $T_n$ is rooted at some unlabelled leaf called the root $r(T_n)$. If $T$ has no unlabelled leaf in the decomposition, we can add an unlabelled leaf by adding a vertex in the middle of an edge and connecting this vertex by an edge to a new leaf which will be the root; note that adding such a root yields a disc carving-decomposition. Let $a, b$ be two edges of $T \in \mathcal{T}$. The edge $a$ is said to be an **ancestor** of $b$ if $a$ lies on the unique path from $r(T)$ to $b$ and if for all edges $e$ between $a$ and $b$ on this path $w(e) \ge w(a) = w(b)$; in such a case, $b$ is called a **successor** of $a$. We define $\mathcal{T} = \bigcup_{n \in \mathbb{N}} T_n$ as the forest made of all the trees $T_n$.

Thanks to our assumption, for each edge $e$ of a carving-decomposition $(T, \phi)$ of a graph $G$, $T \setminus e$ consists of two subtrees of $T$, only one of which, written $T^e$, does not contain the root $r(T)$. We then define $G^e$ to be the embedded subgraph of $G$ induced by the vertices labelled by the leaves of $T^e$, i.e., $G^e := G[\phi^{-1}(L(T^e))]$.

We want to keep track of how edges of $T(e)$ leave $G^e$ in the embedding. Hence, for each $e \in E(T)$,
we define the **leaving graph** $\tilde{G}^e$, which is an embedded graph summarizing this information. Since $T$ satisfies the disc property,

there exists a Jordan curve $\gamma_e$ such that $G^e$ lies on one side of $\gamma_e$ and intersect $G$ exactly on $T(e)$. Up to isotopy, we can assume that each edge $x$ of $T(e)$ intersects $\gamma_e$ exactly once. The side containing $G^e$ is a disc that we call $D_e$. We subdivide each edge $f$ of $T(e)$ by introducing a new vertex $s_x$ at the point of intersection with $\gamma_e$. The embedded graph induced by $V(G^e) \cup_{x \in T(e)} \{s_x\}$ on $D_e$ is $\tilde{G}^e$ (see Figure 18). This way, $\tilde{G}^e$ consists of $G^e \cap D_e$, $(s_x)_{x \in T(e)}$, embedded on $D_e$.

<figure><img src="image_21.png" /><figcaption>Figure 18: How to obtain $\tilde{G}^e$ from $G$, the vertices $(s_x)_{e \in T(e)}$ are in green on $\partial D_e$.</figcaption></figure>

We can define a quasi-order on the set $\mathcal{E} = \cup_{T \in \mathcal{T}} E(T)$ of all edges of $\mathcal{T}$: for $e, f \in \mathcal{E}^2$, $e \prec f$ if $\tilde{G}^e$ is an embedded immersion of $\tilde{G}^f$ and the image of $(s_x)_{x \in T(e)}$ in the embedded immersion is $(s_x)_{x \in T(f)}$. Lemma 5.6 will then enforce that leaving graphs associated to tree edges are in relation if one edge is an ancestor of the other in our decompositions. To establish it, we first need to understand how to make a family of paths around a vertex tangent.

Consider a family of directed embedded paths $P = \{p_1, \dots, p_k\}$, where $p_i$ is a sequence of edges from vertex $v_{i,0}$ to vertex $v_{i,\ell_i}$. If two paths $p_i, p_j$ are transverse at a vertex $v$, it is possible to swap the two subpaths of $p_i$ and $p_j$ starting at $v$, so that $p_i$ now goes from $v_{i,0}$ to $v_{j,\ell_j}$ and $p_i$ now goes from $v_{j,0}$ to $v_{i,\ell_i}$. After this operation, called **path-swap**, $p_i$ and $p_j$ are tangent.

It can happen that after a path-swap, a path $p$ involved in the swap ends up traversing a same vertex twice (for example, a path-swap between the red and purple paths in Figure 21). In this case, a self-loop appears in $p$, which we simply remove. After any number of path-swaps, the family $P$ joins $\{v_{0,0}, \dots, v_{k,0}\}$ to $\{v_{0,\ell_0}, \dots, v_{0,\ell_k}\}$ by $k$ paths, which may have possibly lost some edges in the process.

**Lemma 5.5.** Let $P$ be a family of embedded directed paths $\{p_1, \dots, p_k\}$ and a vertex $v$. There exists a sequence of path-swaps transforming $\{p_1, \dots, p_k\}$ to a tangent family of paths at $v$.

*Proof.* Since paths not containing $v$ do not matter for the result, assume that every one of these paths uses $v$. As the paths are embedded, we can consider the circular sequence $s$ of indices of paths around $v$, where each incoming edge of $p^i$ is numbered $i$, and each outgoing edge of $p^i$ is numbered $i^{-1}$ (see Figure 19).

In $s$, two letters are interlaced ($i.e., i^{\pm 1}j^{\pm 1}i^{\mp 1}j^{\mp 1}$, where $x^{\pm}$ and $x^{\mp}$ have opposite exponents) if and only if their pair of associated paths are transverse at $v$. Two opposite and adjacent letters cancel out like in standard words: indeed, the path associated to this letters is tangent with no other
<figure><img src="image_22.png" /><figcaption>Figure 19: Order around $v$ and the result of the swaps.</figcaption></figure>

one; it will not be swapped with another path at $v$. Finally, the path-swap operation corresponds to exchanging the place in $s$ of two $\cdot^{-1}$ letters. To prove our lemma, we need to prove that we can bring $s$ to an empty word by iterating path-swa ps.

Let us consider any $i$ in $s$ that is followed by some $j^{-1}$ where $i \neq j$. Such a letter necessarily exists as long as $s$ is non-empty. Indeed, $s$ is equivalent up to circular rotations, and each letter in $s$ also has its opposite in $s$. Simply swap $j^{-1}$ and $i^{-1}$, which cancels $ii^{-1}$, and repeat. $\square$

**Lemma 5.6.** Let $G$ be a plane graph, $(T, \phi)$ a disc carving-decomposition of $G$, and $a, b \in E(T)^2$ such that $a$ is an ancestor of $b$. Then $b \prec a$.

*Proof*. The $\prec$ relation between $b$ and $a$ can be defined since the carving-decomposition satisfies the disc property. We denote $k = w(a) = w(b)$. Let assume that $G_1^a = G^a$ so that $A = V(G_2^a)$ and $B = V(G^b)$ with respect to the linked definition of $A$ and $B$. Let us call $P$ the minimal path of $T$ containing both $a$ and $b$. We define $H = G \setminus E(G_2^a) \cup E(G^b)$, in other words, the edges of $G$ between $T(a)$ and $T(b)$ (where $T(a)$ and $T(b)$ are included). By construction, there are two disjoint families $\mathcal{F}_a = V(H) \cap V(A)$ and $\mathcal{F}_b = V(H) \cap V(B)$, where $\mathcal{F}_a$ consists of the endpoints of $T(a)$ in $G_2^a$ and $\mathcal{F}_b$ consists of the endpoints of $T(b)$ in $G^b$.

<figure><img src="image_23.png" /><figcaption>Figure 20: Definition of $A$, $B$, and $H$ from $a$ and $b$.</figcaption></figure>

By construction, every cut of $H$ separating $\mathcal{F}_a$ and $\mathcal{F}_b$ is a cut separating $A$ and $B$ so that m-cut$(A, B) \le$ m-cut$(\mathcal{F}_a, \mathcal{F}_b)$. However, since $(T, \phi)$ is linked, m-cut$(A, B) = \min_{e \in P} w(e)$. As $a$
is an ancestor of $b$, $w(b) = w(a) = k \le \min_{e \in P} w(e)$. Hence, $k \le \text{m-cut}(\mathcal{F}_a, \mathcal{F}_b)$ and by Menger's theorem [18] applied to the associated abstract graphs, there exists a family $\mathcal{P}$ of $k$ edge-disjoint paths from $\mathcal{F}_a$ to $\mathcal{F}_b$. As $H$ is embedded, the paths are also embedded.

The family $\mathcal{P}$ may contain transverse paths, since all edges of $T(a)$ and $T(b)$ are used by these paths, the only transverse vertices are the ones for which edges around them are interlaces. Let $m$ be the number of transverse vertices of $\mathcal{F}$. A path-swap at $v$ does not affect the transversality of paths at any other vertex of $H$, unless it involves the suppression of edges from some path, in which case the number of transversal paths can only decrease at any other vertex. Hence, we can apply the sequence of path-swaps from Lemma 5.5 to reduce $m$ by one (see Figure 21 for a visual description of the process).

<figure><img src="image_24.png" /><figcaption>Figure 21: An example of a sequence of path-swapping on a graph.</figcaption></figure>

After this process, $\mathcal{P}$ is a family of edge-disjoint embedded paths connecting vertices from $\mathcal{F}_b$ to vertices of $\mathcal{F}_a$, where the first edge of each path belongs to $T(b)$ and the last one to $T(a)$, which have same size. Hence, each path starts on $G_b$, goes through the edge $x \in T(b)$ whose subdivision yields $c_x$ in $\tilde{G}^b$, $H$, then the edge $y \in T(a)$ whose subdivision yields $c_y$ in $\tilde{G}^a$ and ends on $\mathcal{F}_a$. This way, we associate to each vertex $c_x$ induced by $T(b)$, a vertex $c_y$ induced by $T(a)$, and the subpath $P_x$ of $\mathcal{P}$ starting with $x$ and ending at the vertex $c_y$ on the last one of its edge. The path $P_x$ is the image of the edge incident to $c_x$ in $\tilde{G}^b$.

By the identity, $G^b$ is obviously an embedded immersion minor of $G^a$. By construction the family $(P_x)_{x \in T(b)}$ is tangent and respects the order at their starting point in $G^b$ so that, by Lemma 3.2, $\tilde{G}^b$ is an embedded immersion of $\tilde{G}^a$, i.e., $b \prec a$. $\square$

## 5.3 Nash-Williams' argument.

A **forest** is a family or union of rooted trees (the root induces an orientation on edges which will be used for the definition of ancestor in this context). We denote by $\mathcal{E}(\mathcal{T}) = \bigcup_{T \in \mathcal{T}} \mathcal{E}(T)$ the set of edges in this forest. A **subforest** $\mathcal{F}'$ of $\mathcal{F}$ is a forest where each tree $T'$ is a subtree of $T$ which is rooted at the only incoming edge. A subtree induced by an edge $e \in \mathcal{E}(T)$ is the maximal subtree of $T$ whose root is $e$. For each edge $e \in \mathcal{E}(T)$, the set of children of $e$ is the set $\text{ch}_{\mathcal{T}}(e)$ of edges of $T$ whose tail is the head of $e$, i.e., the edges which follow $e$ for the order induced by the root.

The following is a lemma on trees where there is a quasi-order on the set of edges. The concepts behind the proof of the following proposition stem from [19] and we adapt them in a similar way as [9]. For convenience, we will prove it in a more general context than cubic trees.
**Lemma 5.7.** Lemma on trees [9, (3.1)] Let $\mathcal{T}$ be a family of trees, $n \in \mathbb{N}$ an integer, $w$ a map $\mathcal{E}(\mathcal{T}) \to \mathbb{N}$, and $\ll$ a quasi-order on $\mathcal{E}(\mathcal{T})$ with no infinite descending sequence such that for all pairs of edges $a, b$, if $a$ is an ancestor of $b$ then $b \ll a$. Then:

> If $\mathcal{E}(\mathcal{T})$ is not well-quasi-ordered by $\ll$ then, there exists an antichain $(e_n)_{n \in \mathbb{N}}$ such that
> the set $\cup_{n \in \mathbb{N}} \text{ch}_{\mathcal{T}}(e_n)$ is well-quasi-ordered by $\ll$. \hfill (S)

*Proof.* Let us assume by contraction that this lemma is false. Let $\mathcal{T}$ be a forest not satisfying this lemma, such that $w$ has minimal range and $\mathcal{E}(\mathcal{T})$ is not well-quasi-ordered by $\ll$. In particular, for each value $k$ in its range there is an infinite number of edges with image $k$ (otherwise a finite number of trees could be deleted).

Let $k$ be the minimum value of $w$ in its range. Then the set $K = w^{-1}(k)$ of edges labelled by $k$ is not well-quasi-ordered by $\ll$. Indeed, if this was the case, let us consider $\mathcal{T}' = \mathcal{T} \setminus K$, the subforest of $\mathcal{T}$ where edges labelled $k$ have been removed. By minimality of the range of $w$, $\mathcal{T}$ must satisfy property (S). Either it is well-quasi-ordered by $\ll$, which is absurd because by adding back $K$, $\mathcal{T}$ would still be well-quasi-ordered. Or, there exists an antichain $(e_n)_{n \in \mathbb{N}} \in \mathcal{E}(\mathcal{T}')^{\mathbb{N}}$ such that the set $\cup_{n \in \mathbb{N}} \text{ch}_{\mathcal{T}'}(e_n)$ is well-quasi-ordered by $\ll$. It follows that $\cup_{n \in \mathbb{N}} \text{ch}_{\mathcal{T}'}(e_n) \cup K$ is well-quasi-ordered. This last set contains $\cup_{n \in \mathbb{N}} \text{ch}_{\mathcal{T}}(e_n)$, which is hence well-quasi-ordered as well; this contradicts property (S), hence the set of edges labelled by $k$ is not well-quasi-ordered by $\ll$.

We now construct a minimal antichain $(a_n)_{n \in \mathbb{N}} \in K^{\mathbb{N}}$ with respect to the ancestry relation. Note that, in our framework, since $k$ is the minimal value taken by $w$ on $\mathcal{E}(\mathcal{T})$, if $w(e) = k$ then, every edge $f$ in the subtree induced by $e$ such that $w(f) = k$ is a successor of $e$. We proceed by induction and first choose $a_1$ such that $a_1$ is the first element of an antichain, but none of its successor is. Then if the first $k-1$ elements are fixed, we choose $a_k$ so that $a_i \not\ll a_k$ for $i < k$, $(a_i)_{1 \le i \le k}$ can be extended to an infinite antichain, and none of its successors can. Such elements exist since $K$ contains antichains, and if an element does not satisfy the successor condition, replace it by one of its successors which are in finite number since there is no infinite descending sequence.

By property (S), $\cup_{n \in \mathbb{N}} \text{ch}(a_n)$ is not well-quasi-ordered. Let $\mathcal{A}$ be the subforest of $\mathcal{T}$ induced by $(\text{ch}_{\mathcal{A}}(a_n))_{n \in \mathbb{N}}$. Since any antichain of $\mathcal{A}$ is an antichain of $\mathcal{T}$, and $\text{ch}_{\mathcal{T}}|_{\mathcal{E}(\mathcal{A})} = \text{ch}_{\mathcal{A}}$, it follows that $\mathcal{A}$ also contradicts property (S). Hence, $K \cap \mathcal{E}(\mathcal{A})$ is not well-quasi-ordered and we can find among it another antichain $(s_n)_{n \in \mathbb{N}} \in (K \cap \mathcal{E}(\mathcal{A}))^{\mathbb{N}}$.

By construction, each edge $s_n$ is the successor of exactly one edge $a_{p(n)}$. Let $N$ be such that $p(N)$ is minimal and $n > N$. Since $a_{p(n)}$ is an ancestor of $s_n$, we have $s_n \ll a_{p(n)}$. It follows that no $a_i$ satisfies $a_i \ll s_n$ for $i < p(N)$, by transitivity of $\ll$. Thus, $a_1, \dots, a_{p(N)-1}, s_N, s_{N+1}, \dots$ is an antichain, which contradicts the construction of $a_{p(N)}$ and concludes the proof. $\square$

Usually the proof of analogues of Theorem 1.2 exploits an antichain yielded by Lemma 5.7 to construct an edge $\ll$ to another in the antichain, which leads to a contradiction. That construction is the crux relying on the finiteness of the number of ways to merge two “abstract leaving graphs”. Here, our leaving graphs are much more constrained by the embedding, which modifies this part of the proof: it is harder to assemble the graphs but easier to find the ones to assemble.

*Proof of Theorem 1.2.* Let $(G_n)_{n \in \mathbb{N}}$ be a sequence of plane graphs such that the carving-width of each graph $G_n$ is bounded by $k \in \mathbb{N}$. For each $n \in \mathbb{N}$, thanks to Proposition 1.4, we choose a disc carving-decomposition $T_n$ of $G_n$ of carving-width $cw(G_n)$ and set the forest $\mathcal{T} = \cup_{n \in \mathbb{N}} T_n$. Let us assume by contradiction that $(G_n)_{n \in \mathbb{N}}$ is not well-quasi-ordered by embedded immersion.
It follows that the set of roots of $\mathcal{T}$ is an antichain for $\ll$ and $\mathcal{E}(\mathcal{T})$ is not well-quasi-ordered by $\ll$. By Lemma 5.6, if two edges $a, b$ of $\mathcal{T}$ are such that $a$ is an ancestor of $b$, then $b \ll a$. Since the number of graphs on a fixed vertex is finite and there is a finite number of embeddings of a planar graph up to isotopy, there cannot be an infinite descending sequence of graphs for $\ll$. Hence, as $w$ is bounded by $k$ on $\mathcal{E}(\mathcal{T})$, we can apply Lemma 5.7 and exhibit an antichain $(a_n)_{n \in \mathbb{N}}$ such that $\cup_{n \in \mathbb{N}} \text{ch}_{\mathcal{T}}(a_n)$ is well-quasi-ordered by $\ll$.

Since our trees are cubic, each set $\text{ch}(a_n)$ either consists of two edges, a left child $\ell_n$ and a right child $r_n$, or is empty. However, the edges incident to leaves are well-quasi-ordered since the number of leaving graphs for such edges are in finite number (they have at most $k$ edges). Hence, there is at most a finite number of edges incident to leaves in $(a_n)_{n \in \mathbb{N}}$ and each sequence of $(\ell_n)_{n \in \mathbb{N}}$, $(r_n)_{n \in \mathbb{N}}$ is infinite and well-quasi-ordered by $\ll$.

Up to extracting subsequences of $(a_i)_{i \in \mathbb{N}}$ and hereby $(\ell_n)_{n \in \mathbb{N}}$, $(r_n)_{n \in \mathbb{N}}$, we can assume that $\forall i \in \mathbb{N}, \ell_i \ll \ell_{i+1}, \forall i \in \mathbb{N}, r_i \ll r_{i+1}$, and $\forall i \in \mathbb{N}, w(\ell_i) = w(r_{i+1}), w(\ell_i) = w(r_{i+1})$, and $w(a_i) = w(a_{i+1})$ (each one of these properties may require an extraction). In other words, the sequences $(\ell_n)_{n \in \mathbb{N}}$ and $(r_n)_{n \in \mathbb{N}}$ are ascending chains, and each sequence has a unique value by $w$. For simplicity of notations, we consider a subset of the sequence $(G_n)_{n \in \mathbb{N}}$ and index it such that we can design by $G_i$ the graph of $(G_n)_{n \in \mathbb{N}}$ such that $a_i$ is an edge of a carving-decomposition of $G_i$.

We now exploit our embedded structure. Let us set $i \in \mathbb{N}$. By the disc property, there exists a Jordan curve $\gamma_{a_i}$ in the plane such that $\gamma_{a_i}$ only meets $G_i$ once on the interior of each edge of $T_i(a_i)$. Furthermore, up to switching orientation, $\gamma_{a_i}$ intersects $T_i(a_i)$. Similarly, we define $\gamma_{\ell_i}$ and $\gamma_{r_i}$, which intersect $T_i(\ell_i)$ and $T_i(r_i)$. Since our decompositions satisfy the disc property, vertices of $G_i^{\ell_i}$ and $G_i^{r_i}$ both lie on the same side of $\gamma_{a_i}$. Furthermore, it is possible to isotope $\gamma_{\ell_i}, \gamma_{r_i}$, and $\gamma_{a_i}$ so that each point of any $\gamma$ curve belongs to another one. Their union forms a $\theta$-curve as depicted in Figure 22. By comparing the endpoint in $G_i^{\ell_i}$ and the order around it, it is possible to establish a bijection between edges met along $\gamma_{\ell_i}$ with respect to $G_i^{a_i}$ and edges met along $\gamma_{\ell_i}$ with respect to $G_i^{r_i}$. This bijection can then be extended to an injection to edges met by $\theta_i$. The same arguments apply for $\theta_i$ and $\gamma_{r_i}$. In the following we will use these bijections and map to $\theta$-curves without emphasizing it.

<figure><img src="image_25.png" /><figcaption>Figure 22: Left: Definition of $\theta_i$ from $\tilde{G}_i^{a_i}$. Right: Visualisation of $\tilde{G}_i^{a_i}$ as an embedded immersion of $\tilde{G}_j^{a_j}$.</figcaption></figure>

Let us set $j > i$, then we have two embedded immersions from $\tilde{G}_i^{\ell_i}$ to $\tilde{G}_j^{\ell_j}$ and from $\tilde{G}_i^{r_i}$ to $\tilde{G}_j^{r_j}$. The sizes of cuts $|T_i(r_i)|$, $|T_i(\ell_i)|$, and $|T_i(a_i)|$ determine the sizes of $|T_i(\ell_i) \cap T_i(r_i)|$, $|T_i(a_i) \cap T_i(r_i)|$, and $|T_i(\ell_i) \cap T_i(a_i)|$. Since $|T_i(x_i)| = |T_j(x_j)|$ by construction for $x \in \{\ell, r, a\}$,
we conclude that the sizes of intersections of pairs of cuts also match between $\tilde{G}_i^i$ and $\tilde{G}_j^j$, i.e.,
$|T_i(x_i) \cap T_i(y_i)| = |T_j(x_j) \cap T_j(y_j)|$ for $x, y \in \{\ell, r, a\}^2$.

By Lemma 3.2, we have ordered immersions $\phi_\ell, \phi_r$ where the images of edges are families of tangent paths $P_{\ell,j}$ and $P_{r,j}$. For each edge $e$ in $T_j(\ell_j) \cap T_j(r_j)$, that is the edges met on the vertical part of $\theta_j$, there exists a path $p_{\ell,j}$ of the families yielded by Lemma 3.2 within $G_j^{\ell,j}$ ending with $e$. Similarly, we have a path $p_{r,j}$ within $G_j^{r,j}$ reaching the same edge so that we can merge these paths to get a path $p_e$. These paths are tangent since their inner vertices are also inner vertices in $P_{\ell,j}$ and $P_{r,j}$, they are also tangent paths in $G_j^j$, this proves that $G_i^i$ is an embedded immersion of $G_j^j$.

Then, we identify the non-merged vertices $s_x$ of $\tilde{G}_j^{\ell,j}$ with their equivalent among the remaining non-merged vertices $s_y$ of $\tilde{G}_j^{a_j}$ on the proper arc of $\theta_j$. We do similarly with the ones remaining in $\tilde{G}_j^{r_j}$. We then have edge-disjoint paths joining $G_j^{a_j}$ to vertices $s_x$ on $\partial D_{a_j}$ which respect the order around the starting vertices of $G_j^{a_j}$. By Lemma 3.2 $\tilde{G}_i^{a_i}$ is an embedded immersion of $\tilde{G}_j^{a_j}$. Hence, $a_i \prec a_j$, which is a contradiction and concludes our proof. $\square$

# 6 Embedded graph minor

The aim of this sections is to prove that plane graphs are well-quasi-ordered by embedded minor, i.e., Theorem 1.1.

A way to prove this theorem for the abstract setting is to prove that planar graphs with bounded width (either branchwidth or treewidth) are well-quasi-ordered by exploiting branch-decompositions, which is similar to what we did in Section 5. For graphs with high treewidth, it can be done by proving two properties. The first is that any plane graph can be obtained as a minor of a big enough grid [26, 20]. The second is that we can find grids of arbitrary size in a family of planar graphs with unbounded treewidth [24].

Adapting our techniques from Section 5 to prove directly that plane graphs with bounded branch-width (respectively treewidth) are well-quasi-ordered by the embedded minor relation fails due to the fact that a cut induced by a branch-decomposition (respectively tree-decomposition) is a vertex-cut, i.e., a set of vertices whose removal renders the graph disconnected. In consequence, although it is possible to prove the existence of bond-linked branch-decomposition, the cut-cycle duality of cuts produced by carving-decomposition does not readily imply the disc property. We circumvent this issue by considering an oriented version of the embedded immersion applied to the medial digraph in Section 6.1 and apply the methods that we developed earlier.

The case of unbounded width plane graphs follows from adaptations of existing theorem in the literature. First of all, it is quite convincing to see that plane graphs can be obtained as embedded minors of a grid: consider an embedding of a planar graph $G$, split vertices into trees of degree less than 4, and push each edge on a thin enough grid. Contracting back the trees and deleting the unused part of the grid is the embedded minor. Furthermore, it is already known that walls can be found as subgraph of a graph with high width, and they have few distinct embeddings in $\mathbb{R}^2$. Hence, finding embedded grids as embedded minor require little extra work.

## 6.1 Bounded branch-width

The goal of this section is to prove that plane graphs with bounded branch-width are well-quasi-ordered by embedded minors, i.e., Proposition 6.1.
<figure><img src="image_26.png" /><figcaption>Figure 23: The medial digraph DM(G) of a plane graph G, and a checkerboard colouring of its faces.</figcaption></figure>

**Proposition 6.1.** *Plane graphs with bounded branch-width are well-quasi-ordered by embedded minors.*

Similarly to last Section, with Lemma 5.1, focusing on graphs embedded in $\mathbb{S}^2$ is enough.

**Embedded minor and embedded directed immersions.** To prove Proposition 6.1, we first connect embedded minor with embedded minors via medial graphs. This idea is not new, it was already introduced in [17], but Proposition 2.4 used there was in fact not proven for the embedded setting. Our new setting, which considers embeddings carefully allow us to prove this proposition. Medial graphs were introduced by Seymour and Thomas in 1994 [27] alongside with carving-width. These two objects play a major role in this theory since the famous ratcatcher algorithm developed there, which computes the branch-width of planar graphs in polynomial time; boils down to computing the carving-width of the associated medial graph. Indeed:

**Proposition 6.2.** [*27, (7.2)]* Let G be a plane graph such that $|E(G)| \ge 2$, and M be its medial graph. Then, $2bw(G) = cw(G)$.

The **medial graph** $M(G)$ of a cellularly embedded graph $G$ is an embedded 4-regular graph on vertex set $E(G)$, where two vertex $e, e' \in V(M(G))$ are adjacent if $e, e'$ are consecutive on the boundary of some face $F$. A vertex $v_e$ of $M(G)$ can be placed on the relative interior of the embedded edge $e$, this vertex can be connected by a an arc to its neighbors in each face incident to $e$. An edge forming a self loop is incident to itself on the boundary of faces bounded by the self-loop. In addition, the two edges $e, e'$ of a face $F$ bounded by exactly two edges are considered consecutive twice, i.e., there are two edges between $v_e$ and $v_{e'}$ on $F$. Choosing the arcs connecting the vertices of $M(G)$ disjoint on each face yields an embedding of $M(G)$ associated to $G$ which is unique, see Figure 23 for a directed version of the medial graph.

Note that since $G$ is plane, $M(G)$ is plane as well. Furthermore, overlapping the two embeddings spotlights that faces of $M(G)$ are bipartitioned as in a checkerboard colouring: either the face is disjoint from $G$, or it contains exactly a vertex from $G$.

To establish a link between embedded minor and embedded immersion via graph minor, one needs to further restrain the operations allowed. Indeed, deleting an edge of the medial graph does
not translate as an embedded operation on the associated plane graph. However, performing two
embedded lifts on a vertex does. The additional restriction comes from [17]: we orient the medial
graphs and consider embedded immersion for digraph.

The **medial digraph** of a graph *G* is DM(*G*), the plane medial graph of *G* where edges along the boundary of faces containing vertices of *G* are oriented clockwise. Since these faces form a checkerboard colouring of faces of *M*(*G*), the edges along boundaries of faces of *M*(*G*) not containing vertices of *G* are oriented counter-clockwise as illustrated in Figure 23. The medial digraph DM(*G*) is then a 2-regular digraph: each vertex is incident to two incoming edges and two outgoing edges. In addition, they alternate by construction.

**Lemma 6.3.** Let *H* and *G* be two plane graphs. Then *H* is an embedded minor of *G* if and only if DM(*H*) is an embedded directed immersion of DM(*G*)

*Proof.* A **bilift** is performing two directed embedded lifts on the same vertex of (G). First not that a bilift is equivalent to deleting the matching edge of G (if the edges merged follow the faces containing V(G)), or contracting the matching edge of G (if the edges merged follow the faces not containing V(G)), as pictured in Figure 24. Deleting a non isolated vertex of G can be done by first deleting all incident edges but one, that we contract afterwards. Deleting an entire connected component of one the graph is equivalent to deleting the entire matching component.

<figure><img src="image_27.png" /><figcaption>Figure 24: Deleting or contracting a, edge of G is equivalent to 2 embedded directed lift on DM(G).</figcaption></figure>

Hence, there remains to prove that embedded directed immersions on medial digraphs can always
be realized by bilifts only and deleting connected components. This is in fact mentioned in [10,
Proposition 1.2]. Let us consider a connected medial digraph $M_1$ which is a directed embedded
immersion of a connected medial digraph $M_2$.

Since both graphs are directed 2-regular graphs in which edges alternate, vertices of $M_2$ that are images of vertices of $M_1$ are exactly the vertices not taking part in any bilift and for which no incident edges are deleted. The others take part in one of a bilift, a directed lift and two edge-deletions, or 4 edge-deletions. Hence, by following edges to be deleted in $M_2$, we identify Eulerian components (components where vertices have as much incoming edges as outgoing ones) $C_1, \dots, C_k$ which form the subgraph to delete in $M_2$.

First perform all bilifts on vertices for which all incident edges are part of paths that are images of edges of $M_1$, this does not affect the $C_i$'s. Then, let us consider a component $C_i$, it is a directed cycle by construction. Since $M_2$ is connected, $C_i$ necessarily has a vertex $v$ with exactly one incoming edge and one outgoing one. Follow this cycle starting at $v$ and perform the appropriate embedded directed lift. After this, $C_i$ is a self-loop at $v$. Performing the proper bilift on $v$ merges it with the two other edges incident to $v$: $C_i$ was "deleted" with embedded directed lifts only. After all components were removed via this process, no vertices of edge to delete remain, and all vertices of $M_2$ are of degree 4, $M_2$ is now equivalent to $M_1$ (see Figure 25 for example). All vertices which are not images of vertices of $M_1$ where part of two embedded direct lifts. □

Thus, by Lemma 6.3 and Proposition 6.2, proving Proposition 6.1 boils down to proving:
<figure><img src="image_28.png" /><figcaption>Figure 25: Embedded directed immersions in medial graphs can be realized by bilifts.</figcaption></figure>

**Proposition 6.4.** *Plane medial digraphs are well-quasi ordered by embedded directed immersion.*

To prove this we exploit discs decompositions of Section 5, and follow the same proof method, i.e., a Nash-Williams’ argument on the order put on edges of disc carving decompositions. In the following we essentially redefine this order and reprove Lemma 5.6 and Theorem 1.2 in this context.

**Order on edges.** The size of a cut in the directed and undirected context is the same, as well as satisfying the disc property. A disc carving decomposition for a graph $M(G)$ is also a disc carving decomposition of its directed version $DM(G)$.

Let $(G_n)_{n \in \mathbb{N}}$ be a family of plane medial digraphs. Thanks to Proposition 1.4, for all $n \in \mathbb{N}$, there exists $T_n$ a disc carving-decomposition of $G_n$ that we can assume rooted at some unlabelled edge $r(T_n)$. We define $\mathcal{T} = \bigcup_{n \in \mathbb{N}} T_n$ as the forest made of all the trees $T_n$.

Let $G$ be a plane digraph. For each $e \in E(T)$, the **leaving digraph** $\tilde{G}^e$, is the directed version of the leaving graph defined in Section 5: by the disc property there exist a disc $D_e$ intersecting $G$ on $G^e \cup T(e)$ which intersects each edge of $T(e)$ once on $\partial D_e$. We subdivide each edge $f$ of $T(e)$ at the place of intersection with $\partial D_e$ with a vertex $s_x$. The embedded digraph induced by $V(G^e) \cup_{x \in T(e)} \{s_x\}$ on $D_e$ is $\tilde{G}^e$, see Figure 26 for an example. It is a digraph embedded on $D_e$ such that vertices on the inside of $D_e$ are 2-regular and edges around them alternate, and vertices on the boundary have only one incident edge.

We define a quasi-order on the set $\mathcal{E} = \cup_{T \in \mathcal{T}} E(T)$ of all edges of $\mathcal{T}$: for $e, f \in \mathcal{E}^2$, $e \preceq f$ if $\tilde{G}^e$ is an embedded directed immersion of $\tilde{G}^f$ and the image of $(s_x)_{x \in T(e)}$ in the embedded immersion is $(s_x)_{x \in T(f)}$.

We now prove the equivalent of Lemma 5.6 for medial digraphs, this relies essentially on a version of Menger’s theorem for digraphs.

**Lemma 6.5.** Let $G$ be a plane medial digraph, $(T, \phi)$ a disc carving-decomposition of $G$, and $a, b \in E(T)^2$ such that $a$ is an ancestor of $b$. Then $b \preceq a$.

*Proof.* Let $D_e$ be the disc associated to an edge $e$ of $T$, i.e., the component delimited by $\gamma_e$ containing $G^e$. The curve $\gamma_e$ intersects incoming edges, i.e., edges of $T(e)$ with head in $D_e$ and outgoing one when their tail is there instead. In between two consecutive edges, $\gamma$ lies on the face bounded by these two edges. However, since they belong to the boundary of the same face, which are oriented consistently in that regard by definition of plane medial digraph, one of them is incoming and the other one is outgoing. Hence, edges met by $\gamma$ alternate (see $\gamma_e$ on Figure 26 for example). It follows
<figure><img src="image_29.png" /><figcaption>Figure 26: How to obtain $\tilde{G}^e$ from $G$, the vertices $(s_x)_{e \in T(e)}$ are in green on $\partial D_e$.</figcaption></figure>

that cuts of $G$ are of even size, and contain as many incoming edges with respect to $T(e)$ as outgoing ones.

The $\prec$ relation between $b$ and $a$ can be defined since the carving-decomposition satisfies the disc property. We denote $2k = w(a) = w(b)$. Let assume that $G_1^a = G^a$ so that $A = V(G_2^a)$ and $B = V(G^b)$ with respect to the linked definition of $A$ and $B$. Let us call $P$ the minimal path of $T$ containing both $a$ and $b$. We define $H = G \setminus E(G_2^a) \cup E(G^b)$, in other words, the edges of $G$ between $T(a)$ and $T(b)$ (where $T(a)$ and $T(b)$ are included). By construction, there are two disjoint families $\mathcal{F}_a = V(H) \cap V(A)$ and $\mathcal{F}_b = V(H) \cap V(B)$, where $\mathcal{F}_a$ consists of the endpoints of $T(a)$ in $G_2^a$ and $\mathcal{F}_b$ consists of the endpoints of $T(b)$ in $G^b$.

<figure><img src="image_30.png" /><figcaption>Figure 27: Definition of $\mathcal{F}_a$, $\mathcal{F}_b$, and $H$ from $a$ and $b$.</figcaption></figure>

By construction, every cut of $H$ separating $\mathcal{F}_a$ and $\mathcal{F}_b$ is a cut separating $A$ and $B$ so that m-cut($A, B$) $\le$ m-cut($\mathcal{F}_a, \mathcal{F}_b$). However, since $(T, \phi)$ is linked, m-cut($A, B$) = min$_{e \in P}$ w(e). As $a$ is
an ancestor of $b$, $w(b) = w(a) = 2k \le \min_{e \in P} w(e)$. Hence, $2k \le \text{m-cut}(\mathcal{F}_a, \mathcal{F}_b)$ and by Menger's theorem on digraphs, there exists a family $P$ of $2k$ edge-disjoint paths between $\mathcal{F}_a$ and $\mathcal{F}_b$ in the abstract digraph associated to $G$. Since all cuts have as many incoming edges as outgoing ones, we have in fact $k$ paths from $\mathcal{F}_a$ to $\mathcal{F}_b$ and $k$ paths from $\mathcal{F}_b$ to $\mathcal{F}_a$.

Since $G$ is embedded, $P$ is a family of edge-disjoint direct embedded paths connecting vertices from $\mathcal{F}_b$ and $\mathcal{F}_a$ where the first edge of each path belongs to one of $T(b)$ and $T(a)$ and the last one belongs to the other cut. Hence, each path starts in $\mathcal{F}_i$, goes through the edge $x \in T(i)$ whose subdivision yields $c_x$ in $\tilde{G}^i$, $H$, then the edge $y \in T(j)$ whose subdivision yields $c_y$ in $\tilde{G}^j$ and ends on $\mathcal{F}_j$ for $\{i, j\} = \{a, b\}$. This way, we associate to each vertex $c_x$ incident to an incoming edge, a vertex $c_y$ induced by $T(a)$, and the subpath $P_x$ of $P$ starting with $x$ and ending at the vertex $c_y$ on the last one of its edge. We associate to each vertex $c_x$ incident to an outgoing edge, a vertex $c_y$ induced by $T(a)$, and the subpath $P_x$ of $P$ starting with $c_y$ and ending with the edge $x$.

By the identity, $G^b$ is obviously an embedded immersion minor of $G^a$. By definition of medial digraph the family of directed path $(P_x)_{x \in T(b)}$ is tangent and by construction, they respect the order at their starting point in $G^b$ so that, by Lemma 3.3 $\tilde{G}^b$ is an embedded directed immersion of $\tilde{G}^a$, i.e., $b \prec a$. $\square$

**Nash-Williams' argument** The proof of Proposition 6.4 is the very same as the proof of Theorem 1.2 with directed paths which are handled through Lemma 6.5. Again, gluing leaving digraphs is easier than in the abstract case since the embedding is much more constraint.

*Proof of Proposition 6.4.* Let $(G_n)_{n \in \mathbb{N}}$ be a sequence of medial digraphs such that their carving-width is bounded by $k \in \mathbb{N}$. For each $n \in \mathbb{N}$, thanks to Proposition 1.4, we choose a disc carving-decomposition $T_n$ of $G_n$ of carving-width $cw(G_n)$ and set the forest $\mathcal{T} = \cup_{n \in \mathbb{N}} T_n$. Let us assume by contradiction that $(G_n)_{n \in \mathbb{N}}$ is not well-quasi-ordered by embedded directed immersion.

Hence, the set of roots of $\mathcal{T}$ is an antichain for $\prec$ and $\mathcal{E}(\mathcal{T})$ is not well-quasi-ordered by $\prec$. By Lemma 6.5, for a pair of edges of $\mathcal{T}$ if an edge $a$ is an ancestor of $b$, then $b \prec a$. Since the number of graphs on a fixed vertex is finite and there is a finite number of embeddings of a planar graph up to isotopy, there cannot be an infinite descending sequence of graphs for $\prec$. Hence, as $w$ is bounded by $k$ on $\mathcal{E}(\mathcal{T})$, we can apply Lemma 5.7 and exhibit an antichain $(a_n)_{n \in \mathbb{N}}$ such that $\cup_{n \in \mathbb{N}} \text{ch}_{\mathcal{T}}(a_n)$ is well-quasi-ordered by $\prec$.

Since our trees are cubic, each set $\text{ch}(a_n)$ either consists of two edges, a left child $\ell_n$ and a right child $r_n$, or is empty. However, the edges incident to leaves are well-quasi-ordered since the number of leaving graphs for such edges are in finite number (they have at most $k$ edges). Hence, there is at most a finite number of edges incident to leaves in $(a_n)_{n \in \mathbb{N}}$ and each sequence of $(\ell_n)_{n \in \mathbb{N}}$, $(r_n)_{n \in \mathbb{N}}$ is infinite and well-quasi-ordered by $\prec$.

Up to extracting subsequences of $(a_i)_{i \in \mathbb{N}}$ and hereby $(\ell_n)_{n \in \mathbb{N}}$, $(r_n)_{n \in \mathbb{N}}$, we can assume that $\forall i \in \mathbb{N}, \ell_i \prec \ell_{i+1}, \forall i \in \mathbb{N}, r_i \prec r_{i+1}$, and $\forall i \in \mathbb{N}, w(\ell_i) = w(r_{i+1}), w(\ell_i) = w(r_{i+1})$, and $w(a_i) = w(a_{i+1})$ (each one of these properties may require an extraction). In other words, the sequences $(\ell_n)_{n \in \mathbb{N}}$ and $(r_n)_{n \in \mathbb{N}}$ are ascending chains, and each sequence has a unique value by $w$. For simplicity of notations, we consider a subset of the sequence $(G_n)_{n \in \mathbb{N}}$ and index it such that we can design by $G_i$ the graph of $(G_n)_{n \in \mathbb{N}}$ such that $a_i$ is an edge of a carving-decomposition of $G_i$.

We now exploit our embedded structure. Let us set $i \in \mathbb{N}$. By the disc property, there exists a Jordan curve $\gamma_{a_i}$ in the plane such that $\gamma_{a_i}$ only meets $G_i$ once on the interior of each edge of $T_i(a_i)$. Furthermore, up to switching orientation, $\gamma_{a_i}$ intersects $T_i(a_i)$. Similarly, we define $\gamma_{\ell_i}$ and $\gamma_{r_i}$, which intersect $T_i(\ell_i)$ and $T_i(r_i)$. Since our decompositions satisfy the disc property, vertices
of $G_i^{\ell_i}$ and $G_i^{r_i}$ both lie on the same side of $\gamma_{a_i}$. Furthermore, it is possible to isotope $\gamma_{\ell_i}$, $\gamma_{r_i}$, and $\gamma_{a_i}$ so that each point of any $\gamma$ curve belongs to another one. Their union forms a $\theta$-curve as depicted in Figure 28. By comparing the endpoint in $G_i^{\ell_i}$ and the order around it, it is possible to establish a bijection between edges met along $\gamma_{\ell_i}$ with respect to $G^{a_i}$ and edges met along $\gamma_{\ell_i}$ with respect to $G^{a_i}$. This bijection can then be extended to an injection to edges met by $\theta_i$. The same arguments apply for $\theta_i$ and $\gamma_{r_i}$. In the following we will use these bijection and map to $\theta$-curves without emphasising it.

<figure><img src="image_31.png" /><figcaption>Figure 28: Left: Definition of $\theta_i$ from $\tilde{G}_i^{a_i}$. Right: Visualisation of $\tilde{G}_i^{a_i}$ as an embedded immersion of $\tilde{G}_j^{a_j}$.</figcaption></figure>

Let us set $j > i$, then we have two embedded immersions from $\tilde{G}_i^{\ell_i}$ to $\tilde{G}_j^{\ell_j}$ and from $\tilde{G}_i^{r_i}$ to $\tilde{G}_j^{r_j}$. The sizes of cuts $|T_i(r_i)|$, $|T_i(\ell_i)|$, and $|T_i(a_i)|$ determine the sizes of $|T_i(\ell_i) \cap T_i(r_i)|$, $|T_i(a_i) \cap T_i(r_i)|$, and $|T_i(\ell_i) \cap T_i(a_i)|$. Since $|T_i(x_i)| = |T_j(x_j)|$ by construction for $x \in \{\ell, r, a\}$, we conclude that the sizes of intersections of pairs of cuts also match between $\tilde{G}_i^i$ and $\tilde{G}_j^j$: $|T_i(x_i) \cap T_i(y_i)| = |T_j(x_j) \cap T_j(y_j)|$ for $x, y \in \{\ell, r, a\}^2$.

By Lemma 3.3, we have ordered immersions $\phi_\ell, \phi_r$ where the images of edges are families of tangent directed paths $P_{\ell,j}$ and $P_{r,j}$. For each edge $e$ in $T_j(\ell_j) \cap T_j(r_j)$, that is the edges met on the vertical part of $\theta_j$, there exists a path $p_{\ell,j}$ of the families yielded by Lemma 3.3 within $G_j^{\ell_j}$ ending with $e$. Similarly, we have a path $p_{r,j}$ within $G_j^{r_j}$ reaching the same edge so that we can merge these paths to get a path $p_e$. Indeed, a path leaving $D_{\ell_j}$ at edge $p$ is a path incoming $D_{r_j}$ and vice versa, so we can merge them.

These directed paths are tangent since their inner vertices are also inner vertices in $P_{\ell,j}$ and $P_{r,j}$, they are also tangent paths in $G_j^j$, this proves that $G_i^i$ is an embedded immersion of $G_j^j$. Then, we identify the non-merged vertices $s_x$ of $\tilde{G}_j^{\ell_j}$ with their equivalent among the remaining non-merged vertices $s_y$ of $\tilde{G}_j^{a_j}$ on the proper arc of $\theta_j$. We do similarly with the ones remaining in $\tilde{G}_j^{r_j}$. We then have edge-disjoint directed paths joining $G_j^{a_j}$ to vertices $s_x$ on $\partial D_{a_j}$ which respect the order around the starting vertices of $G_j^{a_j}$. By Lemma 3.3 $\tilde{G}_i^{a_i}$ is an embedded directed immersion of $\tilde{G}_j^{a_j}$. Hence, $a_i \prec a_j$, which is a contradiction and concludes our proof. $\square$

## 6.2 Unbounded branch-width

The aim of this sections is to prove that plane graphs with unbounded branch-width are well-quasi-ordered by embedded minor. We do so by proving first that any plane graph can be obtained as
embedded minor of a big enough embedded grid: Proposition 6.6. Then, we prove that if the graphs have unbounded branch-width, we can always find an embedded grid as embedded minor of a graph of the family via Proposition 6.7.

So for a family of plane graphs, either the branch-width of graphs of this family is bounded and handled by Proposition 6.1, or it is not bounded and arbitrarily large grids can be found as embedded minors of members of the family by Proposition 6.7. Hence, any graph of the family is in relation with a graph of the family with high enough branch-width by Proposition 6.6.

**Proposition 6.6.** Let $G$ be a plane graph. Then, there exists $n \in \mathbb{N}$ such that $G$ is an embedded minor of the $n \times n$ plane grid.

**Proposition 6.7.** For all $n \in \mathbb{N}$, there exists $k \in \mathbb{N}$ such that if $G$ is a plane graph with branch-width at least $k$, then the $n \times n$ plane grid $G_{n,n}$ is an embedded minor of $G$.

As said before, everything needed here is fairly intuitive and already proven elsewhere, we need only check that the minor defined there can be realized as embedded minor.

**Finding a grid as embedded minor.** The abstract grid $n \times m$ is the graph with $nm$ vertices $v_{i,j}$ where $(v_{i,j}, v_{i',j'})$ is an edge of this grid if and only if $|i' - i| + |j - j'| = 1$. The abstract grid has a unique embedding in $\mathbb{S}^2$:

**Lemma 6.8.** For all $n \in \mathbb{N}$, there is a unique embedding of $n \times n$ grid in $\mathbb{S}^2$.

*Proof.* The proof is trivial for $n = 0$ and $n = 1$. Let $G$ be the abstract grid of size $n \times n$. If $n \ge 2$, for $1 \le i, j < n$, let $C_{i,j}$ be the cycle $G[\{v_{i,j}, v_{i+1,j}, v_{i+1,j+1}, v_{i,j+1}\}]$ and $C$ be the cycle $G[\{v_{i,j}|\{i,j\} \cap \{1, n\} \ne \emptyset\}]$.

Let us assume by contradiction that there exists an embedding $\tilde{G}$ of $G$ such that $C_{i,j}$ is not the boundary of a face of $\tilde{G}$. Since $C_{i,j}$ is a cycle which is not the boundary of a face, there should be at least a vertex on both sides of its embedding (it cannot be only an edge). Hence, $G \setminus C_{i,j}$ is disconnected since there is no path connecting the vertices on different sides of $C_{i,j}$. This is absurd since $G \setminus C_{i,j}$ is connected for $n > 2$.

Similarly, the graph $G \setminus C$ is an $(n-2) \times (n-2)$ grid, which is connected so that any embedding of $G$ has $C$ as the boundary of a face.

Each edge is present twice in $C \cup_{1 \le i,j < n} C_{i,j}$ so that all faces of every embedding of $G$ are the same: $G$ has a unique embedding on $\mathbb{S}^2$. $\square$

A **wall** is similar to a grid except that vertical edges are placed on staggered rows instead of being aligned, it is a 3-regular graph. Formally, the wall of **height** $n$ for $n$ even is defined as the graph on vertices $\{v_{i,j}|1 \le i \le n+1, 1 \le j \le 2n+2, (i,j) \notin \{(1,2n+2), (n+1,1)\}\}$ where vertices $v_{i,j}$ and $v_{i',j'}$ are adjacent if $i = i'$ and $|j - j'| = 1$ or if $j = j'$, $|i - i'| = 1$, and $\min(i, i') + j$ is even. For $i, j$ such that $i + j$ is even and $i < n, j \le 2n$, the **brick-cycle** at $v_{i,j}$ is the cycle $v_{i,j} \to v_{i,j+1} \to v_{i,j+2} \to v_{i+1,j+2} \to v_{i+1,j+1} \to v_{i+1,j} \to v_{i,j}$. The same proof as Lemma 6.8 shows that brick-cycles are necessarily boundaries of faces of any embedding of a wall in $\mathbb{S}^2$, as well as a remaining cycle bounding a face of high degree.

The **plane grid** $G_{n,n}$ is the embedding of the abstract $n \times n$ grid where the high-degree face of the embedding is the unbounded face of the embedding. Similarly, the **plane wall** $W_n$ of height $n$ is the embedding of the wall of height $n$ where the high-degree face of the embedding is the unbounded face of the embedding. See for example the plane grid and the plane wall on Figure 29. A **subdivided wall** is a wall on which any number of edge subdivisions has been done.
<figure><img src="image_32.png" /><figcaption>Figure 29: Left: the plane grid $G_{7,7}$. Right: the plane wall $W_6$.</figcaption></figure>

It is quite well-known that branch-width is equivalent to tree-width [23, (5.1)], in fact for any graph $G$, bw($G$) < tw($G$). Hence we will be able to use the following proposition which results from [21] and its formulated as such in [3]:

**Proposition 6.9.** [3, (1.3)] For all $n \ge 2$ there exists $k$ such that every graph with tree-width at least $k$ contains a subdivided wall of height $h$.

It remains to explain of to get a plane grid out of such subdivided wall obtained as a subgraph.

*Proof.* *Proof of Proposition 6.7* By Proposition 6.7 and equivalence between branchwidth and treewidth, there exists $k$ such that if $G$ has branch-width $k$ or more, then $G$ contains a subdivision $W$ of the Wall of height $2n$ as a subgraph. We delete every edge of $G \setminus W$ so that we end up with an embedding of $W$. Then, we perform embedded contraction to have an embedding of the wall instead of one of the subdivided wall. Then, we perform embedded contractions on each edge $(v_{i,2j}, v_{i,2j+1})$ for $1 \le i \le n+1$ and $1 \le j \le n+1$, so that $G$ is now an embedded grid of size $2n \times 2n$.

By Lemma 6.8, the embedding of $G$ is the unique embedding of $G$ on $\mathbb{S}^2$ where one face $F$ has been chosen as the unbounded face. If $F$ is the high degree face of $G$, the proof is done. Otherwise, if $F$ is incident to $v_{i,j}$ and $v_{i+1,j+1}$, then the 4 quarters $G[\{v_{i',j'}|1 \le i' \le i, 1 \le j' \le j\}]$, $G[\{v_{i',j'}|i < i' \le 2n, 1 \le j' \le j\}]$, $G[\{v_{i',j'}|1 \le i' \le i, j < j' \le 2n\}]$, and $G[\{v_{i',j'}|i < i' \le 2n, j < j' \le 2n\}]$ are plane grids as illustrated in Figure 30.

<figure><img src="image_33.png" /><figcaption>Figure 30: The 5 × 5 grid embedded in $\mathbb{S}^2$, and its embedding in $\mathbb{R}^2$ where the chosen unbounded face is the face of $\mathbb{S}^2$ containing the blue dot.</figcaption></figure>

Then, the quarter containing the more vertices contains the plane grid $G_{n,n}$, removing everything outside of is the final step to obtain $G_{n,n}$ as embedded minor of $G$. $\square$
**Embedded minor in a plane grid.** We detail here a construction of [20] and remark that it is well adapted for embedded minors we claim no novelty for neither the methods nor the constructions.

**Lemma 6.10.** [20, (1.3)] Let $H$ be a simple planar graph embedded in $\mathbb{S}^2$ with $n$ vertices, then $H$ is an embedded minor of the unique embedding of $G_{n,n}$ in the sphere.

*Proof.* We detail the construction of [20]. One can first add edges to $H$ so that $H$ is triangulated, i.e., each face has degree 3. Such edges can be deleted in the end after all the contraction operations. Let us first chose an Hamiltonian cycle $C$ of $H$, i.e., a cycle $C$ passing exactly through each vertex of $H$. Let us number these vertices $\{v_1, \dots, v_n\}$ by picking a first one and following the order along $C$. Since $V(C) = V(H)$, and $C$ is embedded, every edge of $H$ is either on the bounded face $A$ of $C$, the unbounded face $B$ of $C$, or is an edge of $C$. Let us define $H_A$ and $H_B$, the subgraphs induced by $A \cup C$ and $B \cup C$ respectively, i.e., $H_A = H \cap (C \cup A)$ and $H_B = H \cap (C \cup B)$.

Set $G = G_{n,n}$, the $n \times n$ plane grid. Let us define subgraphs of $G$ thanks to the quantities:

$$ 
\left\{ 
\begin{array}{l}
\text{For } 1 < k < n, \quad i(k) = \min\{1 \le i \le n | (v_k, v_i) \in E(H_A)\} \\
\text{For } 1 < k < n, \quad j(k) = \min\{1 \le j \le n | (v_k, v_j) \in E(H_B)\} \\
\text{For } 1 < k < n, \quad j'(k) = \max\{1 \le j \le n | (v_k, v_j) \in E(H_A)\} \\
\text{For } 1 < k < n, \quad i'(k) = \max\{1 \le i \le n | (v_k, v_j) \in E(H_B)\}
\end{array}
\right. 
$$

Then, for $1 < k < n$, $X_k = G[\{v_{i,k}|i(k) < i < i'(k)\} \cup \{v_{k,j}|j(k) < j < j'(k)\}]$, $X_1 = G[\{v_{i,1}|1 \le i < n\} \cup \{v_{1,j}|1 \le j < n\}]$, and $X_n = G[\{v_{i,n}|1 \le i \le n\} \cup \{v_{n,j}|1 \le j \le n\}]$. See each black component centred at $v_{k,k}$ in Figure 31 for illustration.

<figure><img src="image_34.png" /><figcaption>Figure 31: Construction of the embedding of a plane Hamiltonian graph.</figcaption></figure>

It follows directly from the definitions that each $X_i$ contains $v_{i,i}$. Furthermore, $X_k$ crosses $X_\ell$ with $k < \ell$ if and only if $j'(k) > i(\ell)$ or $i'(k) > j(\ell)$. However, this would imply the existence of edges crossing themselves in $A$ and $B$ respectively, which is absurd since the graph is embedded. Hence the $X_i$'s are disjoint (they are disjoint from $X_1$ and $X_n$ by definition).

If an edge $(k, \ell)$ with $k < \ell$ exists in $A$, then $k \le j'(\ell)$ and $i(\ell) \le k$. Since $H$ is triangulated, one of these inequalities must be strict. Indeed, the faces incident to $(k, \ell)$ are bounded by another edge with either $k$ or $\ell$ as an endpoint and one of these edges will imply that $i(\ell) < k$ or $k < j'(\ell)$. It follows that one of $(v_{k,\ell-1}, v_{k,\ell})$ or $(v_{k,\ell}, v_{k+1,\ell})$ is incident to both $X_k$ and $X_\ell$. Furthermore, $H$
is simple so that these edges cannot appear between $k$ and $k+1$. Hence such edges are to the right of the boundary of the diagonal faces $v_{i,i}, v_{i+1,i}, v_{i+1,i+1}, v_{i,i+1}$, of $G_{n,n}$. Similarly, if an edge $(k, \ell)$ with $k < \ell$ exists in $B$, then one of $(v_{\ell,k+1}, v_{k,\ell})$ or $(v_{\ell,k-1}, v_{\ell,k})$ is incident to both $X_k$ and $X_\ell$ on the left of the diagonal faces of $G_{n,n}$ (see Figure 31 for example).

Similar arguments prove that we can always connect $X_i$ and $X_{i+1}$ for $i < n$ on the boundary of diagonal faces. By joining $X_n$ and $X_1$ with $(v_{1,n-1}, v_{1,n})$, we enclose all edges stemming from $A$ by the cycle stemming from $H$ and the sets $X_i$. In addition, edges of $B$ lie outside of this cycle. Hence, by deleting all unused edges of $G_{n,n}$ and contracting all sets $X_i$ to vertices, we obtain an embedding of $H$ with all edges on the proper side of $C$, and in the proper order by construction (they appear in the proper order along each $X_i$). Hence, $H$ is an embedded minor of $G_{n,n}$. $\square$

*Proof*. Proof of Proposition 6.6 The construction of Lemma 6.10 can be translated to the context of embedding in $\mathbb{R}^2$ but then, the unbounded face of the embedded minor is the one incident to the edge (1, n). Hence, if $H$ is a plane Hamiltonian graph with an edge of a Hamiltonian cycle incident to the unbounded face, we know that it is an embedded minor of a plane grid. In fact, this is easy to reduce any plane Hamiltonian graph to this case by replacing a vertex incident to the unbounded face by an edge taking part in the Hamiltonian cycle. And preserve the property when the graph is triangulated.

Hence, there remains to show that a plane graph $G$ can be obtained as an embedded minor of a Hamiltonian plane graph. Again, this is explained in [20]. Whitney's theorem [28] ensures that if a simple triangulated graph has no separating triangle, then it is Hamiltonian. There is a finite number of them; subdividing an edge of such triangle and connecting the newly created vertex to the two non-neighboring vertices of incident faces (see Figure 32) reduces the number of separating triangles by at least one. A finite number of such operation allows to remove all separating triangles and thus obtain a triangulated Hamiltonian graph. These operation can be reversed by edge deletion and contraction so that $G$ is an embedded minor of this graph.

<figure><img src="image_35.png" /><figcaption>Figure 32: Removing a separating triangle.</figcaption></figure>

Finally, if $G$ is non-simple, subdivide it enough so that it becomes simple before applying the constructions above. This concludes this proof. $\square$

**Acknowledgements.** This project was supported by the ANR project AlgoKnot: ANR-20-CE48-0007. Corentin Lunel was partially supported by the GAČR grant 25-16847S. The authors want to thank Pierre Dehornoy and Arnaud de Mesmay for introducing them to this problem.

## References

[1] Sebastian Baader and Pierre Dehornoy. Minor theory for surfaces and divides of maximal signature. 2012. URL: https://arxiv.org/abs/1211.7348.
[2] Dario Cavallaro, Ken ichi Kawarabayashi, and Stephan Kreutzer. Well-quasi-ordering eulerian digraphs embeddable in surfaces by strong immersion, 2025. URL: https://arxiv.org/abs/2509.26260.

[3] M. Chudnovsky, Zdeněk Dvorák, Tereza Klimošová, and Paul D. Seymour. Immersion in four-edge-connected graphs. *J. Comb. Theory B*, 116:208–218, 2013.

[4] Pierre Dehornoy, Corentin Lunel, and Arnaud de Mesmay. Hopf arborescent links, minor theory, and decidability of the genus defect. *Proceedings of the 40th International Symposium on Computational Geometry (SoCG 204, to appear)*, 2024.

[5] Matt Devos, Zdeněk Dvořák, Jacob Fox, Jessica McDonald, Bojan Mohar, and Diego Scheide. A minimum degree condition forcing complete graph immersion. *Combinatorica*, 34(3):279–298, February 2014.

[6] Reinhard Diestel. *Graph theory*. Number 173 in Graduate texts in mathematics. Springer, New York, 5th edition, 2016.

[7] Zdeněk Dvořák and Tereza Klimošová. Strong immersions and maximum degree. *SIAM Journal on Discrete Mathematics*, 28(1):177–187, January 2014.

[8] Zdeněk Dvořák and Paul Wollan. A structure theorem for strong immersions. *Journal of Graph Theory*, 83(2):152–163, September 2015.

[9] James F. Geelen, A.M.H. Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. *J. Comb. Theory Ser. B*, 84(2):270–290, 2002.

[10] Stefan Hannie. *2-regular Digraphs on Surfaces*. PhD thesis, Simon Fraser University, 2018.

[11] Kristóf Huszár and Jonathan Spreer. On the width of complicated JSJ decompositions. In Erin W. Chambers and Joachim Gudmundsson, editors, *39th International Symposium on Computational Geometry, SoCG 2023, Dallas, Texas, USA, June 12-15, 2023*, volume 258 of *LIPIcs*, pages 42:1–42:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.

[12] Kristóf Huszár, Jonathan Spreer, and Uli Wagner. On the treewidth of triangulated 3-manifolds. In Bettina Speckmann and Csaba D. Tóth, editors, *34th International Symposium on Computational Geometry, SoCG 2018, Budapest, Hungary, June 11-14, 2018*, volume 99 of *LIPIcs*, pages 46:1–46:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.

[13] Camille Jordan. *Cours d'analyse de l'École Polytechnique (in french)*. 1887.

[14] Corentin Lunel and Arnaud de Mesmay. A structural approach to tree decompositions of knots and spatial graphs. In *Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)*, volume 258 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 50:1–50:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.

[15] Clément Maria and Jessica Purcell. Treewidth, crushing and hyperbolic volume. *Algebraic & Geometric Topology*, 19(5):2625–2652, 2019.

[16] Dániel Marx and Paul Wollan. Immersions in highly edge connected graphs. *SIAM Journal on Discrete Mathematics*, 28(1):503–520, 2014.
[17] Carolina Medina, Bojan Mohar, and Gelasio Salazar. Well-quasi-order of plane minors and an application to link diagrams, 2019. arXiv:1905.01830.

[18] Karl Menger. Zur allgemeinen kurventheorie. *Fundamenta Mathematicae*, 10:96–115.

[19] C. St. J. A. Nash-Williams. On well-quasi-ordering finite trees. *Mathematical Proceedings of the Cambridge Philosophical Society*, 59(4):833–835, 1963.

[20] N. Robertson, P. Seymour, and R. Thomas. Quickly excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 62(2):323–348, 1994.

[21] Neil Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41(1):92–114, August 1986.

[22] Neil Robertson and P. D. Seymour. Graph minors. IV. tree-width and well-quasi-ordering. *Journal of Combinatorial Theory, Series B*, 48(2):227–254, 1990.

[23] Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. *Journal of Combinatorial Theory, Series B*, 52(2):153–190, July 1991.

[24] Neil Robertson and Paul D. Seymour. Graph minors. XI. Circuits on a Surface. *Journal of Combinatorial Theory. Series B*, 60(1):72–106, 1994.

[25] Neil Robertson and Paul D. Seymour. Graph minors. XXIII. Nash-Williams’ immersion conjecture. *Journal of Combinatorial Theory, Series B*, 100(2):181–205, 2010.

[26] Neil Robertson and P.D Seymour. Graph minors. VII. disjoint paths on a surface. *Journal of Combinatorial Theory, Series B*, 45(2):212–254, 1988.

[27] Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. *Combinatorica*, 14(2):217–241, 1994.

[28] Hassler Whitney. A theorem on graphs. *The Annals of Mathematics*, 1931.