Masaryk University, Brno, Czech
republichlineny@fi.muni.czhttps://orcid.org/0000-0003-2125-1514 Masaryk
University, Brno, Czech
republic484988@mail.muni.czhttps://orcid.org/0000-0001-9585-2553 Petr Hliněný
and Jan Jedelský Supported by the Czech Science Foundation, project no.
20-04567S. [500]Mathematics of computing Graph theory

# Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite
Planar

Petr Hliněný  Jan Jedelský

###### Abstract

The structural parameter twin-width was introduced by Bonnet et al. in [FOCS
2020], and already this first paper included an asymptotic argument bounding
the twin-width of planar graphs by a non-explicit constant. Quite recently, we
have seen first small explicit upper bounds of $183$ by Jacob and Pilipczuk
[arXiv, January 2022, also WG’22], $583$ by Bonnet et al. [arXiv, February
2022], of $37$ by Bekos et al. [arXiv, April 2022], and of $9$ by the first
author [arXiv, June 2022]. We further elaborate on the approach used in the
last paper and improve the upper bound to $8$. This is already very close to
the currently best lower bound of $7$ by Král’ and Lamaison [arXiv, September
2022]. We some of the new ideas, we also significantly simplify the previous
proof of the first author [arXiv, August 2022] that the twin-width of
bipartite planar graphs is at most $6$.

###### keywords:

twin-width, planar graph

##  1 Introduction

Twin-width is a new structural width measure of graphs introduced in 2020 by
Bonnet, Kim, Thomassé and Watrigant [2].

Consider only simple graphs in the coming definition.111In general, the
concept of twin-width is defined for binary relational structures of a finite
signature, and so one may either define the twin-width of a multigraph as the
twin-width of its simplification, or allow only bounded multiplicities of
edges and use the more general matrix definition of twin-width. A _trigraph_
is a simple graph $G$ in which some edges are marked as red, and with respect
to the red edges only, we naturally speak about _red neighbours_ and _red
degree_ in $G$. However, when speaking about edges and neighbours without
further specification, we count both ordinary and red edges and neighbours.
The edges of $G$ which are not red are sometimes called (and depicted) black
for distinction. For a pair of (possibly not adjacent) vertices
$x_{1},x_{2}\in V(G)$, we define a _contraction_ of the pair $x_{1},x_{2}$ as
the operation creating a trigraph $G^{\prime}$ which is the same as $G$ except
that $x_{1},x_{2}$ are replaced with a new vertex $x_{0}$ (said to stem from
$x_{1},x_{2}$) such that:

  * •

the full neighbourhood of $x_{0}$ in $G^{\prime}$ (i.e., including the red
neighbours), denoted by $N_{G^{\prime}}(x_{0})$, equals the union of the
neighbourhoods of $x_{1}$ and $x_{2}$ in $G$ except $x_{1},x_{2}$ themselves,
that is, $N_{G^{\prime}}(x_{0})=(N_{G}(x_{1})\cup
N_{G}(x_{2}))\setminus\\{x_{1},x_{2}\\}$, and

  * •

the red neighbours of $x_{0}$, denoted by $N_{G^{\prime}}^{r}(x_{0})$, inherit
all red neighbours of $x_{1}$ and of $x_{2}$ and add those in
$N_{G}(x_{1})\Delta N_{G}(x_{2})$, that is,
$N_{G^{\prime}}^{r}(x_{0})=\big{(}N_{G}^{r}(x_{1})\cup
N_{G}^{r}(x_{2})\cup(N_{G}(x_{1})\Delta
N_{G}(x_{2}))\big{)}\setminus\\{x_{1},x_{2}\\}$, where $\Delta$ denotes the
symmetric set difference.

A _contraction sequence_ of a trigraph $G$ is a sequence of successive
contractions turning $G$ into a single vertex, and its _width_ is the maximum
red degree of any vertex in any trigraph of the sequence. The _twin-width_ of
a trigraph $G$ is the minimum width over all possible contraction sequences of
$G$.

As shown already in the pioneering paper on this concept [2], the twin-width
of planar graphs is bounded (but there was no explicit number given there). In
the first half of 2022, first explicit upper bounds on the twin-width of
planar graphs have appeared; $183$ by Jacob and Pilipczuk [6], $583$ by Bonnet
et al. [3] (this paper more generally bounds the twin-width of so-called
$k$-planar graphs with an asymptotic exponential function of $O(k)$), and most
recently $37$ by Bekos et al. [1] (which more generally bounds the twin-width
of so-called $h$-framed graphs, and in particular gives also an upper bound of
$80$ on the twin-width of $1$-planar graphs). It is worth to mention that all
three papers [6, 3, 1], more or less explicitly, use the product structure
machinery of planar graphs (cf. [4]) which, however, has its limits towards
the exact maximum twin-width of planar graphs.

We have recently developed an alternative decomposition-based approach,
leading to a single-digit upper bound of $9$ for all planar graphs in [5],
followed by an upper bound of $6$ on the twin-width of bipartite planar graphs
thereafter. However, the approach of [5] seems to be stuck right at $9$, too,
and new ideas are needed to obtain further improvements, even by $1$.

Here we give the following strengthened upper bound, which uses an improved
approach over previous [5] and also simplifies some cumbersome technical
details of the former:

######  Theorem 1.1.

The twin-width of any simple planar graph is at most $8$, and a corresponding
contraction sequence can be found in linear time.

It is worth to note that, very recently, Král’ and Lamaison [7] have found a
construction (with a proof) of a planar graph with twin-width $7$; hence, a
lower bound which is by just one off our new upper bound.

In an addition, we also give a simplified proof for the bipartite planar case:

######  Theorem 1.2 ([5]).

The twin-width of any simple bipartite planar graph is at most $6$, and a
corresponding contraction sequence can be found in linear time.

##  2 Notation and Tools

We start with a few technical definitions and claims needed for the proofs.

#### BFS layering and related.

Let $G$ be a connected graph and $r\in V(G)$ a fixed vertex. The _BFS layering
of $G$ determined by $r$_ is the vertex partition ${\cal
L}=(L_{0}=\\{r\\},L_{1},L_{2},\ldots)$ of $G$ such that $L_{i}$ contains all
vertices of $G$ at distance exactly $i$ from $r$. A path $P\subseteq G$ is
$r$-geodesic if $P$ is a subpath of some shortest path from $r$ to any vertex
of $G$ (in particular, $P$ intersects every layer of ${\cal L}$ in at most one
vertex). Let $T$ be a BFS tree of $G$ rooted at the vertex $r$ as above (that
is, for every vertex $v\in V(G)$, the distance from $v$ to $r$ is the same in
$G$ as in $T$). A path $P\subseteq G$ is $T$-vertical, or shortly vertical
with respect to implicit $T$, if $P$ is a subpath of some root-to-leaf path of
$T$. Notice that a $T$-vertical path is $r$-geodesic, but the converse may not
be true. Analogously, an edge $e\in E(G)$ is horizontal (with respect to
implicit ${\cal L}$) if both ends of $G$ are in the same ${\cal L}$-layer.

Observe the following:

######  Claim 1.

For every edge $\\{v,w\\}$ of $G$ with $v\in L_{i}$ and $w\in L_{j}$, we have
$|i-j|\leq 1$, and so a contraction of a pair of vertices from $L_{i}$ may
create new red edges only to the remaining vertices of $L_{i-1}\cup L_{i}\cup
L_{i+1}$.

#### Plane graphs and special BFS trees.

We will deal with plane graphs, which are planar graphs with a given
(combinatorial) embedding in the plane, and one marked outer face (the
remaining faces are then bounded). A plane graph is a plane triangulation if
every face of its embedding is a triangle. Likewise, a plane graph is a plane
quadrangulation if every face of its embedding is of length $4$. It is easy to
turn an embedding of any simple planar graph into a simple plane triangulation
by adding vertices and incident edges into each non-triangular face.
Furthermore, twin-width is non-increasing when taking induced subgraphs, and
so it suffices to focus on plane triangulations in the proof of Theorem 1.1,
and to similarly deal with plane quadrangulations in the proof of Theorem 1.2.

In this planar setting, consider now a plane graph $G$, and a BFS tree $T$
spanning $G$ and rooted in a vertex $r$ of the outer face of $G$, and picture
(for clarity) the embedding $G$ such that $r$ is the vertex of $G$ most at the
top. For two adjacent vertices $u,v\in V(G)$, $\\{u,v\\}\in E(G)$, we say that
$u$ is to the left of $v$ (wrt. $T$) if neither of $u,v$ lies on the vertical
path from $r$ to the other, and the following holds; if $r^{\prime}$ is the
least common ancestor of $u$ and $v$ in $T$ and $P_{r^{\prime},u}$ (resp.,
$P_{r^{\prime},v}$) denote the vertical path from $r^{\prime}$ to $u$ (resp.,
$v$), then the cycle $(P_{r^{\prime},u}\cup P_{r^{\prime},v})+uv$ has the
triple $(r^{\prime},u,v)$ in this counter-clockwise cyclic order.

A BFS tree $T$ of $G$ with the BFS layering ${\cal L}=(L_{0},L_{1},\ldots)$ is
called left-aligned if there is no edge $f=uv$ of $G$ such that, for some
index $i$, $u\in L_{i-1}$ and $v\in L_{i}$, and $u$ is to the left of $v$ (an
informal meaning is that one cannot choose another BFS tree of $G$ which is
“more to the left” of $T$ in the geometric picture of $G$ and $T$, such as by
picking the edge $uv$ instead of the parental edge of $v$ in $T$).

######  Lemma 2.1.

Given a simple plane graph $G$, and a vertex $r$ on the outer face, there
exists a left-aligned BFS tree of $G$ and can be found in linear time.

######  Proof 2.2.

For this proof, we have to extend the above relation of “being left of” to
edges emanating from a common vertex of $G$. So, for an arbitrary BFS tree T
of $G$ and edges $f_{1},f_{2}\in E(G)$ incident to $v\in V(G)$, such that
neither of $f_{1},f_{2}$ is the parental edge of $v$ in $T$, we write
$f_{1}\leq_{l}f_{2}$ if there exist adjacent vertices $u_{1},u_{2}\in V(G)$
such that $u_{1}$ is to the left of $u_{2}$, the least common ancestor of
$u_{1}$ and $u_{2}$ in $T$ is $v$ and, for $i=1,2$, the edge $f_{i}$ lies on
the vertical path from $u_{i}$ to $v$. Observe the following; if $f_{0}$ is
the parental edge of $v$ in $T$ (or, in case of $v=r$, $f_{0}$ is a “dummy
edge” pointing straight up from $r$), then $f_{1}\leq_{l}f_{2}$ implies that
the counter-clockwise cyclic order around $v$ is $(f_{0},f_{1},f_{2})$. In
particular, $\leq_{l}$ can be extended into a linear order on its domain.

We first run a basic linear-time BFS search from $r$ to determine the BFS
layering ${\cal L}$ of $G$. Then we start the construction of a left-aligned
BFS tree $T\subseteq G$ from $T:=\\{r\\}$, and we recursively (now in a “DFS
manner”) proceed as follows:

  * •

Having reached a vertex $v\in V(T)\subseteq V(G)$ such that $v\in L_{i}$, and
denoting by $X:=(N_{G}(v)\cap L_{i+1})\setminus V(T)$ all neighbours of $v$ in
$L_{i+1}$ which are not in $T$ yet, we add to $T$ the nodes $X$ and the edges
from $v$ to $X$.

  * •

We order the vertices in $X$ using the cyclic order of edges emanating from
$v$ to have it compatible with $\leq_{l}$ at $v$, and in this increasing order
we recursively (depth-first, to be precise) call the procedure for them.

The result $T$ is clearly a BFS tree of $G$. Assume, for a contradiction, that
$T$ is not left-aligned, and let $u_{1}\in L_{i-1}$ and $u_{2}\in L_{i}$ be a
witness pair of it, where $\\{u_{1},u_{2}\\}\in E(G)$ and $u_{1}$ is to the
left of $u_{2}$. Let $v$ be the least common ancestor of $u_{1}$ and $u_{2}$
in $T$, and let $v_{1}$ and $v_{2}$ be the children of $v$ on the $T$-paths
from $v$ to $u_{1}$ and $u_{2}$, respectively. So, by the definition,
$vv_{1}\leq_{l}vv_{2}$ at $v$, and hence when $v$ has been reached in the
construction of $T$, its child $v_{1}$ has been taken for processing before
the child $v_{2}$. Consequently, possibly deeper in the recursion, $u_{1}$ has
been processed before the parent of $u_{2}$ and, in particular, the procedure
has added the edge $u_{1}u_{2}$ into $T$, a contradiction to $u_{1}$ being to
the left of $u_{2}$.

This recursive computation is finished in linear time, since every vertex of
$G$ is processed only in one branch of the recursion, and one recursive call
takes time linear in the number of incident edges (to $v$).

Notice that we have not assumed $G$ to be a triangulation in the previous
definition and in Lemma 2.1, which will be useful for the case of bipartite
planar graphs.

#### Vertex levels in contraction sequences.

We are going to work with contraction sequences which, preferably, preserve
the BFS layers of ${\cal L}$ of connected $G$. However, we do not always
preserve the layers, and so we need a notion which is related to the layers of
${\cal L}$, but it can differ from these layers when needed – informally, when
this “causes no harm at all”. For the graph $G$ itself, we define
$\lambda[G](v)=i$ if and only if $v\in L_{i}\in{\cal L}$. If $G^{\prime}$ is a
trigraph along a contraction sequence of $G$, and a vertex $v^{\prime}\in
V(G^{\prime})$ stems from a set $X\subseteq V(G)$ by (possible) contractions,
then $\lambda[G^{\prime}](v^{\prime})$ equals the minimum $i$ such that
$L_{i}\cap X\not=\emptyset$. We say that $\lambda[G^{\prime}](v^{\prime})$ is
the level of $v^{\prime}$ in $G^{\prime}$ along the considered contraction
sequence of $G$, or simply the level of $v^{\prime}$ when the particular graph
of a sequence is implicit. In other words, we can inductively say that if
$v^{\prime\prime}$ of $G^{\prime\prime}$ results by the contraction of
$u^{\prime}$ and $v^{\prime}$ of $G^{\prime}$, then
$\lambda[G^{\prime\prime}](v^{\prime\prime}):=\min(\lambda[G^{\prime}](u^{\prime}),\lambda[G^{\prime}](v^{\prime}))$.
If $w^{\prime}$ does not participate in a contraction along the subsequence
from $G^{\prime}$ to $G^{\prime\prime}$, then
$\lambda[G^{\prime\prime}](w^{\prime}):=\lambda[G^{\prime}](w^{\prime})$.

A _partial contraction sequence_ of $G$ is defined in the same way as a
contraction sequence of $G$, except that it does not have to end with a
single-vertex graph. A partial contraction sequence of $G$ is _level-
respecting_ if every step contracts, in a trigraph $G^{\prime}$ along the
sequence, only a pair $x,y\in V(G^{\prime})$ such that the following
inductively holds; the levels of $x$ and $y$ are the same, i.e.
$\lambda[G^{\prime}](y)=\lambda[G^{\prime}](x)$, or all neighbours of $y$ (red
or black) in $G^{\prime}$ are on the same level as $x$ is on, i.e.
$\lambda[G^{\prime}](z)=\lambda[G^{\prime}](x)$ for all $z$ such that
$\\{y,z\\}\in E(G^{\prime})$. (The conditions in the latter case, in
particular, imply that $\lambda[G^{\prime}](y)=\lambda[G^{\prime}](x)+1$; cf.
2.)

Usefulness of level-respecting contraction sequences lies in the subsequent
claim. Informally, we may say that our levels in $G^{\prime}$ behave
analogously to the BFS layers of $G$; the levels form a layering (in the usual
sense), albeit not a BFS layering.

######  Claim 2.

Let a trigraph $G^{\prime}$ result from a level-respecting partial contraction
sequence of a connected graph $G$. Then any vertex $z\in V(G^{\prime})$ may
have neighbours (red or black) only on the levels $\lambda[G](z)-1$,
$\lambda[G](z)$ and $\lambda[G](z)+1$. Moreover, $z$ must have some neighbour
on the level $\lambda[G](z)-1$.

######  Proof 2.3.

We proceed easily by induction. The claim is trivial from the definition of a
BFS layering when $G^{\prime}=G$ and $G$ is connected. Assume that $z\in
V(G^{\prime\prime})$ results from a contraction of a pair $x,y\in
V(G^{\prime})$, where $\lambda[G^{\prime\prime}](z)=\lambda[G^{\prime}](x)$.
Then
$\lambda[G^{\prime}](y)\in\\{\lambda[G^{\prime}](x),\lambda[G^{\prime}](x)+1\\}$
by the definition of a level-respecting contraction and connectivity of $G$.
So, there cannot be any neighbour of $z$ on the levels lower than
$\lambda[G^{\prime\prime}](z)-1=\lambda[G^{\prime}](x)-1$ from the induction.
Regarding levels higher than $\lambda[G^{\prime\prime}](z)+1$, they cannot
host any neighbour of $x$ in $G^{\prime}$ by the induction, and no neighbour
of $y$ as well by the definition of a level-respecting contraction (if
$\lambda[G^{\prime}](y)=\lambda[G^{\prime}](x)+1$). Lastly, since $x$ has a
neighbour on the level $\lambda[G^{\prime\prime}](z)-1$ in $G^{\prime}$, so
does $z$ in $G^{\prime\prime}$.

##  3 Proof of Theorem 1.1

###  3.1 Induction setup

Our main proof proceeds by induction on suitably defined subregions of the
assumed plane triangulation $G$. In this subsection, we define the setup of
this induction in Lemma 3.1, and show how it will imply the main result.

For a plane graph $G$ and its cycle $C$, the subgraph of $G$ bounded by $C$,
denoted by $G_{C}$, is the subgraph of $G$ formed by the vertices and edges of
$C$ and the vertices and edges of $G$ drawn inside $C$ – formally, in the
region of the plane bounded by $C$ and not containing the outer face. Let the
vertices in the set $U:=V(G_{C})\setminus V(C)$ be called the interior
vertices of $C$. We call a set $U_{0}\subseteq U$ an interior section of $C$
in $G$ if all neighbours of vertices of $U_{0}$ belong to $U_{0}\cup V(C)$ (in
other words, $U_{0}$ is a collection of connected components of $G[U]$).

Consider a now fixed BFS tree $T$ of $G$. Assume that a cycle $C$ of $G$ is
formed as $C=(P_{1}\cup P_{2})+f$, where $P_{1}$ and $P_{2}$ are two
$T$-vertical paths of length at least $1$ with a common end $u\in V(P_{1})\cap
V(P_{2})$ and $f\in E(G)$ is an edge joining the other ends $v_{1}$ of $P_{1}$
and $v_{2}$ of $P_{2}$. Observe that $u$ is the (unique) vertex of $G_{C}$
closest to the root $r$ of $T$. Then we say that $C$ is a V-separator in $G$
with respect to implicit $T$ (‘V’ as vertical), and we call $u$ the sink of
$C$ and $f$ the lid of $C$. If the vertices $u$, $v_{1}$, $v_{2}$ lie on $C$
in this counter-clockwise order (equivalently, if $v_{1}$ is to the left of
$v_{2}$ with respect to $T$), then we say that $P_{1}$ is the left path of $C$
and $P_{2}$ is the right path of $C$ (picture the sink at the top).

######  Lemma 3.1.

Let $G$ be a simple plane triangulation, and $T$ be a left-aligned BFS tree of
$G$ rooted at a vertex $r\in V(G)$ of the outer triangular face and defining
the initial levels $\lambda[G](\cdot)$. Assume that a cycle $C$ of $G$ is a
V-separator of $G$, that $G_{C}$ is the subgraph of $G$ bounded by $C$, and
$u$ is the sink of $C$. Let the distance of $u$ from the root $r$ be $\ell$,
so $\lambda[G](u)=\ell$, and the maximum distance from a vertex of $C$ to $r$
be $m\geq\ell+1$. Let $U\subseteq V(G_{C})$ be an interior section of $C$ in
$G$, and denote by $W:=V(G)\setminus(V(C)\cup U)$ the set of the “remaining”
vertices.

Then there exists a level-respecting partial contraction sequence of $G$ which
contracts only pairs of vertices that are in or stem from $U$, results in a
trigraph $G^{*}$, and satisfies the following conditions for every trigraph
$G^{\prime}$ along this sequence from $G$ to $G^{*}$:

  1. (I)

For $U^{\prime}:=V(G^{\prime})\setminus(V(C)\cup W)$ (which are the vertices
that are in or stem from $U$ in $G^{\prime}$), every vertex of $U^{\prime}$ in
$G^{\prime}$ has red degree at most $8$,

  2. (II)

every vertex of the left path of $C$ has at most $5$ red neighbours and every
vertex of the right path of $C$ has at most $3$ red neighbours in
$U^{\prime}$,

  3. (III)

the sink $u$ of $C$ has no red neighbour in $U^{\prime}$, and if the least
level of a vertex of $U$ in $G$ is $k\geq\ell+2$, then the vertices of $C$ on
levels up to $k-2$ in $G$ have no red neighbours in $U^{\prime}$ as well and
each of the (two) vertices of $C$ on the level $k-1$ in $G$ has at most $1$
red neighbour in $U^{\prime}$, and

  4. (IV)

at the end of the partial contraction sequence, for the set
$U^{*}:=V(G^{*})\setminus(V(C)\cup W)$ that stems from $U$ in $G^{*}$, we have
that if $z\in U^{*}$ is of level $i$, then $\ell<i\leq\max(m,\ell+2)$ and $z$
is the only vertex in $U^{*}$ of level $i$.

$r$$v_{1}$$v_{2}$$\leavevmode\nobreak\ {u}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$C\quad$$U$$f$$W$ $\leadsto$
$r$$v_{1}$$v_{2}$$\leavevmode\nobreak\ {u}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$U^{*}$$W$$(\leq\\!8)$$(\leq\\!5)$$(\leq\\!3)$
Figure 1: (left) The setup of Lemma 3.1, where $P_{1}$ and $P_{2}$ are the
left and right paths of the chosen V-separator $C$. (right) The outcome of the
claimed partial contraction sequence which contracts only vertices of $U$
inside the shaded region from the left, and which maintains bounded red
degrees in the region and on its boundary $C$. No other vertex than the
sketched ones is affected by the contraction sequence. Not all depicted red
edges do exist, and some of them may actually be black.

Before proceeding further, we comment on two important things. First, we
remark that, in Lemma 3.1, all vertices of $U$ have the distance from $r$
greater than $\ell$, but on the other hand the distance from $r$ to some
vertices in $U$ may be much larger than $m$ (and our coming proof is aware of
this possibility). Second, we observe that all vertices of $U$ on level
$\ell+1$ must be adjacent to the sink $u$, since all other potential
neighbours of them have the distance from $r$ greater than $\ell$.
Consequently, contracting $U$ on level $\ell+1$ into one vertex within the
claimed sequence indeed does not create a red edge to $u$, as long as we do
not contract into it from higher levels (which we will explicitly avoid in the
proof). We illustrate Lemma 3.1 in Figure 1.

We also observe that the assumptions and conditions of Lemma 3.1 directly
imply some other properties useful for the coming proofs.

######  Claim 3.

Respecting the notation and assumptions of Lemma 3.1, we also have that:

  1. (V)

Every red edge in $G^{\prime}$ has one end in $U^{\prime}$ and the other end
in $U^{\prime}\cup V(C)$,

  2. (VI)

if $P_{1}$ and $P_{2}$ are the left and right paths of $C$, respectively, and
$v\in V(P_{2})$ is of level $j$ in $G^{\prime}$, then there is no edge of
$G^{\prime}$ (red or black) from $v$ to a vertex of
$U^{\prime}\cup(V(P_{1})\setminus\\{u\\})$ of level $j-1$ in $G^{\prime}$,

  3. (VII)

at the end, that is, in $G^{*}$, every vertex of the left path of $C$ has at
most $3$ red neighbours and every vertex of the right path of $C$ has at most
$2$ red neighbours in $U^{*}$.

Regarding (V), observe that since only vertices that stem from $U$ participate
in contractions, every red edge of $G^{\prime}$ must have an end in
$U^{\prime}$. Furthermore, since $U$ is an interior section of $C$, no vertex
of $U$ is adjacent to a vertex of $W$ in $G$, and hence no vertex of $W$ is
ever adjacent to a vertex being contracted in our sequence from $G$ to
$G^{*}$.

Concerning (VI), if $v$ were adjacent to $x\in V(P_{1})$ of level $j-1$, then
this was already true in $G$; $\\{x,v\\}\in E(G)$. If $v$ were adjacent to
$x^{\prime}\in U^{\prime}$ of level $j-1$ in $G^{\prime}$, then, among the
vertices of $U$ contracted into $x^{\prime}$, there had to be $x\in U$ such
that $\\{x,v\\}\in E(G)$. By the definition of a level-respecting sequence,
possible vertices of level higher than $j-1$ contracted into $x^{\prime}$
cannot be adjacent to $v$ of level $j$, and so $\lambda[G](x)=j-1$, too.
Since, in both cases, such $x$ would be to the left of $v$ in $G$, this
contradicts the assumption that $T$ is left-aligned.

Finally, (VII) directly follows from 2 and (IV) for the left path of $C$. For
the right path we additionally apply (VI), which for $x\in V(P_{2})$ of level
$j$ says that potential red neighbours of $x$ are only on levels $j$ and
$j+1$.

We also show how Lemma 3.1 implies the first part of our main result:

######  Proof 3.2 (Proof of Theorem 1.1 (the upper bound)).

We start with a given simple planar graph $H$, and extend any plane embedding
of $H$ into a simple plane triangulation $G$ such that $H$ is an induced
subgraph of $G$. Then we choose a root $r$ on the outer face of $G$ and, for
some left-aligned BFS tree of $G$ rooted in $r$ which exists by Lemma 2.1, the
facial cycle $C$ of the outer face incident to $r$, and $u=r$, we apply Lemma
3.1.

This way we get a partial contraction sequence from $G$ to a trigraph $G^{*}$
of maximum red degree $8$ (along the sequence). Observe by (IV) that the set
$U^{*}=V(G^{*})\setminus V(C)$ contains only two vertices, on levels $1$ and
$2$. In the final phase, we may hence pairwise contract the remaining vertices
in an arbitrary order. The restriction of this whole contraction sequence of
$G$ to only $V(H)$ then certifies that the twin-width of $H$ is at most $8$.

###  3.2 Decomposing into subregions

Here we, for start, decompose the full general induction step of the proof of
Lemma 3.1 into suitable substeps.

So, let $C$ be a V-separator in the plane triangulation $G$, formed by the
left path $P_{1}$, the right path $P_{2}$ and the lid edge
$f=\\{v_{1},v_{2}\\}$ where $v_{i}$ is an end of $P_{i}$. Let $G_{C}$ be the
subgraph bounded by $C$ and $U\subseteq V(G_{C})$ be an interior section of
$C$ in $G$. Moreover, assume that there exists a triangular face in $G$
incident to $f$ with the vertices $v_{1},v_{2},v_{3}$ where $v_{3}\in U$, and
that the $T$-vertical path from $v_{3}$ to the root $r$ contains neither
$v_{1}$ nor $v_{2}$. In particular, since $T$ is left-aligned, we have that
$\lambda[G](v_{2})\leq\lambda[G](v_{1})$ and
$\lambda[G](v_{3})\leq\lambda[G](v_{1})$. Under these assumptions, we are
going to define the vertical-horizontal division of $G_{C}$ as follows.

$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}$$\leavevmode\nobreak\ u_{3}\leavevmode\nobreak\
$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$P_{3}$$C_{2}$$x_{2}$$y_{2}$$x_{1}$$\>y_{1}$$h_{1}$$h_{2}$$f$$f_{1}$$f_{2}$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u=u_{3}}$$v_{3}$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$P_{3}$$C_{2}$$e\\!:\,\leavevmode\nobreak\
$$x_{2}$$y_{2}$$x_{1}$$y_{1}$$h_{1}$$h_{2}$$f$$f_{1}$$f_{2}$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}$$\leavevmode\nobreak\ u_{3}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\
P_{2}$$P_{3}$$C_{2}$$x_{2}$$y_{2}$$x_{1}$$\leavevmode\nobreak\
y_{1}$$h_{1}$$h_{2}$$f$$f_{1}$$f_{2}$ Figure 2: Three schematic cases of the
vertical-horizontal division of $G_{C}$ discussed in Section 3.2. The
(possible) dotted horizontal edge $e$ in the middle case is not counted as
$h_{1}$ since no vertex of $U$ is on a level above it in the picture.

Let $P\subseteq T$ be the vertical path connecting $v_{3}$ to the root $r$
where, by $r\not\in U$ and planarity of $G$, we have that $P$ contains the
sink $u$. Let $P_{3}\subseteq P$ be the subpath of $P$ from $v_{3}$ to the
first vertex $u_{3}\in V(P)\cap V(C)$ shared with the cycle $C$. We have
$u_{3}\not=v_{3}$. (It may be that $u_{3}\in V(P_{1})$ or $u_{3}\in V(P_{2})$
or even $u_{3}=u$; see in Figure 2.) Let $P_{31}$ denote the subpath of $P$
from $v_{3}$ to the first intersection $x$ with $P_{1}$ ($x\in\\{u_{3},u\\}$),
and $P_{11}$ the subpath of $P_{1}$ from $v_{1}$ till $x$. Similarly, let
$P_{32}$ denote the subpath of $P$ from $v_{3}$ to the first intersection $y$
with $P_{2}$, and $P_{22}$ be the subpath of $P_{2}$ from $v_{2}$ till $y$.
Let $f_{1}=\\{v_{1},v_{3}\\}$ and $f_{2}=\\{v_{2},v_{3}\\}$. Observe that
$P_{31},P_{32}\subseteq G_{C}$, and that $C_{1}:=(P_{11}\cup P_{31})+f_{1}$
and $C_{2}:=(P_{22}\cup P_{32})+f_{2}$ are again V-separators in $G$, such
that $P_{31}$ is the right path of $C_{1}$ and $P_{32}$ is the left path of
$C_{2}$.

Furthermore, let $h_{1},\ldots,h_{a}$, $a\geq 0$, be the collection of all
horizontal edges of $G_{C}$ such that, for $h_{i}=\\{x_{i},y_{i}\\}$, we have
$x_{i}\in V(P_{1})$, $y_{i}\in V(P_{3})\setminus V(C)$ and
$\lambda[G](x_{i})=\lambda[G](y_{i})$, and that
$\lambda[G](z)\leq\lambda[G](x_{i})-1$ holds for some $z\in U$ (the reason for
this strange-looking restriction is in property (III) of Lemma 3.1). These
edges $h_{1},\ldots,h_{a}$ are ordered by their increasing level
$\lambda[G](x_{i})$. This is illustrated in Figure 2 (where the ordering of
$h_{i}$’s is top-down). For $i=1,\ldots,a$, let $C_{1,i-1}$ denote the cycle
passing through the sink of $C_{1}$ (which is $u_{3}$ or $u$) and formed by
relevant subpaths of $P_{11},P_{31}$ and the edge $h_{i}$. Let
$C_{1,a}=C_{1}$. Let $U_{1,0}$ denote the set of the interior vertices of
$C_{1,0}$ in $G$, and for $i=1,\ldots,a$, let $U_{1,i}:=X\setminus U_{1,i-1}$
where $X$ is the set of the interior vertices of $C_{1,i}$ in $G$. Let $U_{2}$
denote the set of the interior vertices of $C_{2}$ in $G$.

The system of the cycles $C_{1,0},\ldots,C_{1,a},C_{2}$ and of the sets
$U_{1,0},\ldots,U_{1,a},U_{2}$ is called the vertical-horizontal division of
$G_{C}$. The following is straightforward from the definition:

######  Claim 4.

For $i=0,1,\ldots,a$, the cycle $C_{1,i}$ is a V-separator in $G$, and each
vertex of $U_{1,i}$ has neighbours only in $U_{1,i}\cup V(C_{1,i})$. Hence,
$U_{1,i}$ is an interior section of $C_{1,i}$. Consequently, for every $z\in
U_{1,i}$ where $i\geq 1$, we have $\lambda[G](z)\geq\lambda[G](x_{i})+1$
(where $\\{x_{i},y_{i}\\}=h_{i}$ above).

The induction step in the proof of Lemma 3.1 will start with the next lemma:

######  Lemma 3.3.

Assume the notation and assumptions of Lemma 3.1 for the graph $G$, cycle $C$
and set $U$, and consider the vertical-horizontal division of the subgraph
$G_{C}$ as defined above; that is, the cycles $C_{1,0},\ldots,C_{1,a},C_{2}$
and the sets $U_{1,0},\ldots,U_{1,a},U_{2}$. Then the following hold:
a) Each cycle $C^{1}\in\\{C_{1,0},\ldots,C_{1,a},C_{2}\\}$ and the
corresponding set $U^{1}\in\\{U_{1,0},$ $\ldots,U_{1,a},U_{2}\\}$ satisfy the
assumptions of Lemma 3.1 (in the place of $C$ and $U$).
b) Let $\tau_{1,i}$, $i=0,\ldots,a$, denote the level-respecting partial
contraction sequence of $G$ claimed by Lemma 3.1 for the input as in (a)
$C^{1}:=C_{1,i}$ and $U^{1}:=U_{1,i}$, and likewise, $\tau_{2}$ be that for
the input $C^{1}:=C_{2}$ and $U^{1}:=U_{2}$. Then the concatenated partial
contraction sequence
$\sigma_{0}:=\tau_{2}\cdot\tau_{1,0}\cdot\ldots\tau_{1,a}$, i.e., one starting
with $\tau_{2}$ and ending with $\tau_{1,a}$, again satisfies the properties
(I), (II) and (III) of Lemma 3.1.

######  Proof 3.4.

Part (a) immediately follows from the definition and 4.

In part (b), we first argue that the concatenation $\sigma_{0}$ is well-
founded; that contractions in one of the subsequences of $\sigma_{0}$ have no
effect on vertices being contracted in another of the subsequences. This is
since, by 4, neighbours of contracted pairs of one subsequence are only in the
interior section of the same subsequence or on the bounding cycles which
together form $V(C)\cup V(P_{3})$ (and the latter set is not participating in
the contractions of $\sigma_{0}$).

Following on the previous argument, we have that the only vertices of $G_{C}$
that may potentially receive red edges from more than one of the subseqeunces
forming $\sigma_{0}$, are those of $V(C)\cup V(P_{3})$. See Figure 2. For all
other vertices of $G_{C}$, we have that (I) is true for them along whole
$\sigma_{0}$ since it has been true for them along their subsequences of
$\sigma_{0}$.

For a vertex $z\in V(P_{3})\setminus V(C)$, we see that $z$ belongs to $C_{2}$
and to each of $C_{1,i},\ldots,C_{1,a}$ for some $i\in\\{0,\ldots,a\\}$.
However, even if $i\leq a-2$, vertices of $U_{1,i+2}$ cannot be neighbours of
$z$ in $G_{C}$ due to a combination of 2 and 4. Therefore, $z$ may have
neighbours (and so can get red edges from by contractions) only in the
interior sections $U_{2}$ and $U_{1,i}$, and possibly in $U_{1,i+1}$ if $z$ is
an end of the horizontal edge $h_{i+1}$. Recall also that $z$ belongs to the
right path of $C_{1,i}$. Along the sequence $\sigma_{0}$, but before
$\tau_{1,i+1}$, the vertex $z$ has red degree at most $5+3=8$ by (II) applied
to $U_{2}$ and $U_{1,i}$. After $\tau_{1,i}$ is finished, $z$ has red degree
at most $3+2=5<8$ by (VII) of 3. So, along the rest of $\sigma_{0}$, (I) stays
true for $z$ with red degree at most $5+1=6$ by (III) applied possibly to
$U_{1,i+1}$.

For the vertex $u$ itself, (III) is true automatically. For $z\in
V(P_{1})\setminus\\{u\\}$ and $i\in\\{0,\ldots,a\\}$ being the least index
such that $z\in V(C_{1,i})$, we get that the properties are true along
$\tau_{1,i}$ and before by (II), and since $\tau_{1,i}$ ends, the vertex $z$
has at most $3$ red neighbours in $U_{1,i}$ by (VII). Additionally, $z$ may
get at most $1$ red neighbour in $U_{1,i+1}$ (and none in $U_{1,i+2},\ldots$)
by (III), altogether at most $4$, satisfying (II). In the special case of
$z\in V(P_{1})\setminus\\{u\\}$ covered by property (III) with respect to $C$,
that is when all vertices belonging to the interior of $C_{1}$ are on levels
higher than $\lambda[G](z)$, we get that this property is satisfied by (III)
with respect to $C_{1,i}$, and there are no more red neighbours of $z$ from
elsewhere.

Finally, for $z\in V(P_{2})\setminus\\{u\\}$, the conditions are simply true
by (II) and possibly (III) for $\tau_{2}$ and then along the whole sequence
$\sigma_{0}$.

###  3.3 Finishing the proof

Now we get to the proof of core Lemma 3.1 which will conclude our main result.

######  Proof 3.5 (Proof of Lemma 3.1).

We first resolve several special cases. If $U=\emptyset$, we are immediately
done with the empty partial contraction sequence. So, assume
$U\not=\emptyset$.

Recall the edge $f=\\{v_{1},v_{2}\\}\in E(G)$ connecting the other ends of the
left path $P_{1}$ and the right path $P_{2}$ of $C$. See again Figure 2. If
$v_{1}$ has no neighbour in $U$, then $\\{v_{2},v_{3}\\}\in E(G)$ where
$v_{3}$ is the neighbour of $v_{1}$ on $P_{1}$. In such case, we simply apply
Lemma 3.1 inductively to $P_{1}-v_{1}$ and $P_{2}$, while the rest of the
assumptions remain the same. The symmetric argument is applied when $v_{2}$
has no neighbour in $U$.

Otherwise, let $v_{3}\in U$ be the vertex (unique in $U$) such that
$(v_{1},v_{2},v_{3})$ bound a triangular face of $G$. Let $P\subseteq T$ be
the vertical path connecting $v_{3}$ to the root $r$. If $v_{1}\in V(P)$, then
$P\supset P_{1}$ and we (similarly as above) apply Lemma 3.1 inductively to
the V-separator $C^{1}=P\cup P_{2}$ with the lid $\\{v_{2},v_{3}\\}$, while
the rest of the assumptions again remain the same. Note that in this case,
$\lambda[G](v_{1})=\lambda[G](v_{3})-1=\lambda[G](v_{2})$ since $T$ is left-
aligned. In the resulting trigraph $G^{1}$, we have the set
$U^{1}:=V(G^{1})\setminus(V(C^{1})\cup W)$ that stems by contractions from the
interior of $C^{1}$. There is no vertex in $U^{1}$ of level higher than
$\lambda[G](v_{3})\geq 2$ and at most one of level equal to
$\lambda[G](v_{3})$, by (IV) of Lemma 3.1. We contract the latter vertex with
$v_{3}$, and then with the vertex of $U^{1}$ of the previous level
$\lambda[G](v_{1})$ unless $v_{1}$ is a neighbour of $u$ (cf. the special case
in (IV) ). This clearly does not exceed red degree $8$ there, and does not add
new potential red neighbours to the vertices of $C$. Since (IV) is now
satisfied, too, we are done. If $v_{2}\in V(P)$, we solve the case similarly
by induction applied to the V-separator $C^{1}=P_{1}\cup P$ with the lid
$\\{v_{1},v_{3}\\}$.

In all other cases, we have got a vertical-horizontal division of the subgraph
$G_{C}$, with $P_{3}\not=\\{v_{3},u\\}$, with the horizontal edges
$h_{1},\ldots,h_{a}$, $h_{i}=\\{x_{i},y_{i}\\}$, the cycles
$C_{1,0},\ldots,C_{1,a},C_{2}$ and the interior sets
$U_{1,0},\ldots,U_{1,a},U_{2}$, and we apply Lemma 3.3 to it. This way we get
a level-respecting partial contraction sequence $\sigma_{0}$, which satisfies
the properties (I), (II) and (III) of Lemma 3.1. Let $G^{0}$ denote the
trigraph which results from $G$ by $\sigma_{0}$, and let
$U^{0}_{1,0},\ldots,U^{0}_{1,a},U^{0}_{2}$ denote the vertex sets of $G^{0}$
that stem from $U_{1,0},\ldots,U_{1,a},U_{2}$, respectively.

We first consider a subcase, that $P_{3}$ consists of a single edge
$\\{v_{3},u_{3}\\}$ and there is no vertex $z\in U$ in $G$ such that
$\lambda[G](z)\leq\lambda[G](u_{3})$. This subcase has to be treated specially
to fulfill (III) of Lemma 3.1. Then $a=0$ in the vertical-horizontal division
of $G_{C}$, and
$\lambda[G](v_{1})\leq\lambda[G](v_{3})+1=\lambda[G](u_{3})+2$. Each of the
sets $U^{0}_{1,0}$ and $U^{0}_{2}$ hence contains vertices at most on the
levels $\lambda[G](v_{3})$ and $\lambda[G](v_{3})+1$, by (IV) of Lemma 3.1.

We finish the desired partial contraction sequence from $G^{0}$ in this
subcase by firstly contracting the two (if existing) vertices of
$U^{0}_{1,0}\cup U^{0}_{2}$ on the level $\lambda[G](v_{3})+1$, and secondly
by contracting each of the vertices of $U^{0}_{1,0}\cup U^{0}_{2}$ on the
level $\lambda[G](v_{3})$ with $v_{3}$. If $u_{3}=u$ is the sink of $C$, then
the only vertex on the level $\lambda[G](v_{3})-1=\lambda[G](u)$ in $G_{C}$ is
$u$, and so every vertex of $U^{0}_{1,0}\cup U^{0}_{2}$ on the level
$\lambda[G](v_{3})$ must be adjacent to $u$ (cf. 2), and this is by a black
edge due to an inductive invocation of (III). Therefore, the contractions into
$v_{3}$ do not create a red edge to $u$. If $u_{3}\not=u$, then let
$u_{3}^{\prime}$ denote the other vertex of $P_{1}\cup P_{2}$ on the level
$\lambda[G](u_{3})$. Analogously to the previous, one of the contractions into
$v_{3}$ does not create a red edge to $\\{u_{3},u_{3}^{\prime}\\}$ and the
other contraction can do so, but at most one red edge to each of
$u_{3},u_{3}^{\prime}$. Therefore, (IV) is true here, and the remaining
properties of Lemma 3.1 are fulfilled easily.

In the remaining cases, we possibly add the following bit in a sequence
$\sigma_{1}$ after $\sigma_{0}$ (while this bit has not been possible in the
special subcase above): If $u_{3}\in V(P_{1})\setminus\\{u\\}$ and $u_{3}$ is
a neighbour of both $x_{1},y_{1}$ (of $h_{1}$), then $U^{0}_{1,0}$ by (IV)
consists of at most two vertices, which we contract into one vertex in
$\sigma_{1}$ – this move adds one red edge incident to $u_{3}$. Analogously,
if $u_{3}\in V(P_{2})\setminus\\{u\\}$ and $u_{3}$ is a neighbour of both
$v_{2},v_{3}$ (of $f_{2}$), then we contract the at most two vertices of
$U^{0}_{2}$ into one within $\sigma_{1}$. Although this contraction in
$\sigma_{1}$ does not preserve levels, it is level-respecting by 2 since
$U_{1,0}$ and $U_{2}$ were interior sections of the triangles $C_{1,0}$ and
$C_{2}$, respectively. In both cases, the added red edge incident to $u_{3}$
does not violate the properties of Lemma 3.1; this follows from the bounds in
(VII) of 3 which are by at least one lower than the bounds in (II) of Lemma
3.1, and property (III) is void for $u_{3}$ unless we have got the previous
special subcase. Otherwise, we leave $\sigma_{1}=\emptyset$.

After applying $\sigma_{1}$ to $U^{0}_{1,0},\ldots,U^{0}_{1,a},U^{0}_{2}$ in
$G^{0}$, we get the trigraph $G^{1}$ and the sets
$U^{1}_{1,0},\ldots,U^{1}_{1,a},U^{1}_{2}$ (which are identical to the former
ones except possibly $U^{0}_{1,0}$ or $U^{0}_{2}$). See Figure 3.

$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}$$u_{3}\leavevmode\nobreak\
$$P_{1}$$P_{2}$$U^{1}_{1,0}$$U^{1}_{1,1}$$U^{1}_{1,2}$$U^{1}_{2}$$h_{2}:\leavevmode\nobreak\
x_{2}$$\leavevmode\nobreak\ y_{2}$$h_{1}:\leavevmode\nobreak\
x_{1}$$\leavevmode\nobreak\ y_{1}$$S_{0}$$S_{1}$$S_{2}$$f$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}$$\leavevmode\nobreak\
u_{3}$$P_{1}$$P_{2}$$U^{1}_{1,0}$$U^{1}_{1,1}$$U^{1}_{1,2}$$U^{1}_{2}$$h_{2}:\leavevmode\nobreak\
x_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
y_{2}$$h_{1}:\leavevmode\nobreak\ x_{1}$$\leavevmode\nobreak\
y_{1}\leavevmode\nobreak\ $$S_{0}$$S_{1}$$S_{2}$$f$ Figure 3: Proof of Lemma
3.1: a schematic picture of the situation after the parts of the depicted
vertical-horizontal division of $G_{C}$ have been recursively contracted
(right before the $\sigma_{2}$-contractions start). The cases of $u_{3}$ on
the left and right paths are not symmetric in general.

In the next steps, we are going to define level-respecting partial contraction
sequences $\sigma_{2,a},\sigma_{2,a-1},\ldots,\sigma_{2,0}$ which, when
concatenated after $\sigma_{0}\cdot\sigma_{1}$, give the desired outcome. If
$a=0$, the sequence $\sigma_{2,0}$ is going to contract the sets $U^{1}_{1,0}$
with $S_{0}:=V(P_{3})\setminus\\{u_{3}\\}$ and $U^{1}_{2,0}:=U^{1}_{2}$. If
$a>0$, the sequence $\sigma_{2,a}$ is going to contract $U^{1}_{1,a}$ with the
sets $S_{a}$ and $U^{1}_{2,a}$, where $S_{a}\subseteq
V(P_{3})\setminus\\{u_{3}\\}$ and $U^{1}_{2,a}\subseteq U_{2}$ are both the
subsets of those vertices on levels greater than $\lambda[G](y_{a})$. The
sequence $\sigma_{2,i}$ for $0\leq i<a$ is going to contract $U^{1}_{1,i}$
with the sets $S_{i}$ and $U^{1}_{2,i}$, where $S_{i}\subseteq
V(P_{3})\setminus\\{u_{3}\\}$ and $U^{1}_{2,i}\subseteq U^{1}_{2}$ are the
subsets of those vertices on levels greater (if $i\geq 1$) than
$\lambda[G](y_{i})$ and not greater than $\lambda[G](y_{i+1})$. Of course,
some of these sets may be empty, and hence some contractions may not happen.

Specifically, for $i\in\\{0,\ldots,a\\}$ let $p=\max_{z\in
C_{1,i}}\\!\lambda[G](z)$ and $q=1+\min_{z\in C_{1,i}}\\!\lambda[G](z)$.
Observe that there is no vertex in $U^{1}_{1,i}\cup U^{1}_{2,i}$ of level
lower than $q$ or greater than $p$. This follows from an inductive invocation
of (IV) of Lemma 3.1, and from the sequence $\sigma_{1}$. So, the union
$U^{1}_{1}:=U^{1}_{1,0}\cup\ldots\cup U^{1}_{1,a}$ has at most one vertex on
each level. Likewise, each of the sets $V(P_{3})$ and $U^{1}_{2}$ has at most
one vertex on each level. The sequence $\sigma_{2,i}$ first runs over
$j=p,p-1,\ldots,q$ in this order, and contracts the pair of vertices of
$S_{i}\cup U^{1}_{2,i}$ of the equal level $j$ in $G^{1}$ (or nothing if there
is at most one such vertex there). In its second round, $\sigma_{2,i}$ again
runs over $j=p,p-1,\ldots,q$ in this order, and contracts the vertex of level
$j$ that stems from $S_{i}\cup U^{1}_{2,i}$ in the first round, with the
vertex of $U^{1}_{1,i}$ of equal level $j$ in $G^{1}$.

Let $\sigma_{2}$ be the concatenation of the described sequences,
$\sigma_{2}:=\sigma_{2,a}\cdot\sigma_{2,a-1}\cdot\ldots\sigma_{2,0}$ in this
order, and $G^{2}$ denote the trigraph which results from $G^{1}$ by applying
$\sigma_{2}$. Let $U^{2}:=V(G^{2})\setminus(V(C)\cup W)$ denote the contracted
vertices in the interior of $C$ in $G^{2}$. Then $G^{2}$ and $U^{2}$ satisfy
property (IV) of Lemma 3.1 (in the place of $G^{*}$ and $U^{*}$), which is
immediate from the previous definition of $\sigma_{2}$. It thus remains to
verify the properties (I), (II) and (III) of Lemma 3.1 along the sequence
$\sigma_{2}$ from $G^{1}$ to $G^{2}$, that is, for every trigraph $G^{\prime}$
along $\sigma_{2}$.

Denote by $U^{\prime}:=V(G^{\prime})\setminus(V(C)\cup W)$ all interior
vertices of $C$ in $G^{\prime}$, and by $U^{\prime\prime}:=U^{\prime}\setminus
V(G^{1})$ the (new) interior vertices that stem by $\sigma_{2}$-contractions
from $G^{1}$ to $G^{\prime}$, and recall (from Section 3.2) that
$P_{31}\supseteq P_{3}$ is the right path of $C_{1}$ and $P_{32}\supseteq
P_{3}$ is the left path of $C_{2}$ in $G_{C}$.

We start with verification of (III) which has already been in parts addressed
above. Regarding the sink vertex $u$, it has got red edges neither from the
sequence $\sigma_{0}$ by an inductive invocation of (III), nor from the
sequence $\sigma_{1}$. The vertices of $C$ on levels up to $k-2$ as in (III)
do not have any neighbour in $U^{\prime}$ by 2. Consider the vertices
$z,z^{\prime}\in V(C)$ on the level $k-1$ as in (III) (if $k\geq\ell+2$
there). If $\lambda[G](u_{3})\geq k$, then no contraction on the level $k$
happens within $\sigma_{2}$ (Figure 2), and so $z$ and $z^{\prime}$ have each
at most one red edge to $U^{\prime}$ by an inductive invocation of (III).
Otherwise, up to symmetry, $z^{\prime}=u_{3}$. Similarly as argued earlier in
this proof, $u_{3}$ then has a black edge to $U^{1}_{1,0}$ (if $u_{3}\in
V(P_{1})$) or to $U^{1}_{2}$ (if $u_{3}\in V(P_{2})$) in $G^{1}$, and so the
contraction on the level $k$ incident with this black edge does not create a
new red edge to either of $z,u_{3}$. At the same time, each of $z,u_{3}$ has
at most one red edge in $G^{1}$ by an inductive invocation of (III), and this
stays true also (with the set $U^{\prime}$) during and after contractions on
the level $k$ within $\sigma_{2}$.

We move towards verification of (I). Let $z\in U^{\prime}$ for the rest. If
$z\in U^{1}_{2}$, then no $\sigma_{2}$-contraction has touched $z$ so far. In
this case $z$ may have red edges to up to $3$ vertices of $V(P_{2})\cup
U^{1}_{2}\cup V(P_{32})$ of level $\lambda[G^{1}](z)-1$, to $2$ vertices of
$V(P_{2})\cup V(P_{32})$ of level $\lambda[G^{1}](z)$, and to $2$ vertices of
$V(P_{32})\cup U^{1}_{2}\cup U^{\prime\prime}$ of level $\lambda[G^{1}](z)+1$,
altogether at most $7$. Note that there is no edge from $z$ to the vertex of
$P_{2}$ of level $\lambda[G^{1}](z)+1$ by (VI) of 3. If $z\in
V(P_{3})\setminus\\{u_{3}\\}$, then similarly, $z$ may have red edges to up to
$2+2$ vertices of $U^{1}_{1}\cup U^{1}_{2}$ on the levels
$\lambda[G^{1}](z)-1$ and $\lambda[G^{1}](z)$, and to up to $2$ vertices of
$U^{1}_{1}\cup U^{1}_{2}\cup U^{\prime\prime}$ on the level
$\lambda[G^{1}](z)+1$. The case of $z\in U^{1}_{1}$ (not-yet touched by a
$\sigma_{2}$-contraction) is similarly easy.

Assume now that $z\in U^{\prime\prime}$ has been created in $G^{\prime}$ by a
contraction of $z_{2}\in U^{1}_{2}$ and $z_{3}\in
V(P_{3})\setminus\\{u_{3}\\}$ (i.e., within the first round of some
$\sigma_{2,i}$ above), but $z$ is not contracted with a vertex of $U^{1}_{1}$
yet. Let $t\in V(P_{1})\setminus V(P_{3})$ denote the possible (unless equal
to $u_{3}$) vertex of $P_{1}$ of level $\lambda[G^{1}](z_{3})-1$. Then there
is no edge in $G^{1}$ from $t$ to $z_{2}$ by planarity, and no from $t$ to
$z_{3}$ by (VI) of 3. The same applies to the possible vertex $t^{\prime}\in
U^{1}_{1}$ of level $\lambda[G^{1}](z_{3})-1$. Consequently, $z$ may have red
edges to up to $3$ vertices of $V(P_{2})\cup U^{1}_{2}\cup V(P_{32})$ of level
$\lambda[G^{\prime}](z)-1$, to $3$ vertices of $V(P_{2})\cup V(U^{1}_{1})\cup
V(P_{1})$ of level $\lambda[G^{\prime}](z)$, and to up to $3$ vertices of
$U^{\prime\prime}\cup V(U^{1}_{1})\cup V(P_{1})$ of level
$\lambda[G^{\prime}](z)+1$, again using (VI). This sums to $3+3+3=9$, but we
are going to show that this maximum of $9$ cannot be achieved. Let $z_{1}\in
V(P_{1})$ be such that $\lambda[G^{\prime}](z_{1})=\lambda[G^{\prime}](z)$. If
$\\{z_{1},z_{3}\\}\not\in E(G)$, then no red edge $\\{z_{1},z\\}$ is created
by the current contraction and the sum is at most $8$, as needed. If
$\\{z_{1},z_{3}\\}=h_{i}\in E(G)$, then the sequence $\sigma_{2,i}$ has
already contracted $S_{i}\cup U^{1}_{1,i}$ into $U^{\prime\prime}$, and so
there are only $2$ red neighbours of $z$ in $U^{\prime\prime}\cup V(P_{1})$ on
the level $\lambda[G^{\prime}](z)+1$, again summing to at most $8$. If
$\\{z_{1},z_{3}\\}\in E(G)$, but $\\{z_{1},z_{3}\\}$ has not been chosen as
any $h_{i}$ in the vertical-horizontal division above, then there are no
vertices in $U^{1}_{2}\cup(V(P_{3})\setminus\\{u_{3}\\})$ on the level
$\lambda[G^{\prime}](z)-1$, and so the sum is at most $8$.

Assume that $z\in U^{\prime\prime}$ has already been created in $G^{\prime}$
by a contraction of all vertices in $U^{1}_{2}\cup V(P_{3})\cup U^{1}_{1}$ of
the same level. Let this contraction be part of $\sigma_{2,i}$ for some $0\leq
i\leq a$. Then $z$ may have red edges to up to $2$ vertices of $V(P_{2})\cup
V(P_{1})$ of level $\lambda[G^{\prime}](z)$, to $2$ vertices of
$U^{\prime\prime}\cup V(P_{1})$ of level $\lambda[G^{\prime}](z)+1$ (but not
to $V(P_{2})$ due to (VI)), and to vertices of $V(P_{2})\cup U^{1}_{2}\cup
V(P_{3})\cup V(U^{1}_{1})\cup U^{\prime\prime}\cup V(P_{1})=:Y$ of level
$\lambda[G^{\prime}](z)-1$. However, at most $4$ of the vertices of $Y$ are
potential red neighbours of $z$ (so summing to at most $8$), as we now show.
If contractions on the level $\lambda[G^{\prime}](z)-1$ are part of
$\sigma_{2,i}$, too, then red neighbours of $z$ in $Y$ of level
$\lambda[G^{\prime}](z)-1$ actually belong to $V(P_{2})\cup
U^{\prime\prime}\cup V(U^{1}_{1})\cup V(P_{1})$ with an upper bound of $4$.
Otherwise, if contractions on the level $\lambda[G^{\prime}](z)-1$ are part of
$\sigma_{2,i-1}$, then there is no edge from $z$ to a vertex of $U^{1}_{i-1}$,
or $U^{1}_{i-1}$ on the level $\lambda[G^{\prime}](z)-1$ has already been
contracted into $U^{\prime\prime}$, too. Then red neighbours of $z$ in $Y$ of
level $\lambda[G^{\prime}](z)-1$ belong to $V(P_{2})\cup U^{1}_{2}\cup
V(P_{3})\cup V(P_{1})$ or to $V(P_{2})\cup U^{\prime\prime}\cup V(P_{1})$, and
we again get a bound of $4$.

Finally, we want to verify (II) of Lemma 3.1. Consider $z\in
V(P_{2})\setminus\\{u\\}$. By the definition of $\sigma_{2}$, the vertex $z$
may have at most one red neighbour of each level in $U^{\prime}$ (at any
moment of $\sigma_{2}$). Then the bound of at most $3$ red edges from $z$ to
$U^{\prime}$ follows immediately in view of 2. Consider now $z\in
V(P_{1})\setminus\\{u\\}$, which is a bit more complicated case. On each of
the levels $\lambda[G^{1}](z)-1$, $\lambda[G^{1}](z)$ and
$\lambda[G^{1}](z)+1$ of $U^{\prime}$, there are clearly at most $2$ red
neighbours of $z$. Although, we now show that the maximum sum of $6$ cannot be
achieved. If $z=u_{3}$, then there is actually at most red neighbour of $z$ on
the level $\lambda[G^{1}](z)-1$. Otherwise, we denote the following vertices
of $G^{1}$ of level $\lambda[G^{1}](z)+1$ by $z_{1},z_{2},z_{3}$ such that
$z_{1}\in U^{1}_{1}$, $z_{2}\in U^{1}_{2}$, $z_{3}\in V(P_{3})$, and
$\lambda[G^{1}](z_{1})=\lambda[G^{1}](z_{2})=\lambda[G^{1}](z_{3})=\lambda[G^{1}](z)+1$.
Then $z_{3}$ has no edge to $z\not=u_{3}$ by (VI) of 3, and $z_{2}$ has no
edge to $z$ by planarity. If $z_{3}\in U^{\prime}$ (i.e., not contracted yet),
then only $z_{1}$ may be a red neighbour of $z$. If $z_{2}$ and $z_{3}$ have
already been contracted in $G^{\prime}$, but $z_{1}\in U^{\prime}$, then the
new vertex again has no edge to $z$. Finally, if all of $z_{1},z_{2},z_{3}$
have been contracted in $G^{\prime}$, then $U^{\prime}$ has only (this) one
vertex of level $\lambda[G^{1}](z)+1$. In any case, $z$ has at most $5$ red
neighbours in $U^{\prime}$.

We have verified all conditions of Lemma 3.1 for the partial contraction
sequence $\sigma_{0}\cdot\sigma_{1}\cdot\sigma_{2}$, and so we can set
$G^{*}:=G^{2}$ and the proof is done.

######  Proof 3.6 (Proof of Theorem 1.1 (the algorithmic part)).

We can construct a simple plane triangulation $G\supseteq H$ in linear time
using standard planarity algorithms, and then construct a left-aligned BFS
tree $T\subseteq G$ again in linear time by Lemma 2.1. In the rest, we
straightforwardly implement the recursive vertical-horizontal division of $G$
as used in the proof of Lemma 3.1, and construct the contraction sequence of
$H$ on return from the recursive calls as defined in the proof. Note that we
do not need at all to construct the intermediate trigraphs along the
constructed contraction sequence, and so the construction of the sequence is
very easy—each recursive call returns just a simple list of the vertices which
stem from the recursive contractions, indexed by the levels. Then these (up
to) two lists are easily in linear time “merged” together with the dividing
path $P_{3}$, as specified by the proof of Lemma 3.1, into the resulting list
of this call.

We may account total runtime in the “division part” of the algorithm to the
edge(s) of $v_{3}$ into $v_{1}$ or $v_{2}$ and the edges of the path $P_{3}$
starting in $v_{3}$ in each call of the recursion, and these edges are not
counted multiple times in different branches of the recursion. Likewise,
runtime of the “merging” part of each recursive call can be counted to the
individual steps of the resulting contraction sequence, which is of linear
length. Hence, altogether, the algorithm runs in linear time.

##  4 Proof of Theorem 1.2

On a high level, the proof will still proceed in the same way as in [5], and
will prove the same bound. However, there will be significant changes in the
technical details, in which ideas from the previous section can save a lot of
difficulties of the cumbersome proof from [5].

In a nutshell, the bipartite case carries two major differences from the proof
of the general planar case (and this was the same already in [5]):

  * •

Since our graph is now bipartite, we will work with a plane quadrangulation
(instead of a triangulation). However, with a suitable detailed analysis, it
does not bring any significant new challenges to the proof.

  * •

Since, again, our graph is bipartite, we immediately get that in any BFS
layering, each layer is an independent set, and so we will never create a red
edge inside the same layer. This is the crucial saving which allows us to
derive a better upper bound on the red degree along the constructed sequence.

Before proceeding further, we need to adjust the concept of a level-respecting
contraction sequence (beacuse of the fact that the definition from Section 2
possibly allowed to create red edges inside the same level).

A partial contraction sequence of $G$ is _bi-level-respecting_ if every step
contracts, in a trigraph $G^{\prime}$ along the sequence, only a pair $x,y\in
V(G^{\prime})$ such that the following inductively holds; the levels of $x$
and $y$ are the same, i.e. $\lambda[G^{\prime}](y)=\lambda[G^{\prime}](x)$, or
all neighbours of $y$ (red or black) in $G^{\prime}$ are on the level
$\lambda[G^{\prime}](x)+1$, i.e.
$\lambda[G^{\prime}](z)=\lambda[G^{\prime}](x)+1$ is true for all $z$ such
that $\\{y,z\\}\in E(G^{\prime})$. Again, we easily get by induction as in 2:

######  Claim 5.

Let a trigraph $G^{\prime}$ result from a bi-level-respecting partial
contraction sequence of a bipartite connected graph $G$. Then any vertex $z\in
V(G^{\prime})$ may have neighbours (red or black) only on the levels
$\lambda[G](z)-1$ and $\lambda[G](z)+1$. In particular, the trigraph
$G^{\prime}$ is again bipartite. Moreover, $z$ must have some neighbour on the
level $\lambda[G](z)-1$.

###  4.1 Induction setup

Our proof is again by induction, precisely as set up in the following lemma.
Before starting, note that a plane quadrangulation is always bipartite, and so
it has all cycles (not only the faces) of length at least $4$.

######  Lemma 4.1.

Let $G$ be a simple plane quadrangulation, and $T$ be a left-aligned BFS tree
of $G$ rooted at a vertex $r\in V(G)$ of the outer face and defining the
initial levels $\lambda[G](\cdot)$. Assume that a cycle $C$ of $G$ is a
V-separator of $G$, that $G_{C}$ is the subgraph of $G$ bounded by $C$, and
$u$ is the sink of $C$. Let the distance of $u$ from the root $r$ be $\ell$,
so $\lambda[G](u)=\ell$, and the maximum distance from a vertex of $C$ to $r$
be $m\geq\ell+2$. Let $U:=V(G_{C})\setminus V(C)$ be the interior vertices of
$C$, and denote by $W:=V(G)\setminus(V(C)\cup U)$ the set of the “remaining”
vertices.

Then there exists a bi-level-respecting partial contraction sequence of $G$
which contracts only pairs of vertices that are in or stem from $U$, results
in a trigraph $G^{*}$, and satisfies the following conditions for every
trigraph $G^{\prime}$ along this sequence from $G$ to $G^{*}$:

  1. (I)’

For $U^{\prime}:=V(G^{\prime})\setminus(V(C)\cup W)$ (which are the vertices
that are in or stem from $U$ in $G^{\prime}$), every vertex of $U^{\prime}$ in
$G^{\prime}$ has red degree at most $6$,

  2. (II)’

every vertex of the left path of $C$ has at most $4$ red neighbours and every
vertex of the right path of $C$ has at most $1$ red neighbour in $U^{\prime}$,

  3. (III)’

the sink $u$ of $C$ has no red neighbour in $U^{\prime}$,

  4. (IV)’

if the next step of the sequence is going to contract a pair $x,y\in
U^{\prime}$ such that $\lambda[G^{\prime}](y)>\lambda[G^{\prime}](x)$, then
$y$ has no neighbour in the right path of $C$, and

  5. (V)’

at the end of the partial contraction sequence, for the set
$U^{*}:=V(G^{*})\setminus(V(C)\cup W)$ that stems from $U$ in $G^{*}$, we have
that if $z\in U^{*}$ is of level $i$, then $\ell<i\leq m+1$ and $z$ is the
only vertex in $U^{*}$ of level $i$.

$r$$v_{1}$$v_{2}$$\leavevmode\nobreak\ {u}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$C\quad$$U$$f$$W$ $\leadsto$
$r$$v_{1}$$v_{2}$$\leavevmode\nobreak\ {u}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$U^{*}$$W$$(\leq\\!6)$$(\leq\\!4)$$(\leq\\!1)$
Figure 4: (left) The setup of Lemma 4.1, where $P_{1}$ and $P_{2}$ are the
left and right paths of the chosen V-separator $C$. (right) The outcome of the
claimed partial contraction sequence which contracts only vertices of $U$
inside the shaded region from the left, and which maintains bounded red
degrees in the region and on its boundary $C$.

We illustrate Lemma 4.1 in Figure 4. We also observe that the assumptions and
conditions of Lemma 4.1 imply the next properties useful for the coming
proofs, similarly as in 3.

######  Claim 6.

Respecting the notation and assumptions of Lemma 4.1, we also have that:

  1. (VI)’

Every red edge in $G^{\prime}$ has one end in $U^{\prime}$ and the other end
in $U^{\prime}\cup V(C)$,

  2. (VII)’

if $P_{1}$ and $P_{2}$ are the left and right paths of $C$, respectively, and
$v\in V(P_{2})$ is of level $j$ in $G^{\prime}$, then there is no edge of
$G^{\prime}$ (red or black) from $v$ to a vertex of
$U^{\prime}\cup(V(P_{1})\setminus\\{u\\})$ of level $j-1$ in $G^{\prime}$.

The proof of (VI)’ is the same as in 3 before. Concerning (VII)’, it is again
the same argument with the left-aligned property as before, except that we use
the condition (IV)’ in addition to the definition of a bi-level-respecting
contraction.

Lemma 4.1 already easily implies the first part of Theorem 1.2:

######  Proof 4.2 (Proof of Theorem 1.2 (the upper bound)).

We start with a given simple planar graph $H$, and extend any plane embedding
of $H$ into a simple plane quadrangulation $G$ such that $H$ is an induced
subgraph of $G$ (i.e., by adding vertices). Then we choose a root $r$ on the
outer face of $G$ and, for some left-aligned BFS tree of $G$ rooted in $r$
which exists by Lemma 2.1, the facial cycle $C$ of the outer face incident to
$r$, and $u=r$, we apply Lemma 4.1. Observe that this is sound since the
vertex of $C$ opposite to $r$ must have its (left-aligned) vertical path as
the left path of $C$.

This way we get a partial contraction sequence from $G$ to a trigraph $G^{*}$
of maximum red degree $6$ (along the sequence). Observe by (V)’ that the set
$U^{*}=V(G^{*})\setminus V(C)$ contains only three vertices, on levels $1$,
$2$ and $3$. In the final phase, we may hence pairwise contract the remaining
vertices in an arbitrary order and not exceed red degrees $6$. The restriction
of this whole contraction sequence of $G$ to only $V(H)$ then certifies that
the twin-width of $H$ is at most $6$.

###  4.2 Decomposing into subregions

$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}\leavevmode\nobreak\ $$\leavevmode\nobreak\
v_{4}$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$P_{3}$$C_{1}$$C_{2}$$f$$u_{3}$$f_{1}$$f_{2}$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}$$\leavevmode\nobreak\ v_{4}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$P_{3}$$C_{1}$$C_{2}$$f$$u_{3}$$f_{1}$$f_{2}$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u}$$v_{3}$$\leavevmode\nobreak\ v_{4}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$C_{1}$$f$$f_{1}$ Figure 5: Three schematic cases
of decomposing the drawing of $G_{C}$ into subregions (bounded by $C_{1}$ and
$C_{2}$) discussed in Section 4.2 and specifically in Lemma 4.3. They
generally cover all possibilities in which $v_{3},v_{4}\not\in V(P_{1}\cup
P_{2})$. Vertical positions of the vertices of the $4$-cycle
$A=(v_{1},v_{2},v_{3},v_{4})$ outline their levels in $G$. Note that, in the
right-most case, we have only one “nested” V-separator $C_{1}$, which is
however not equal to $C=(P_{1}\cup P_{2})+f$, but instead $C_{1}$ passes
through $v_{2},v_{3},v_{4},v_{1}$ and has the lid edge
$f_{1}=\\{v_{3},v_{4}\\}$.

We assume the setting of Lemma 4.1. So, let $C$ be a V-separator in the plane
quadrangulation $G$, formed by the left path $P_{1}$, the right path $P_{2}$
and the lid edge $f=\\{v_{1},v_{2}\\}$ where $v_{i}$ is an end of $P_{i}$. Let
$G_{C}$ be the subgraph bounded by $C$ and $U:=V(G_{C})\setminus V(C)$.
Moreover, let $A\subseteq G_{C}$ denote the cycle bounding the $4$-face
incident to the edge $f$ and drawn in the closed disk of $C$. The vertices of
$A$ are $(v_{1},v_{2},v_{3},v_{4})$ in this counter-clockwise order, and the
vertices $v_{3},v_{4}$ may or may not lie on $C$.

First, observe that since $G$ is bipartite, we have
$\lambda[G](v_{2})\not=\lambda[G](v_{1})$, and hence
$\lambda[G](v_{1})=\lambda[G](v_{2})+1$ by the left-aligned property. For the
same reasons, $\lambda[G](v_{3})=\lambda[G](v_{2})+1=\lambda[G](v_{1})$ unless
$v_{3}\in V(P_{2})$, and finally
$\lambda[G](v_{4})\in\big{\\{}\lambda[G](v_{1})-1,\lambda[G](v_{1})+1\big{\\}}$.
Analogously to Section 3.2, we are going to use vertical paths of $G$ starting
in $v_{3}$ and $v_{4}$ for “subdividing” the case of $G_{C}$ into subcases to
be solved inductively, but we first show that, actually, only one such
vertical path is relevant in any case. See also Figure 5.

######  Lemma 4.3.

Assume the setting of Lemma 4.1, and with respect to it, let $U\not=\emptyset$
and $A\subseteq G_{C}$, $A=(v_{1},v_{2},v_{3},v_{4})$, denote the cycle
bounding the $4$-face incident to the lid edge $f$ of the V-separator $C$ and
drawn in the closed disk of $C$.

a) There exists a vertical path $P_{3}\subseteq G_{C}$ (internally disjoint
from $C\cup A$ and possibly empty) such that the plane subgraph $C\cup A\cup
P_{3}$ has two (if $P_{3}=\emptyset$) or three distinct bounded faces, one of
them being the face of $A$. The one or two bounded faces of $C\cup A\cup
P_{3}$ other than that of $A$ are bounded by cycles $C_{1}$ and $C_{2}$, where
$v_{1}\in V(C_{1})$, and each of $C_{1}$ and $C_{2}$ (or just $C_{1}$ if
$P_{3}=\emptyset$) is again a V-separator whose lid edge is from
$E(A)\setminus\\{f\\}$.

b) Assume now that $C\cup A\cup P_{3}$ has three bounded faces. Then
$C_{1}\cap C_{2}=P_{3}$, and the sinks of $C_{1}$ and $C_{2}$ are in some
order the sink $u$ of $C$ and the end $u_{3}$ of $P_{3}$ not in $A$ (which may
be the same vertex). If $\tau_{i}$, $i=1,2$, is the bi-level-respecting
partial contraction sequence of $G$ obtained by inductively applying Lemma 4.1
to the cycle $C_{i}$, then the concatenation
$\sigma_{0}:=\tau_{2}\cdot\tau_{1}$ of these two sequences is a bi-level-
respecting partial contraction sequence of $G$ which satisfies the properties
(I)’ to (IV)’ of Lemma 4.1.

######  Proof 4.4.

a) If $v_{4}\in V(P_{1})$, then $v_{3}\in V(P_{2})$ or
$\lambda[G](v_{4})=\lambda[G](v_{1})-1=\lambda[G](v_{3})-1$, and the vertical
path from $v_{3}$ in the latter case passes through $v_{4}$. Then we easily
conclude with $P_{3}=\emptyset$. If $v_{3}\in V(P_{2})$ and $v_{4}\not\in
V(P_{1})$, then $\lambda[G](v_{4})=\lambda[G](v_{1})-1$ again, and we take the
vertical path $P_{3}$ starting in $v_{4}$. For the rest of part (a) we assume
$v_{3},v_{4}\not\in V(C)$.

We start from the above observation that
$\lambda[G](v_{3})=\lambda[G](v_{1})=\lambda[G](v_{2})+1$ and
$\lambda[G](v_{4})\in\big{\\{}\lambda[G](v_{1})-1,\lambda[G](v_{1})+1\big{\\}}$.
If $\lambda[G](v_{4})=\lambda[G](v_{1})-1$, then the vertical path from
$v_{3}$ to the root $r$ must pass through $v_{4}$ by the left-aligned
property, and we take as $P_{3}$ the vertical (sub)path from $v_{4}$ to the
first vertex $u_{3}$ which is on $C$ (the leftmost case in Figure 5). In this
case, the lid edges are $f_{1}=\\{v_{1},v_{4}\\}$ for $C_{1}$ and
$f_{2}=\\{v_{3},v_{2}\\}$ for $C_{2}$.

If $\lambda[G](v_{4})=\lambda[G](v_{1})+1$, then the vertical path from
$v_{4}$ to the root passes through $v_{1}$ by the left-aligned property. So,
we again choose the vertical path from $v_{3}$, unless it passes through
$v_{2}$, and get a case with lid edges $f_{1}=\\{v_{3},v_{4}\\}$ for $C_{1}$
and $f_{2}=\\{v_{3},v_{2}\\}$ for $C_{2}$ (the middle case in Figure 5). If
the vertical path from $v_{3}$ passes through $v_{2}$, we have
$P_{3}=\emptyset$ and get $C_{1}$ with the lid edge $f_{1}=\\{v_{3},v_{4}\\}$.
We are finished with part (a).

b) This part is similar to the proof of Lemma 3.3, and actually easier that
that. Again, the concatenation $\sigma_{0}$ is well-founded thanks to (VI)’ of
6. Subsequently, the only vertices of $G_{C}$ possibly receiving red edges
from both sequences $\tau_{1}$ and $\tau_{2}$ are those of $P_{3}$. Validity
of the claimed properties (I)’, (II)’ and (III)’ of Lemma 4.1 for $\sigma_{0}$
thus follows from inductive invocations of the same properties for $\tau_{1}$
and $\tau_{2}$, except for the vertices of $P_{3}$. The end vertex of $P_{3}$
which is the sink of $C_{1}$ or $C_{2}$, however, also gets red edges from
only one of the sequences by (III)’. Finally, every vertex of
$V(P_{3})\setminus V(C)$ gets at most $1+4=5<6$ red neighbours by inductive
(II)’, and so it fulfills (I)’ easily.

Lastly, the property (IV)’ follows from an inductive invocation of (IV)’ for
$\tau_{1}$ and $\tau_{2}$, since every vertex of the right path of $C$ belongs
to the right path of $C_{2}$ or to the right path of $C_{1}$.

###  4.3 Finishing the proof

Now we get to the proof of Lemma 4.1 which will conclude Theorem 1.2.

######  Proof 4.5 (Proof of Lemma 4.1).

We first resolve the possible special cases. If $U=\emptyset$, we are
immediately done with the empty partial contraction sequence. So, assume
$U\not=\emptyset$.

We invoke Lemma 4.3, and first assume that $C_{2}$ does not exist there, i.e.,
that $P_{3}=\emptyset$. Let $\sigma_{0}$ be the bi-level-respecting partial
contraction sequence of $G$ obtained by inductively applying Lemma 4.1 to the
cycle $C_{1}$, and resulting in the trigraph $G^{0}$. Then $\sigma_{0}$ easily
satisfies the properties (I)’, (II)’ and (III)’ of Lemma 4.1 also for the
cycle $C$ of $G_{C}$. Recall from Lemma 4.1 that $\lambda[G](u)=\ell$ and that
$\max_{v\in V(C)}\lambda[G](v)=m$, and observe that $\max_{v\in
V(C_{1})}\lambda[G](v)\leq m+1$ where the upper bound can be attained if
$\lambda[G](v_{4})=m+1$. Let $U^{0}$ be the vertices of $G^{0}$ that stem by
contractions along $\sigma_{0}$ from $U$, which are of levels up to $m+2$ in
$G^{0}$ by an inductive invocation of (V)’. There are also up to two vertices
of $U\cap V(C_{1})=V(C_{1})\setminus V(C)$ in $G^{0}$, and as previously
discussed, they are of levels $m$ and $m+1$ in $G$.

We finish this case by contracting each of the possible (two) vertices of
$U\cap V(C_{1})$ with the vertex of $U^{0}$ of the same level, which satisfies
the claimed properties as well. Finally, if there is a vertex $x\in U^{0}$
such that $\lambda[G^{0}](x)=m+2$, then we contract $x$ with the vertex of
$U^{0}$ of level $m$. This is fine with respect to (IV)’ since $x$ has no edge
to $C$ due to its level, and this contraction does not violate (III)’ either
since $m\geq\ell+2$. We are done in this special case.

We are hence in the case of Lemma 4.3(b); such that the V-separators $C_{1}$
and $C_{2}$ in $G_{C}$ exist as claimed, and $C_{1}\cap
C_{2}=P_{3}\not=\emptyset$ where $P_{3}$ starts in
$w_{3}\in\\{v_{3},v_{4}\\}$. From this we get the claimed bi-level-respecting
partial contraction sequence $\sigma_{0}$ of $G$ which results in the trigraph
$G^{0}$, and set $U^{0}:=V(G^{0})\setminus(V(C)\cup W)$. Note that $U^{0}$
possibly contains $v_{3}$ or $v_{4}$, cf. Figure 5. Let $Q_{2}$ denote the
right path of $C_{2}$ where $Q_{2}\subseteq P_{2}$, and $u_{3}$ be the end of
$P_{3}$ on $C$, that is $V(P_{3})\cap V(C)=\\{u_{3}\\}$ and $u_{3}$ is the
sink of $C_{1}$ or $C_{2}$. Let similarly $Q_{1}$ denote the left path of
$C_{1}$ where $Q_{1}$ is “nearly” contained in $P_{1}$, except that $Q_{1}$
possibly includes the vertex $v_{4}\not=w_{3}$ (the middle case in Figure 5).
The right path of $C_{1}$, as well as the left path of $C_{2}$, are formed by
$Q_{3}:=P_{3}$ (or $Q_{3}:=P_{3}+v_{3}$ for $C_{2}$ in the leftmost case of
Figure 5) and possibly the subpath of $C$ from $u_{3}$ to $u$ (if
$u_{3}\not=u$).

Furthermore, let $U^{0}_{1},U^{0}_{2}\subseteq U^{0}$ denote the subsets that
stem by contractions of the interior vertices of $C_{1}$ and $C_{2}$,
respectively, along the sequence $\sigma_{0}$, and recall the property (V)’.
Let $\lambda[G^{0}](w_{3})=m^{\prime}$. As already observed,
$m^{\prime}=\lambda[G](v_{1})=m$, or $m^{\prime}=m-1$ if $w_{3}=v_{4}$. Let a
partial contraction sequence $\sigma_{2}$ be defined, for
$j=m^{\prime},m^{\prime}-1,\ldots,\lambda[G^{\prime}](u_{3})+1$, by
contracting the up to two vertices of $U^{0}_{2}\cup V(Q_{3})$ on the level
$j$, and let $U^{2}_{2}$ denote the set of vertices that stem from the steps
of $\sigma_{2}$. Subsequently, a sequence $\sigma_{3}$ is defined, for
$j=m^{\prime}+1,m^{\prime},\ldots,\lambda[G^{\prime}](u_{3})+1$, as follows.
If $j=m^{\prime}+1$, then we contract a possible (single) vertex of
$U^{0}_{2}$ of level $m^{\prime}+1$ with the vertex of $U^{0}_{1}$ of the same
level. If $j\leq m^{\prime}$, then we contract the up to two vertices of
$U^{2}_{2}\cup U^{0}_{1}$ on the level $j$. Let $U^{3}_{1}$ denote the set of
vertices that stem from the steps of $\sigma_{3}$. Finally, if $v_{4}\in
V(Q_{1})$, and so $\lambda[G^{0}](v_{4})=m+1=m^{\prime}+1$, then a sequence
$\sigma_{3}^{\prime}$ contracts $v_{4}$ with the resulting vertex of
$\sigma_{3}$ on the level $m^{\prime}+1$, and then it contracts the possible
vertex of $U^{0}_{1}$ of level $m+2$ (which thus cannot be adjacent to $C$)
with the resulting vertex of $\sigma_{3}$ on the level $m$. Otherwise, we let
$\sigma_{3}^{\prime}=\emptyset$.

We take the concatenated sequence
$\sigma:=\sigma_{0}\cdot\sigma_{2}\cdot\sigma_{3}\cdot\sigma_{3}^{\prime}$
which now satisfies the property (V)’ for the resulting trigraph $G^{*}$ and
the interior vertices $U^{*}$ of $C$ in it. It thus remains to verify the
properties (I)’ to (IV)’ of Lemma 4.1 along the sequence $\sigma$ from $G^{0}$
to $G^{*}$, that is, for every trigraph $G^{\prime}$ specifically along
$\sigma_{2}\cdot\sigma_{3}\cdot\sigma_{3}^{\prime}$.

Verification of (IV)’ is immediate since the only possible contraction not
preserving the levels has been that in $\sigma_{3}^{\prime}$ of level $m+2$,
the vertex of which has got no neighbour on $C$. Likewise, verification of
(III)’ is easy since every vertex of $U^{0}$ on the level $\ell+1$ has a
neigbour of level $\ell$ by 5, and the only such possible neighbour is the
sink $u$ by planarity, which is moreover a black neighbour in $G^{0}$ by an
inductive invocation of (III)’. Since no vertex of level higher than $\ell+1$
is contracted into the level $\ell+1$ along $\sigma$, the resulting single
vertex of $U^{*}$ of level $\ell+1$ is a black neighbour of $u$.

Consider now the property (II)’ for $G^{\prime}$. Let $x\in V(P_{2})$ be from
the right path of $C$, and $\lambda[G](x)=k$. By 5, $x$ can have red
neighbours in $G^{\prime}$ only on the levels $k-1$ and $k+1$, but (VII)’ of 6
excludes the former possibility. On the level $k+1$, there is (always along
the sequence) only one potential red neighbour of $x$, which is from
$U^{0}_{2}$ at the beginning of $\sigma_{2}$, then later from $U^{2}_{2}$, and
during $\sigma_{3}$ it becomes a vertex of $U^{3}_{1}$, but there are never
two such vertices at the same stage of $\sigma$. Let $x\in V(P_{1})$ be from
the left path of $C$, and again $\lambda[G](x)=k$. Then the potential red
neighbours of $x$ in $G^{\prime}$ are on the levels $k-1$ and $k+1$, and there
are clearly at most two such on each level among the interior vertices of $C$
in $G^{\prime}$, altogether fulfilling the claimed bound of $4$.

Finally, consider the property (I)’ for $G^{\prime}$. We first assume that the
trigraph $G^{\prime}$ results along the subsequence
$\sigma_{2}\cdot\sigma_{3}$ (i.e., before $\sigma_{3}^{\prime}$). Denote by
$U^{\prime}:=V(G^{\prime})\setminus(V(C)\cup W)$ the set of all interior
vertices of $C$ in $G^{\prime}$, and pick $x\in U^{\prime}$ such that
$\lambda[G^{\prime}](x)=k$. By 5, red neighbours of $x$ belong only to levels
$k-1$ and $k+1$. The neighbours of $x$ on the level $k+1$ may be one in
$V(Q_{1})$, up to three in $U^{\prime}$, but none in $V(P_{2})$ by (VII)’.
However, if there are all three vertices in $U^{\prime}$ of level $k+1$, then
the contraction sequence has not yet touched the level $k+1$, and then $x$
cannot be adjacent to all three in $U^{\prime}$ of level $k+1$ anyway, by
planarity. The conclusion is that $x$ at any considered stage has at most $3$
red neighbours of level $k+1$. Thus, whenever $x$ has at most $3$ red
neighbours of level $k-1$, we will be done.

Let us now look closer at potential red neighbours of $x$ of level $k-1$. If
there has not been a $\sigma_{2}$-contraction on the level $k$ yet, i.e. when
$x\in U^{0}_{2}\cup V(Q_{3})\cup U^{0}_{1}$, then the bound of at most $3$ red
neighbours of level $k-1$ holds trivially. The same holds if $\sigma_{2}$ has
already contracted on the level $k$ in $G^{\prime}$, and $x\in U^{0}_{1}$ has
not participated in this contraction. Assume now that $x\in U^{2}_{2}$,
meaning that $x$ has been contracted in $\sigma_{2}$ from a pair of vertices
$x_{2}\in U^{0}_{2}$ and $x_{3}\in V(Q_{3})$ of level $k$ in $G^{0}$. Then $x$
may have up to $3$ red neighbours in $V(P_{2})\cup U^{0}_{2}\cup U^{2}_{2}\cup
V(Q_{3})$. However, $x$ in such case is not adjacent to the subset $Y\subseteq
U^{0}_{1}\cup V(Q_{1})$ of the vertices (up to two) of level $k-1$. This is
since $x_{2}$ is not adjacent to $Y$ in $G^{0}$ by planarity, and $x_{3}$ is
not adjacent to $Y$ in $G^{0}$ by an inductive invocation of (VII)’ for
$C_{1}$. So, the case of $x\in U^{2}_{2}$ is also fine.

Finally, we may have $x\in U^{3}_{1}$, meaning that $x$ has already been
contracted in $\sigma_{3}$. Then $x$ may have up to $4$ red neighbours on the
level $k-1$, in $V(P_{2})\cup U^{2}_{2}\cup U^{0}_{1}\cup V(Q_{1})$.
Fortunately, in this case $x$ has at most $2$ red neighbours on the level
$k+1$, in $U^{3}_{1}\cup V(Q_{1})$. This again satisfies the property (I)’ for
$G^{\prime}$.

The proof is finished by observing that neither the last sequence
$\sigma_{3}^{\prime}$, if nonempty, violates (I)’.

######  Proof 4.6 (Proof of Theorem 1.2 (the algorithmic part)).

We can construct a simple plane quadrangulation $G\supseteq H$ in linear time
using standard planarity algorithms. Then we continue (in linear time) the
same way as in the proof of Theorem 1.1.

##  5 Conclusion

We have further improved by one the previous best upper bound [5] on the twin-
width of planar graphs. This seemingly small improvement has required a
careful reconsideration of the previous method and several new ideas, and
although our new approach has simplified some cumbersome technical details in
[5], new technical difficulties emerged which makes some parts of the proof
again quite technical. This is probably to be expected since we are now very
close to the currently best lower bound of $7$ on the twin-width of planar
graphs [7].

To conclude, the problem to determine the exact maximum value of the twin-
width over all planar graphs is still open, and we have no good guess about
which of the two possible values, $7$ or $8$, is the right answer.

Furthermore, [5] has also proved an upper bound of $6$ on the twin-width of
bipartite planar graphs. Some of the new ideas of this paper may be used to
significantly simplify the previous proof from [5], but unfortunately, we are
currently not able to improve the bound of $6$ for bipartite planar graphs
further down. Again, we have no good guess about whether the value of $6$ is
the right maximum value over bipartite planar graphs, or whether the upper
bound may possibly be $5$.

## References

  * [1] Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann.  Graph product structure for h-framed graphs.  CoRR, abs/2204.11495, 2022.  Accepted to ISAAC 2022.  arXiv:2204.11495v1.
  * [2] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  J. ACM, 69(1):3:1–3:46, 2022.
  * [3] Édouard Bonnet, O-joung Kwon, and David R. Wood.  Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond).  CoRR, abs/2202.11858, 2022.  arXiv:2202.11858.
  * [4] Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood.  Planar graphs have bounded queue-number.  J. ACM, 67(4):22:1–22:38, 2020.
  * [5] Petr Hliněný.  Twin-width of planar graphs is at most 9, and at most 6 when bipartite planar.  CoRR, abs/2205.05378, 2022.  arXiv:2205.05378.
  * [6] Hugo Jacob and Marcin Pilipczuk.  Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs.  CoRR, abs/2201.09749, 2022.  Accepted to WG 2022.  arXiv:2201.09749.
  * [7] Daniel Král and Ander Lamaison.  Planar graph with twin-width seven.  CoRR, abs/2209.11537, 2022.  arXiv:2209.11537.