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

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

Petr Hliněný

###### 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], $583$ by Bonnet et al. [arXiv, February 2022], and of
$37$ by Bekos et al. [arXiv, April 2022]. We prove that the twin-width of
planar graphs is at most $9$. Furthermore, if a planar graph is also
bipartite, then its twin-width 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 we then
naturally speak about _red neighbours_ and _red degree_ in $G$. 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 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 [5], $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 [5, 3, 1], more or less
explicitly, use the product structure machinery of planar graphs (cf. [4]). We
give the following improved bounds on the twin-width of planar graphs:

######  Theorem 1.1.

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

######  Theorem 1.2.

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

Our proofs do not use the product structure machinery, but another recursive
decomposition of planar graphs which is fine-tuned for the purpose of
obtaining the results.

##  2 Proving the bound for general planar graphs

We start with a few technical definitions needed for the proof of Theorem 1.1.

Let $G$ be a 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\in V(G)$ 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 vertical (wrt. implicit
$T$) if $P$ is a subpath of some root-to-leaf path of $T$. Notice that a
vertical path is $r$-geodesic, but the converse may not be true.

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}$.

Consider a BFS layering ${\cal L}$ of $G$ as above. 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. Such a
sequence is _${\cal L}$ -respecting_ if every step contracts only pairs
belonging to $L_{j}\in{\cal L}$ for some $j$. For reference, when $G^{\prime}$
is a trigraph resulting from an ${\cal L}$-respecting partial contraction
sequence of $G$, we will write $L_{j}[G^{\prime}]$ for the vertex set that
stems from $L_{j}$ by these contractions (hence, $L_{j}=L_{j}[G]$).

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$.

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)$, $uv\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$).

######  Claim 2.

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.

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$).

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. It is
easy to turn any planar graph into a simple plane triangulation by adding
vertices and incident edes into each non-triangular face. Furthermore, twin-
width is non-increasing when taking induced subgraphs, and so it suffices to
focus on plane triangulations when stating the following core lemma:

######  Lemma 2.1.

Let $G$ be a 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
BFS layering ${\cal L}=(L_{0}=\\{r\\},L_{1},L_{2},\ldots)$ of $G$. Assume that
$P_{i}$, $i=1,2$, are two edge-disjoint vertical paths of $G$ of lengths at
least $1$, where $P_{i}$ has the ends $u_{i}$ and $v_{i}$ such that
$u_{1}=u_{2}\in L_{\ell}$ is the vertex of $P_{1}\cup P_{2}$ closest to $r$
(i.e., at distance $\ell$ from $r$), and $f=\\{v_{1},v_{2}\\}\in E(G)$ is an
edge such that $v_{1}$ is to the left of $v_{2}$. Then $C:=(P_{1}\cup
P_{2})+f$ is a cycle of $G$, and let $G_{C}$ be the subgraph of $G$ bounded by
$C$, let $U:=V(G_{C})\setminus V(C)$ and $W:=V(G)\setminus V(G_{C})$ (so,
$V(G)$ is tri-partitioned into $U$, $W$ and $V(C)$, and $U\cap
L_{j}=\emptyset$ for all $j\leq\ell$).

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

  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 $9$,

  2. (II)

the vertex $u_{1}$ of $P_{1}\cap P_{2}$ has no red neighbour in $U^{\prime}$,
every vertex of $P_{1}-u_{1}$ has at most $5$ red neighbours in $U^{\prime}$,
every vertex of $P_{2}-u_{1}$ has at most $3$ red neighbours in $U^{\prime}$
except the neighbour of $u_{1}$ on $P_{2}$ which may have up to $4$ red
neighbours in $U^{\prime}$, and

  3. (III)

at the end of the partial sequence, that is for
$U^{0}:=V(G^{0})\setminus(V(C)\cup W)$, we have $\big{|}U^{0}\cap
L_{\ell+1}[G^{0}]\big{|}\leq 2$ and $\big{|}U^{0}\cap L_{j}[G^{0}]\big{|}\leq
1$ for all $j>\ell+1$.

$r$$v_{1}$$v_{2}$$\leavevmode\nobreak\
{u_{1}=u_{2}}$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$C\quad$$U$$f$$W$ $\leadsto$ $r$$v_{1}$$v_{2}$$\leavevmode\nobreak\
{u_{1}=u_{2}}$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$U^{0}$$W$$(\leq\\!9)$$(\leq\\!5)$$(\leq\\!4)$$(\leq\\!3)$
Figure 1: (left) The setup of Lemma 2.1, where $v_{1}$ is to the left of
$v_{2}$. (right) The outcome of the claimed partial contraction sequence which
contracts only vertices of $U$ inside the shaded region from the left and
maintains bounded red degrees in the region and on its boundary $C$ formed by
$P_{1}$ and $P_{2}$ and $f$. Not all depicted red edges really exist, and some
of them may actually be black.

Before proceeding further, we comment on two important things. First, the
possible case of $\big{|}U^{0}\cap L_{\ell+1}[G^{0}]\big{|}=2$ in (III) of
Lemma 2.1 is unavoidable since a contraction of this pair could result in a
red edge from $u_{1}$ which must be forbidden in the induction. Second, we
remark that, in Lemma 2.1, all vertices of $U$ have distance from $r$ greater
than $\ell$, but also the distance from $r$ of some vertices in $U$ may be
greater than the distance from $r$ to $v_{1}$ or $v_{2}$ (and our coming proof
is aware of this possibility). We illustrate Lemma 2.1 in Figure 1.

We also observe that the assumptions of Lemma 2.1 directly imply some other
properties useful for the proof of Lemma 2.1.

######  Claim 3.

Within the notation and assumptions of Lemma 2.1, for $G^{\prime}$ we also
have that:

  1. (IV)

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

  2. (V)

if $v\in V(P_{2})\cap L_{j}[G^{\prime}]$, then there is no edge in
$G^{\prime}$ (red or black) from $v$ to a vertex of $(U^{\prime}\cup
V(P_{1}))\cap L_{j-1}[G^{\prime}]$.

Regarding (IV), 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, due to the cycle $C$ in the plane graph $G$, no
vertex of $W$ is adjacent to a vertex of $U$ in $G$, and so the same holds in
$G$. Then no vertex of $W$ is ever adjacent to a vertex being contracted in
our sequence from $G$ to $G^{0}$ (which includes $G^{\prime}$).

Concerning (V), if $v$ was adjacent to $x^{\prime}\in U^{\prime}\cap
L_{j-1}[G^{\prime}]$, then, among the vertices of $U\cap L_{j-1}$ contracted
into $x^{\prime}$, there had to be a neighbour $x\in U\cap L_{j-1}$ of $v$ in
$G$, and so also $xv\in E(G)$. Then $x$ was to the left of $v$ in $G$ by the
definition of $U$, which contradicts the assumption that $T$ is left-aligned.

######  Claim 4.

With the notation and assumptions of Lemma 2.1, we have that if (III) is true,
then (II) and (I) except the condition on $u_{1}$ are also true for
$G^{\prime}=G^{0}$.

Every vertex of $P_{1}-u_{1}$ may have red neighbours only in $U^{0}$ by (IV),
and by (III) and 1 there are at most $2+1+1=4$ such potential neighbours
(layer by layer, and this can be improved further). Likewise, every vertex of
$P_{2}-u_{1}$ may have red neighbours only in $U^{0}$, and using additionally
(V), there are at most $2+1=3$ such potential neighbours. For every vertex of
$U^{0}$, we have at most $4+2+3=9$ such potential neighbours simply by (III)
and 1 (again layer by layer, and the bound can be improved further).

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

######  Proof 2.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 at $r$ which exists by 2, and the
paths $P_{1}$ and $P_{2}$ formed by each of the two edges of the outer face
incident to $r$, apply Lemma 2.1. This way we get a partial contraction
sequence from $G$ to a trigraph $G^{0}$ of maximum red degree $9$ (along the
sequence). Observe that $L_{0}[G^{0}]=\\{r\\}$ and $L_{1}[G^{0}]$ contains the
two vertices of the outer face other than $r$ and at most two vertices of
$U^{0}$ by (III). For all $j\geq 2$, we have $\big{|}L_{j}[G^{0}]\big{|}\leq
1$ again by (III).

In the final phase, we pairwise contract the at most $4$ vertices of
$L_{1}[G^{0}]$ into one vertex, making $G^{0}$ into a path by 1, and then
naturally contract this path down to a vertex, never exceeding red degree
$5<9$ along this final phase. The restriction of the whole contraction
sequence of $G$ to $V(H)$ then certifies that the twin-width of $H$ is at most
$9$, too.

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

######  Proof 2.3 (Proof of Lemma 2.1).

We first resolve several possible degenerate 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
$P_{1}$ and $P_{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 2.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$ where, by $r\not\in U$
and planarity of $G$, we have $u_{1}\in V(P)$. If $v_{1}\in V(P)$, then we
(similarly as above) apply Lemma 2.1 inductively to $P$ and $P_{2}$, while the
rest of the assumptions again remain the same. In the resulting trigraph
$G^{1}$, assuming $v_{3}\in L_{j}$ (note that $j\geq\ell+2$) and $L_{j}\cap
U\not=\\{v_{3}\\}$ at the beginning, we then contract $v_{3}$ with the (unique
by (III)) vertex of $L_{j}[G^{1}]\cap U^{1}$ where
$U^{1}:=V(G^{1})\setminus(V(P\cup P_{2})\cup W)$. This is correct by 4.

In all other cases we continue as follows. See in Figure 2.

$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u_{1}=u_{2}}$$v_{3}$$\leavevmode\nobreak\ u_{3}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$P_{3}$$U_{1}$$U_{2}$$C_{2}$$C_{1}$ $\leadsto$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u_{1}=u_{2}}$$v_{3}$$\leavevmode\nobreak\ u_{3}$$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\ P_{2}$$P_{3}$$U^{2}_{1}$$U^{2}_{2}$ Figure 2: (left)
The setup of the main induction step in the proof of Lemma 2.1 (another
possibilities are that $u_{3}$ lies on $P_{1}$, or is equal to $u_{1}$).
(right) A schematic outcome of the recursive application of Lemma 2.1 to each
of the cycles $C_{1}$ and $C_{2}$. Note that the only vertices that have
neighbours in both contracted subsets $U_{1}^{2}$ and $U_{2}^{2}$ are those of
$P_{3}$, and among them only $u_{3}$ has possibly neighbours not explicitly
mentioned in this picture, that is, neighbours not in $V(P_{1}\cup P_{2}\cup
P_{3})$ and not among the vertices that stem from $U_{1}\cup U_{2}$.

Observe that $v_{3}$ is to the left of $v_{2}$, and $v_{1}$ is to the left of
$v_{3}$. 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$. Assuming
$u_{3}\in V(P_{k})$ for $k\in\\{1,2\\}$ (and the following is sound even if
$u_{3}=u_{1}\in V(P_{1})\cap V(P_{2})$ ), let $P_{k}^{-}$ be the subpath of
$P_{k}$ from $v_{k}$ to $u_{3}$, and $P_{3}^{+}\subseteq P$ be the subpath of
$P$ from $v_{3}$ to $u_{1}$ (which is the union of $P_{3}$ with the subpath of
$P_{k}$ from $u_{3}$ to $u_{1}$).

We have got two cycles $C_{1},C_{2}\subseteq G$, namely $C_{k}:=(P_{k}^{-}\cup
P_{3})+\\{v_{k},v_{3}\\}$ and $C_{3-k}:=(P_{3-k}\cup
P_{3}^{+})+\\{v_{3-k},v_{3}\\}$. For $i=1,2$, we denote by $U_{i}\subseteq U$
the set of vertices drawn in the interior of $C_{i}$. Note that $U$ is tri-
partitioned into $U_{1}$, $U_{2}$ and $V(P_{3})\setminus\\{u_{3}\\}$. We apply
Lemma 2.1 inductively to each of the cycles $C_{1}$ and $C_{2}$. This is sound
by the following:

  * •

Each of the paths $P_{3}$, $P_{3}^{+}$ and $P_{k}^{-}$ is vertical wrt. $T$
(as a subpath of other vertical path). Furthermore, $V(P_{k}^{-})\cap
V(P_{3})=\\{u_{3}\\}$ and $V(P_{3-k})\cap V(P_{3}^{+})=\\{u_{1}\\}$.

  * •

We get that each of the vertical paths $P_{k}^{-}$, $P_{3}$ and $P_{3}^{+}$ is
of length at least $1$, and it is possible to apply Lemma 2.1 to both $C_{1}$
and $C_{2}$ independently and concurrently.

  * •

Since $v_{3}\in U$ belongs to neither of $U_{1},U_{2}$, we always have
$|U_{1}|+|U_{2}|<|U|$.

This way we get ${\cal L}$-respecting partial contraction sequences $\tau_{1}$
(for $C_{1}$ contracting in $U_{1}$) and $\tau_{2}$ (for $C_{2}$ contracting
in $U_{2}$) of $G$. These sequences are independent in the sense that no
contraction pair in $U_{1}$ creates a red edge incident to a vertex of $U_{2}$
by inductive invocation of condition (IV), and vice versa. We may thus append
$\tau_{2}$ after $\tau_{1}$, as the concatenation $\tau:=\tau_{1}.\tau_{2}$,
such that $\tau$ is a valid ${\cal L}$-respecting partial contraction sequence
of $G$ resulting in a trigraph $G^{2}$. At every step of $\tau$, each vertex
that stems from $U_{1}$ or $U_{2}$ is of red degree at most $9$ by inductive
invocation of condition (I). Furthermore, by (II), each vertex of
$V(P_{3})\setminus\\{u_{3}\\}$ is of red degree at most $5+4=9$ at every step
of $\tau$. This fulfills (I) for $\tau$.

Concerning (II), the property is inherited for $\tau$ from its recursive
application to one of $\tau_{1}$ or $\tau_{2}$, using also (IV), for every
vertex of $P_{1}\cup P_{2}$ (including for $u_{1}$), except possibly for
$u_{3}$ which belongs to both bounding cycles $C_{1}$ and $C_{2}$. However,
condition (II) of $u_{3}$ from the recursive application to $\tau_{k}$ claims
that there are no red edges created from $u_{3}$ to vertices that stem from
$U_{k}$, and so (II) is inherited also for the vertex $u_{3}$ from its
application to $\tau_{3-k}$. Condition (III) is void for this intermediate
sequence $\tau$.

We are going to continue with ${\cal L}$-respecting partial contraction
sequences $(\tau_{0}.\tau_{3})$ from $G^{2}$ to $G^{3}$, then $\tau_{4}$ from
$G^{3}$ to $G^{4}$ and (possibly empty) $\tau_{5}$ from $G^{4}$ to $G^{5}$,
such that the concatenation $(\tau.\tau_{0}.\tau_{3}.\tau_{4}.\tau_{5})$
fulfills all conditions of Lemma 2.1 for the cycle $C$. For $i=1,2$, denote by
$U_{i}^{2}\subseteq V(G^{2})$ the set of vertices which stem from $U_{i}$ by
the sequence $\tau$. Recall that $u_{3}\in V(P_{k})$ where $k\in\\{1,2\\}$,
and let $a>\ell$ be such that $u_{3}\in L_{a-1}$. If $u_{3}=u_{1}$ or
$|L_{a}[G^{2}]\cap U_{k}^{2}|\leq 1$, then let $\tau_{0}=\emptyset$.
Otherwise, $a\geq\ell+2$ and the partial contraction sequence $\tau_{0}$ has
one step contracting the vertex pair $L_{a}[G^{2}]\cap U_{k}^{2}$.

The contraction in $\tau_{0}$ is safe under the stated conditions, as we now
show. First, if $k=1$, then $u_{3}$ actually has red degree at most $2+1+1=4$
in $G^{2}$ (counting BFS layers $L_{a-2}[G^{2}]$, $L_{a-1}[G^{2}]$ and
$L_{a}[G^{2}]$ among the vertices of $U_{2}^{2}$), and so $u_{3}$ may accept a
new red neighbour from this contraction while keeping (II) true. The red
degrees of all other affected vertices, including the contracted one, remain
good in $\tau_{0}$ by 4 (as applied to $C_{1}$). If $k=2$ and $a\geq\ell+3$,
then the situation is again good since, in $G^{2}$ before the $\tau_{0}$
contraction, the vertex $u_{3}\in L_{a-1}$ has at most $1+1=2$ red neighbours
in $\big{(}L_{a}[G^{2}]\cup L_{a-1}[G^{2}]\big{)}\cap U_{1}^{2}$ and no one in
$L_{a-2}[G^{2}]$ by (V) (as applied to the subcase of $C_{1}$), and so $u_{3}$
may accept a new red neighbour from the $\tau_{0}$ contraction while keeping
(II) true. If $a=\ell+2$, then we actually have $u_{3}\in L_{\ell+1}$, i.e.,
$u_{3}$ is the neighbour of $u_{1}$ on $P_{2}$. Then $u_{3}$ has at most $3$
red neighbours which all belong to $\big{(}L_{\ell+2}[G^{2}]\cup
L_{\ell+1}[G^{2}]\big{)}\cap U_{1}^{2}$, and by the special provision in (II)
$u_{3}$ may accept a fourth red neighbour from the $\tau_{0}$ contraction,
too.

Subsequently, the partial contraction sequence $\tau_{3}$ contracts vertex
pairs from $U_{2}^{2}\cup V(P_{3})\setminus\\{u_{3}\\}$ (but it possibly skips
some vertices which are close to $u_{1}$), the partial contraction sequence
$\tau_{4}$ contracts vertex pairs from $U_{1}^{2}\cup
V(P_{3})\setminus\\{u_{3}\\}$ (again possibly skipping some vertices which are
close to $u_{1}$), and the sequence $\tau_{5}$ then contracts pairs among the
possibly skipped vertices from $\tau_{3}$ and $\tau_{4}$.

We continue with the definition of $\tau_{3}$. Let
$d:=\max\\{i:(U_{2}^{2}\cup\\{v_{3}\\})\cap L_{i}[G^{2}]\not=\emptyset\\}$.
Let $G^{2}_{0}$ be the trigraph resulting from $\tau_{0}$ applied to $G^{2}$.
Note that, for $a\leq j\leq d$ we have $|L_{j}[G^{2}_{0}]\cap V(P_{3})|\leq
1$, and for $\ell+2\leq j\leq d$ we have $|L_{j}[G^{2}_{0}]\cap U_{1}^{2}|\leq
1$ and $|L_{j}[G^{2}_{0}]\cap U_{2}^{2}|\leq 1$. For
$j=d,d-1,\ldots,b=\max(\ell+3,a)$ in this order, $\tau_{3}$ contracts the pair
$L_{j}[G^{2}_{0}]\cap(U_{2}^{2}\cup V(P_{3}))$, or $\tau_{3}$ skips the step
if this set has at most $1$ vertex. That is all for $\tau_{3}$.

Let $G^{\prime\prime}$ be an (intermediate) trigraph along the sequence
$\tau_{3}$, and $U^{\prime\prime}:=V(G^{\prime\prime})\setminus(V(C)\cup W)$.
We now verify validity of conditions (II) and (I) for $G^{\prime\prime}$. This
is trivial for a vertex $x\in V(P_{2})$ since no new potential red neighbour
has been created along $\tau_{3}$. On the other hand, the case is more complex
for a vertex $x\in V(P_{1})$ since such $x$ may gain new red neighbours which
stem from $V(P_{3})\cup U_{2}^{2}$. However, assuming $x\in L_{c}$ and
$x\not=u_{3}$, there is no edge in $G$ from $L_{c+1}\cap V(P_{3})$ to $x$ by
(V), and also no such edge in $G^{2}_{0}$ from $L_{c+1}[G^{2}_{0}]\cap
U_{2}^{2}$ by planarity, and consequently, no new red edge to $x$ is created
by the $\tau_{3}$-contraction in layer $c+1$. If $x=u_{3}$, then the edge of
$P_{3}$ from $x=u_{3}$ turns red by the $\tau_{3}$-contraction in layer $c+1$,
but still $x$ has at most $3$ red neighbours in $(L_{c-1}[G^{2}_{0}]\cup
L_{c}[G^{2}_{0}])\cap U_{2}^{2}$ and at most $2$ in layer $c+1$ after this
contraction. Hence the situation is good if $\tau_{3}$ has not yet contracted
in layer $c$ in $G^{\prime\prime}$, and if a contraction in layer $c$ has
happened, then we know that $c\geq\ell+3$. In the latter case, in
$G^{\prime\prime}$ there are up to $3$ red neighbours of $x$ in $U_{1}^{2}$,
up to $2$ among the vertices that stem from $V(P_{3})\cup U_{2}^{2}$ and no
more, as needed in (II).

Among vertices $x\in U^{\prime\prime}$, the case is again trivial for $x\in
U_{1}^{2}$ since no new potential red neighbour of such $x$ has been created
along $\tau_{3}$. So, consider $x$ which is in or stems from $V(P_{3})\cup
U_{2}^{2}$, and assume that $x\in L_{c}[G^{\prime\prime}]$. Then, no matter of
where $G^{\prime\prime}$ is along the sequence, $x$ has at most $3$ red
neighbours in layer $c-1$ since one can be in $V(P_{2})\cap
L_{c-1}[G^{\prime\prime}]$ and at most two in $(U^{\prime\prime}\setminus
U_{1}^{2})\cap L_{c-1}[G^{\prime\prime}]$. There cannot be any neighbour of
$x$ in $(V(P_{1})\cup U_{1}^{2})\cap L_{c-1}[G^{\prime\prime}]$ because of
planarity and (V). Likewise, $x$ has at most $3$ red neighbours in layer $c$
simply since there are no more candidates in the layer. Regarding layer $c+1$,
again by (V), there cannot be a red edge from $x$ to $V(P_{2})\cap
L_{c+1}[G^{\prime\prime}]$. So, before $\tau_{3}$ contracts in layer $c+1$,
$x$ has at most two red neighbours there, and after that at most three such
(considering also a possible $\tau_{3}$-contraction in layer $c$). This sums
to at most $9$, as needed in (I).

We are done with the partial sequence $\tau_{3}$.

We continue with the definition of the partial contraction sequence $\tau_{4}$
starting from the trigraph $G^{3}$ which is the result of $\tau_{3}$. Denote
by $U_{2}^{3}$ the vertices of $G^{3}$ that stem from $V(P_{3})\cup U_{2}^{2}$
along $\tau_{3}$, and note that for $b\leq j\leq d$ we have $|L_{j}[G^{3}]\cap
U_{2}^{3}|\leq 1$. We intend to proceed similarly to the sequence $\tau_{3}$
(but with some changes caused by the fact that the paths $P_{1}$ and $P_{2}$
are not symmetric in our assumptions). Let analogously
$d^{\prime}:=\max\\{i:(U_{1}^{2}\cup\\{v_{3}\\})\cap
L_{i}[G^{3}]\not=\emptyset\\}$. For
$j=d^{\prime},d^{\prime}-1,\ldots,b=\max(\ell+3,a)$ in this order, $\tau_{4}$
contracts the pair $L_{j}[G^{3}]\cap(U_{1}^{2}\cup U_{2}^{3})$, or skips the
step if this set has at most $1$ vertex. This finishes $\tau_{4}$.

Let $G^{\prime\prime}$ now be an (intermediate) trigraph along the sequence
$\tau_{4}$, and $U^{\prime\prime}:=V(G^{\prime\prime})\setminus(V(C)\cup W)$.
We again verify validity of conditions (II) and (I) for $G^{\prime\prime}$.
This time the check is trivial for vertices $x\in V(P_{1})\cup V(P_{2})$ since
no new potential red neighbour (i.e., not counted in our previous arguments
along $\tau_{3}$) for them has been created along $\tau_{4}$. If $x\in
U^{\prime\prime}$ such that $x\in L_{c}[G^{\prime\prime}]$ and $c\leq b-1$,
then the argument of no new potential red neighbour also applies along
$\tau_{4}$.

Assume $x\in U^{\prime\prime}$ such that $x\in L_{c}[G^{\prime\prime}]$ and
$c>b$. If the partial contraction sequence $\tau_{4}$ has not yet reached
layer $c+1$, then the red neighbours of $x$ in $G^{\prime\prime}$ are as in
$G^{3}$, and so we assume that the $\tau_{4}$-contractions have already
reached layer $c+1$. Hence, $x$ has at most $2$ red neighbours in layer $c+1$
by (V), and since $\big{|}(V(C)\cup U^{\prime\prime})\cap
L_{i}[G^{\prime\prime}]\big{|}\leq 4$ for $i\geq c-1\geq b$ (even if
$\tau_{4}$-contractions have not yet reached layer $c$), $x$ has at most
$3+4=7$ red neighbours in layers $c$ and $c-1$, together at most $9$ as
desired. Special care has to be taken of the case $c=b$, in which $x$ may
potentially have up to $5$ red neighbours in layer $b-1\geq\ell+2$. If
$\tau_{4}$ is not at the end, i.e. the layer $c=b$ has not been contracted
yet, then $x\in U^{2}_{1}\cap L_{c}[G^{\prime\prime}]$ has no neighbour on
$P_{2}$ in layer $c-1$ by planarity, and $x\in U^{3}_{2}\cap
L_{c}[G^{\prime\prime}]$ has no neighbour on $P_{1}$ in layer $c-1$ by
planarity and (V) as applied during the sequence $\tau_{3}$. In both
possibilities of $x$ we thus get an upper bound of $2+3+4=9$. At the end of
$\tau_{4}$, $x$ has no other potential red neighbour in layer $c$ than the two
on $P_{1}$ and $P_{2}$, and we hence get $2+2+5=9$.

We are finished with the partial contraction sequence $\tau_{4}$.

To recapitulate, we have verified conditions (II) and (I) for the partial
contraction sequence $(\tau.\tau_{0}.\tau_{3}.\tau_{4})$, and we have also got
that condition (III) is true for all $j\geq b=\max(\ell+3,a)$. Furthermore,
(III) is true for all $j<a$ by the initial inductive application of Lemma 2.1
to one of $C_{1}$ or $C_{2}$ (precisely, to $C_{3-k}$). So, we are completely
done (with empty $\tau_{5}$) unless $a<b$, where the latter can happen (recall
our choice of $b$) only if $b\leq\ell+3$ and $a\leq\ell+2$. In other words,
either when $u_{3}=u_{1}$ or when $u_{3}$ is the neighbour of $u_{1}$ on
$P_{1}$ or on $P_{2}$. A straightforward case check reveals that there are
only three such cases depicted in Figure 3. If none of these happens, we
simply set $\tau_{5}=\emptyset$.

In the case (a) of Figure 3, $\tau_{5}$ contracts $x_{3}$ with $x_{4}$, and
then with $z$, which does not exceed red degrees $9$, specifically for the
vertex which stems from $x_{3}$ thanks to (V). In the case (b), $\tau_{5}$
again contracts $x_{3}$ with $x_{4}$, then with $z$, and the argument is the
same.

Situation is different in the case (c) of $u_{1}=u_{3}$, in which we may up to
symmetry assume that $x_{1}u_{1},x_{4}u_{1}\in E(G)$ and
$x_{2}u_{1},x_{3}u_{1}\not\in E(G)$. Then $\tau_{5}$ in the first two steps
contracts the pair $x_{1},x_{4}$ and the pair $x_{2}x_{3}$ (if these pairs
exist). This does not create red edges from $u_{1}$, and in particular, the
red degree of the vertex obtained by the contraction of $x_{1},x_{4}$ stays at
most $9$ ($5$ in layer $\ell+1$ and $4$ in layer $\ell+2$) thanks to $x_{4}$
not having a red neighbour on $P_{2}$ in layer $\ell+2$ by (V). The red
degrees of other concerned vertices, including those on $P_{1}$ and $P_{2}$,
are easily checked from the picture. Next to that, $\tau_{5}$ contracts $t$
with the vertex that stems above from $x_{1},x_{4}$ if $\\{t,u_{1}\\}\in
E(G)$, or $\tau_{5}$ contracts $t$ with the vertex that stems from
$x_{2},x_{3}$ if $\\{t,u_{1}\\}\not\in E(G)$, and this again does not create a
red edge towards $u_{1}$ while keeping other concerned red degrees within the
required bounds. We finish $\tau_{5}$ by contracting $x_{5}$ with $x_{6}$, and
then with $z$ as in the cases (a) and (b) and using the same argument.

a)$P_{1}$$P_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u_{1}}$$u_{3}\leavevmode\nobreak\ $$z$
($\ell+1$)($\ell+2$)($\ell+3$)($U^{2}_{1}$)($U^{3}_{2}$)$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$
b)$P_{1}$$P_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u_{1}}$$\leavevmode\nobreak\ u_{3}$$z$
($U^{2}_{1}$)($U^{3}_{2}$)$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$

c)$P_{1}$$P_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\ {u_{1}=u_{3}}$$t$
$z$
($\ell+1$)($\ell+2$)($\ell+3$)($U^{2}_{1}$)($U^{3}_{2}$)$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$

Figure 3: The three possible cases at the end of the sequence $\tau_{4}$ in
the proof of Lemma 2.1. In each case, all possible vertices resulting from the
recursive contractions in layers $\ell+1$, $\ell+2$ and $\ell+3$ and all their
potential red edges (dotted) are shown, but the three possibilities cover also
(sub)cases in which some of the red vertices or edges are missing, or edges
are not red. For red edges not present in the pictures, consult 1 and 3.

We have finally verified all conditions of Lemma 2.1 for the concatenated
sequence $(\tau.\tau_{0}.\tau_{3}.\tau_{4}.\tau_{5})$, and so the lemma is
proved.

######  Proof 2.4 (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 2. In the rest, we
straightforwardly implement the recursive division of $G$ as used in the proof
of Lemma 2.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 BFS layers. 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 2.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.

##  3 Proving the bound for bipartite planar graphs

On a high level, the proof will follow the same path as the previous one of
Lemma 2.1. However, some details will be quite different, and it is thus
necessary to repeat the proof in this new setting.

In a nutshell, there will be two major changes in the detailed course of the
proof:

  * •

Since our graph is bipartite, we will work with a plane quadrangulation
(instead of a triangulation). This has the effect that we will need to
consider, in general, more than two subproblems in the recursive decomposition
(actually, up to five), and we will slightly relax the assumptions on the
bounding cycle $C$ in the recursion to handle this. However, it does not bring
any big 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, and properly exploiting this
saving requires different detailed handling of the contraction steps.

Let $G$ be a bipartite graph and $r\in V(G)$ a fixed vertex. We again consider
a (fixed) BFS tree $T$ rooted at $r$, and the corresponding BFS layering
${\cal L}=(L_{0}=\\{r\\},L_{1},L_{2},\ldots)$ of $G$. Observe the following:

######  Claim 5 (refinement of 1).

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

The core lemma in the bipartite (quadrangulated) case now reads:

######  Lemma 3.1.

Let $G$ be a 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 BFS layering
${\cal L}=(L_{0}=\\{r\\},L_{1},L_{2},\ldots)$ of $G$. Assume that $P_{i}$,
$i=1,2$, are two edge-disjoint paths of $G$ of lengths at least $1$, where
$P_{i}$ has the ends $u_{i}$ and $v_{i}$, and $u_{1}=u_{2}$. Furthermore,
assume that $P_{1}$ is an $r$-geodesic path and $P_{2}$ is a vertical path in
$G$, that $u_{1}=u_{2}\in L_{\ell}$ is the vertex of $P_{1}\cup P_{2}$ closest
to $r$ (i.e., at distance $\ell$ from $r$), and $f=\\{v_{1},v_{2}\\}\in E(G)$
is an edge such that $v_{1}$ is to the left of $v_{2}$. Then $C:=(P_{1}\cup
P_{2})+f$ is a cycle of $G$, and let $G_{C}$ be the subgraph of $G$ bounded by
$C$, let $U:=V(G_{C})\setminus V(P_{1}\cup P_{2})$ and $W:=V(G)\setminus
V(G_{C})$.

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

  1. (I)’

For $U^{\prime}:=V(G^{\prime})\setminus(V(P_{1}\cup P_{2})\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)’

the vertex $u_{1}$ of $P_{1}\cap P_{2}$ has no red neighbour in $U^{\prime}$,
every vertex of $P_{2}-u_{1}$ and the (two) vertices of $P_{1}-u_{1}$ at
distance at most $2$ from $u_{1}$ have each at most $3$ red neighbours in
$U^{\prime}$, and each remaining vertex of $P_{1}-u_{1}$ has at most $5$ red
neighbours in $U^{\prime}$,

  3. (III)’

at the end of the partial sequence, that is for
$U^{0}:=V(G^{0})\setminus(V(P_{1}\cup P_{2})\cup W)$, we have
$\big{|}U^{0}\cap L_{\ell+1}[G^{0}]\big{|}\leq 2$ and $\big{|}U^{0}\cap
L_{j}[G^{0}]\big{|}\leq 1$ for all $j>\ell+1$.

$r$$v_{1}$$v_{2}$$\leavevmode\nobreak\
{u_{1}=u_{2}}$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$C\quad$$U$$f$$W$ $\leadsto$ $r$$v_{1}$$v_{2}$$\leavevmode\nobreak\
{u_{1}=u_{2}}$$P_{1}\leavevmode\nobreak\ $$\leavevmode\nobreak\
P_{2}$$U^{0}$$W$$(\leq\\!6)$$(0)$$(\leq\\!5)$$(\leq\\!3)$$(\leq\\!3)$$(\leq\\!3)$
Figure 4: (left) The setup of Lemma 3.1, where $v_{1}$ is to the left of
$v_{2}$. (right) The outcome of the claimed partial contraction sequence which
contracts only vertices of $U$ inside the shaded region from the left and
maintains bounded red degrees in the region and on its boundary $C$ formed by
$P_{1}$ and $P_{2}$ and $f$. Not all depicted red edges really exist, and some
of them may actually be black.

We illustrate Lemma 3.1 in Figure 4. Similarly as in the previous section, we
observe that the assumptions of Lemma 3.1 directly imply the following
properties useful for the coming proof of Lemma 3.1.

######  Claim 6.

Within the notation and assumptions of Lemma 3.1, for $G^{\prime}$ we also
have that:

  1. (IV)’

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

  2. (V)’

if $v\in V(P_{2})\cap L_{j}[G^{\prime}]$, then there is no edge in
$G^{\prime}$ (red or black) from $v$ to a vertex of $(U^{\prime}\cup
V(P_{1}))\cap L_{j-1}[G^{\prime}]$,

These properties follow in the same way as (IV) and (V) in 3.

######  Claim 7.

With the notation and assumptions of Lemma 2.1, we have that if (III)’ is
true, then the following holds at the end of the partial contraction sequence:
every vertex $x$ of $P_{1}-u_{1}$ has at most $2$ red neighbours in $U^{0}$,
except when $x$ has distance $2$ from $u_{1}$ – then the bound is $3$, and
every vertex of $P_{2}-u_{1}$ has at most $1$ red neighbour in $U^{0}$.

Consider a vertex $x\in V(P_{1}\cup P_{2})\setminus\\{u_{1}\\}$ such that
$x\in L_{j}[G^{\prime}]$. By 5, the red neighbours of $x$ may be in
$L_{j-1}[G^{\prime}]\cup L_{j+1}[G^{\prime}]$, and by (III)’ we have
$|L_{j+1}[G^{\prime}]\cap U^{0}|\leq 1$ and also $|L_{j-1}[G^{\prime}]\cap
U^{0}|\leq 1$, except when $x$ has distance $2$ from $u_{1}$ and then we have
$|L_{j-1}[G^{\prime}]\cap U^{0}|\leq 2$. This proves the sought upper bound
($1+1=2$ or $2+1=3$) for vertices of $P_{1}-u_{1}$. Furthermore, if $x\in
V(P_{2})\setminus\\{u_{1}\\}$, then there is no such neighbour in
$L_{j-1}[G^{\prime}]$ by (V)’ and the upper bound becomes
$|L_{j+1}[G^{\prime}]\cap U^{0}|\leq 1$.

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

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

We start with a given simple bipartite 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$. Then we choose a root $r$ on the outer face of $G$
and some left-aligned BFS tree of $G$ rooted at $r$ which exists by 2. Let
$P_{1}$ be the path of length $2$ starting in $r$ on the “left” of the outer
face of $G$, and $P_{2}$ be the other edge incident to $r$ on the outer face
of $G$. Then $P_{1}$ is $r$-geodesic since $G$ is bipartite, and $P_{2}$ is
vertical with respect to $T$. Now we apply Lemma 3.1.

This way we get a partial contraction sequence from $G$ to a (still bipartite
by 5) trigraph $G^{0}$ of maximum red degree $6$. Similarly as in the proof of
Theorem 1.1, we get that $L_{0}[G^{0}]=\\{r\\}$, $|L_{1}[G^{0}]|\leq 4$,
$|L_{2}[G^{0}]|\leq 2$, and $\big{|}L_{j}[G^{0}]\big{|}\leq 1$ for all $j\geq
3$ by (III)’.

In the final phase, we pairwise contract the vertices of $L_{1}[G^{0}]$ into
one vertex, and the same with the vertices of $L_{2}[G^{0}]$, making $G^{0}$
into a path by 5, and then naturally contract this path down to a vertex,
never exceeding red degree $5<6$ along this final phase. The restriction of
the whole contraction sequence of $G$ to $V(H)$ then certifies that the twin-
width of $H$ is at most $6$, too.

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

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

If $U=\emptyset$, we are immediately done with the empty partial contraction
sequence. So, we assume $U\not=\emptyset$. Let $\phi$ be the bounded
quadrangular face of $G_{C}$ incident to the edge $f=\\{v_{1},v_{2}\\}$, and
$C_{\phi}\subseteq G$ its boundary cycle. If $\phi$ has all vertices in
$V(P_{1}\cup P_{2})$, then let $f^{\prime}$ be the edge of $C_{\phi}$ joining
$P_{1}$ to $P_{2}$. We then simply apply Lemma 3.1 inductively to $f^{\prime}$
and the corresponding subpaths of $P_{1}$ and $P_{2}$, while the rest of the
assumptions remain the same. It immediately follows that the claimed
conditions of Lemma 3.1 are inherited from this inductive invocation.

Otherwise, there exist at most two vertices $v_{3},v_{k}\in
V(C_{\phi})\setminus V(P_{1}\cup P_{2})$, where $k=4$ if
$|V(C_{\phi})\setminus V(P_{1}\cup P_{2})|=2$ and $k=3$ otherwise. Up to
symmetry between $v_{3}$ and $v_{4}$ if $k=4$, the counter-clockwise cyclic
order of the vertices of $\phi$ is $(v_{1},v_{2},v_{3},v_{k})$.

Let $P_{3}$ be the (unique) vertical path of $G$ with the ends $v_{3}$ and
$u_{3}$ such that $u_{3}\in V(P_{1}\cup P_{2})$ and $P_{3}-u_{3}$ is disjoint
from $P_{1}\cup P_{2}$ (informally, $P_{3}$ is the vertical path from $v_{3}$
to the first vertex on $P_{1}\cup P_{2}$). Likewise, if $k=4$, let $P_{4}$ be
the (unique) vertical path of $G$ with the ends $v_{4}$ and $u_{4}$ such that
$u_{4}\in V(P_{1}\cup P_{2}\cup P_{3})$ and $P_{4}-u_{4}$ is disjoint from
$P_{1}\cup P_{2}\cup P_{3}$. Note that $Y:=P_{1}\cup P_{2}\cup\ldots\cup
P_{k}$ is a tree rooted at $u_{1}$.

If the plane subgraph $Y\cup C_{\phi}$ defines only one bounded face other
than $\phi$, then let $f^{\prime}$ be the edge of $C_{\phi}$ not in $Y$. We
again simply apply Lemma 3.1 inductively to $f^{\prime}$ and the two subpaths
of $Y$ (from the ends of $f^{\prime}$ to $u_{1}$), which clearly satisfy the
assumptions. With the obtained partial contraction sequence, we are nearly
finished and it suffices to finally contract the (one or two) vertices of
$V(C_{\phi})\setminus V(P_{1}\cup P_{2})$ – which are not neighbours of
$u_{1}$ in this case, within their ${\cal L}$-layers. This easily preserves
the claimed conditions of the lemma.

In the remaining cases, we are going to define special subpaths of this tree,
for each of the former paths. Let $P_{2}^{2}$ be the subpath of $P_{2}$ from
$v_{2}$ till the first intersection with $P_{3}\cup P_{1}$ (which may be
$u_{3}$ or $u_{1}$). Symmetrically, let $P_{3}^{1}$ be the subpath of
$P_{3}\cup P_{1}$ from $v_{3}$ till the first intersection with $P_{2}$. Let
$P_{3}^{2}$ be the subpath of $P_{3}\cup P_{2}$ from $v_{3}$ till the first
intersection with $P_{4}\cup P_{1}$ (with only $P_{1}$ if $k=3$) and,
symmetrically, (only if $k=4$) let $P_{4}^{1}$ be the subpath of $P_{4}\cup
P_{1}$ from $v_{4}$ till the first intersection with $P_{3}\cup P_{2}$. Let
(again only if $k=4$) $P_{4}^{2}$ be the subpath of $P_{4}\cup P_{3}\cup
P_{2}$ from $v_{4}$ till the first intersection with $P_{1}$. Finally, let
$P_{1}^{1}$ be the subpath of $P_{1}$ from $v_{1}$ till the first intersection
with $P_{2}\cup\ldots\cup P_{k}$ (which may be $u_{4}$ or $u_{3}$ or $u_{1}$).
Observe that each of the paths $P_{i}^{2}$, $i\in\\{2,3,4\\}$, is vertical
wrt. $T$ in $G$, and each of the paths $P_{i}^{1}$, $i\in\\{1,3,4\\}$, is
$r$-geodesic in $G$.

For each of the (two or three) index pairs $(i,j)\in\\{(2,3),(3,k),(k,1)\\}$,
$i\not=j$, we consider the cycle $D_{i}:=(P_{i}^{2}\cup
P_{j}^{1})+\\{v_{i},v_{j}\\}$. See Figure 5 (the left of), and observe that
the plane region bounded by $C$ is partitioned (modulo the boundaries) into
the face $\phi$ and the regions bounded by $D_{2},\ldots,D_{k}$. There is one
more special case we have to take care of. If, for $i\in\\{3,k\\}$, we have
that $u_{i}\in L_{\ell+1}\setminus V(P_{2})$ ($u_{i}$ is a neighbour of
$u_{1}$, but not on $P_{2}$), and there exists the edge $\\{x,y\\}\in E(G)$
where $x\in L_{\ell+2}\cap V(P_{i}^{2})$ ($x$ is the neighbour of $u_{i}$ on
$P_{i}^{2}$) and $y\in L_{\ell+3}\cap V(P_{j}^{1})$ ($y$ is the distance-$2$
neighbour of $u_{i}$ on $D_{i}$ in the other direction than $x$), then we say
that the cycle $D_{i}$ is split by the edge $g_{i}=\\{x,y\\}$. In such case,
we denote by $D_{i}^{\prime}$ the cycle of $D_{i}+g_{i}$ containing $g_{i}$
and not $u_{i}$, and by $D_{i}^{\prime\prime}$ the cycle of $D_{i}+g_{i}$
containing both $g_{i}$ and $u_{i}$. Then we will consider the cycles
$D_{i}^{\prime}$ and $D_{i}^{\prime\prime}$ separately (instead of whole
$D_{i}$).

In order to unify the notation, we rename the cycles $D_{2}$, $D_{3}$ and
$D_{k}$, after their possible splitting, as $C_{1},\ldots,C_{m}$ where $2\leq
m\leq 2k-3$, and define the “left” and “right” subpaths $Q_{1}^{1}$,
$Q_{1}^{2}$, $Q_{2}^{1},\ldots$ of these cycles, as follows. See on the right
of Figure 5.

  * •

We let $C_{1}=D_{2}$, and then $C_{2}=D_{3}$ if $D_{3}$ is not split, but
$C_{2}=D_{3}^{\prime}$ and $C_{3}=D_{3}^{\prime\prime}$ if $D_{3}$ is split.
When $k=4$ (and $j\in\\{3,4\\}$ is the next available index), we also let
$C_{j}=D_{4}$ if $D_{4}$ is not split, but $C_{j}=D_{4}^{\prime}$ and
$C_{j+1}=D_{4}^{\prime\prime}$ if $D_{4}$ is split.

  * •

For $j\in\\{1,\ldots,m\\}$, if $C_{j}=D_{i}$ was not split, we have
$Q_{j}^{2}=P_{i}^{2}$ and $Q_{j}^{1}=P_{i^{\prime}}^{1}$ where
$i^{\prime}=(i\\!\mod\\!k)+1$ (these are the same two paths as those which
have defined $D_{i}$ above). If $D_{i}$ was split by the edge $g_{i}$ and
$C_{j}=D_{i}^{\prime}$, then we have $Q_{j}^{2}:=P_{i}^{2}-u_{i}$ and
$Q_{j}^{1}:=(P_{i^{\prime}}^{1}\cap C_{j})+g_{i}$. If (again) $D_{i}$ was
split and $C_{j}=D_{i}^{\prime\prime}$, then we take $Q_{j}^{2}$ as the single
edge of $P_{i}^{2}$ incident to $u_{i}$, and $Q_{j}^{1}$ as the length-$2$
subpath of $P_{i^{\prime}}^{1}$ starting in $u_{i}$.

Notice that $E(C_{j})\setminus E(Q_{j}^{1}\cup Q_{j}^{2})$ is always a single
edge (which is one of the edges of $C_{\phi}$, or the split edge of $D_{3}$ or
$D_{4}$). Furthermore, similarly as above, we observe that each of the paths
$Q_{j}^{2}$ is vertical in $G$, and each $Q_{j}^{1}$ is $r$-geodesic, for
$j\in\\{1,\ldots,m\\}$.

$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u_{1}=u_{2}}$$v_{3}$$v_{4}$$\leavevmode\nobreak\
u_{3}$$u_{4}\leavevmode\nobreak\ $$P_{1}\leavevmode\nobreak\
$$\leavevmode\nobreak\
P_{2}$$P_{3}^{1}$$P_{2}^{2}$$P_{3}^{2}$$P_{4}^{1}$$P_{4}^{2}$$P_{1}^{1}$$D_{2}$$D_{4}$$D_{3}$$\phi$
$v_{1}$$v_{2}$$\leavevmode\nobreak\ \leavevmode\nobreak\
{u_{1}=u_{2}}$$v_{3}$$v_{4}$$\leavevmode\nobreak\
u_{3}$$u_{4}\leavevmode\nobreak\ $$\leavevmode\nobreak\
x$$y\leavevmode\nobreak\ $$P_{1}\leavevmode\nobreak\ \leavevmode\nobreak\
$$\leavevmode\nobreak\
P_{2}$$Q_{1}^{1}$$Q_{1}^{2}$$Q_{2}^{2}$$Q_{2}^{1}$$Q_{3}^{2}$$Q_{3}^{1}$$Q_{4}^{2}$$Q_{4}^{1}$$C_{1}\\!=\\!D_{2}$$C_{3}\\!=\\!D^{\prime}_{4}$$C_{2}\\!=\\!D_{3}$$D^{\prime\prime}_{4}$$g_{4}$
Figure 5: (left) An illustration of the general setup of the main induction
step in the proof of Lemma 3.1; the region bounded by $C$ is “divided” into
the face $\phi$ and up to three subregions bounded by the cycles $D_{2}$,
$D_{3}$ and $D_{4}$ (which are in turn defined by the vertical paths $P_{3}$
and $P_{4}$ inside $C$). (right) The division from the left is further refined
at the cycle $D_{4}$ which is split by the edge $g_{4}$, the defining cycles
of this refined division are further renamed as $C_{1}=D_{2}$, $C_{2}=D_{3}$,
$C_{3}=D_{4}^{\prime}$ and $C_{4}=D_{4}^{\prime\prime}$, and the paths
$Q_{j}^{1}$ and $Q_{j}^{2}$ of each $C_{j}$, $j\in\\{1,2,3,4\\}$, are outlined
in the picture.

The key conclusion from the initial step of this proof is that we can apply
Lemma 3.1 inductively (and independently) to each of the cycles $C_{j}$,
$j\in\\{1,\ldots,m\\}$, more specifically to the pair of paths $Q_{j}^{1}$,
$Q_{j}^{2}$. However, the application is not as straightforward as in the
proof of Lemma 2.1, since we have more than two subcases in general and we are
going to merge them pairwise; the outcome of the subcase of $C_{1}$ with that
of $C_{2}$, then the result with the outcome of the subcase $C_{3}$, then with
$C_{4}$ …To formally manage this process, via nested induction, we are going
to show that the merged region (considering it with a generalized “bounding”
which is to be defined below) will again satisfy the conditions (I)’, (II)’
and (III)’ of Lemma 3.1, and consequently also the additional conditions of 6.

We say that a subgraph $H_{1}\subseteq G$ is properly bounded by paths
$R^{1},R^{2}\subseteq H_{1}$ (with respect to implicit $G$, and in this order
of $R^{1}$, $R^{2}$), if the following holds. The path $R^{i}$, $i=1,2$, has
the ends $s_{i}$ and $t_{i}$ and $s_{1}=s_{2}$ is the vertex of $H_{1}$
closest to $r$ in $G$, and $R^{1}$ is an $r$-geodesic path and $R^{2}$ is a
vertical path in $G$. Moreover, there is no edge between a vertex of
$V(H_{1})\setminus V(R^{1}\cup R^{2})$ and a vertex of $V(G)\setminus
V(H_{1})$. Notice that, under the assumptions of Lemma 3.1, the subgraph
$G_{C}$ is properly bounded by $P_{1}$ and $P_{2}$, however, here we do not
explicitly require the existence of an edge $\\{t_{1},t_{2}\\}$. We shortly
say that the vertex $s_{1}=s_{2}$ is the sink of $H_{1}$, and that the
vertices of $V(H_{1})\setminus V(R^{1}\cup R^{2})$ form the interior of
$H_{1}$, those of $V(G)\setminus V(H_{1})$ the exterior of $H_{1}$ and those
of $V(R^{1}\cup R^{2})$ the boundary of $H_{1}$.

The rest of the proof relies on the following technical claim:

######  Claim 8.

Assume a subgraph $H_{0}\subseteq G$ that is properly bounded by paths
$R_{0}^{1},R_{0}^{2}\subseteq H_{0}$, together with two subgraphs
$H_{i}\subseteq H_{0}$, $i=1,2$, properly bounded by paths
$R_{i}^{1},R_{i}^{2}$, and an $r$-geodesic path $R^{\prime}$ in $G$, such that
the following hold:

  1. a)

$V(R^{\prime})=V(H_{1})\cap V(H_{2})$, and $V(R^{\prime})\setminus
V(R_{0}^{1}\cup R_{0}^{2})\subseteq V(R_{1}^{2})\cap V(R_{2}^{1})$,

  2. b)

$V(R_{0}^{1})\subseteq V(R_{1}^{1})\cup V(R_{2}^{1})$ and
$V(R_{0}^{2})\subseteq V(R_{1}^{2})\cup V(R_{2}^{2})$,

  3. c)

there is at most one vertex in $V(R^{\prime})\cap V(R_{0}^{2})$ and then it is
the sink of $H_{2}$, and for $z$ being the end of $R_{1}^{1}$ farther from
$r$, there is at most one vertex in $V(R^{\prime})\cap V(R_{0}^{1}-z)$ and
then it is the sink of $H_{1}$,

  4. d)

if $z\in V(R^{\prime})\cap V(R_{0}^{1})$, then the length of $R_{1}^{1}$ is
exactly $2$ and $z$ is at distance $3$ from the sink of $H_{0}$ (cf. the split
case in the above definitions).

If, for $i=1,2$, there is an ${\cal L}$-respecting partial contraction
sequence $\tau_{i}$ of $G$ contracting only among the interior vertices of
$H_{i}$, such that $\tau_{i}$ satisfies the conditions (I)’, (II)’ and (III)’
of Lemma 3.1 (specifically, with $P_{1}$ and $P_{2}$ replaced by $R_{i}^{1}$
and $R_{i}^{2}$, respectively, and $U$ and $W$ being the interior and the
exterior vertices of $H_{i}$), then there is an ${\cal L}$-respecting partial
contraction sequence $\tau_{0}$ of $G$ contracting only among the interior
vertices of $H_{0}$, such that $\tau_{0}$ satisfies the conditions (I)’, (II)’
and (III)’ of Lemma 3.1, too.

We first show how 8 finishes the proof of Lemma 3.1. Let $G_{j}\subseteq G$,
$j\in\\{1,\ldots,m\\}$, denote the subgraph bounded by the cycle $C_{j}$ in
$G$. We apply 8 to $H_{0}=G_{2}^{\prime}:=G_{1}\cup G_{2}$ and $H_{1}=G_{1}$,
$H_{2}=G_{2}$, where the partial contraction sequences $\tau_{i}$,
$i\in\\{1,2\\}$, assumed by the claim, are obtained for $i=1,2$ by an
inductive invocation of Lemma 3.1 to $C_{i}$ with the above defined paths
$Q_{i}^{1}=R_{i}^{1}$, $Q_{i}^{2}=R_{i}^{2}$. The remaining conditions of 8
can be routinely verified from the definition of the cycles $C_{1}$ and
$C_{2}$. In particular, $H_{0}=G_{2}^{\prime}$ is properly bounded by
appropriate paths $R_{0}^{1},R_{0}^{2}$ since any edge between an interior and
an exterior vertex of $H_{0}$ would have to cross the face $\phi$ of the plane
graph $G$ which is absurd.

Subsequently, for $j=3,\ldots,m$, we analogously apply 8 to
$H_{0}=G_{j}^{\prime}:=G_{j-1}^{\prime}\cup G_{j}$ and $H_{1}=G_{j}$,
$H_{2}=G_{j-1}^{\prime}$, where the partial contraction sequence $\tau_{2}$
has been obtained inductively in the previous iteration for
$G_{j-1}^{\prime}$, and $\tau_{1}$ is obtained by an inductive invocation of
Lemma 3.1 to $C_{j}$ with the above defined paths $Q_{j}^{1}=R_{1}^{1}$,
$Q_{j}^{2}=R_{1}^{2}$. Since $G_{m}^{\prime}=G_{C}$, as considered by Lemma
3.1, the proof of Lemma 3.1 is finished by this.

Now it remains to prove 8. We first clarify that both 6 and 7 remain true in
the extended setting of 8. For property (IV)’ of 6, this follows from the
definition of $H_{0}$ being properly bounded, and for property (V)’ the
arguments of 6 stay the same since $R_{0}^{2}$ is vertical in $G$. The
arguments of 7 also stay the same.

We apply the ${\cal L}$-respecting partial contraction sequences $\tau_{2}$
and $\tau_{1}$ on $G$ in this order (i.e., $\tau_{1}$ after whole $\tau_{2}$).
This is sound since the subgraphs $H_{1}$ and $H_{2}$ are properly separated,
and so no contraction in $\tau_{2}$ has an effect in the neighbourhood of the
interior vertices of $H_{1}$ and vice versa. Let
$\tau^{\prime}=\tau_{2}.\tau_{1}$ be the concatenated sequence contracting
from original $G$ to the trigraph $G^{2}$. We first verify that the conditions
(I)’ and (II)’ are satisfied along $\tau^{\prime}$ (while (III)’ is void for
$G^{2}$ at this stage). This is immediate for (I)’ and the interior vertices
of $H_{1}$ and of $H_{2}$ since they do not get any other red neighbour than
from their partial sequence. Each vertex $x\in V(R^{\prime})\setminus
V(R_{0}^{1}\cup R_{0}^{2})$ satisfies (I)’ along $\tau_{2}$, using (II)’ for
$H_{2}$ by 8.a, and then (still in $\tau_{2}$) it ends up with at most $1$ red
neighbour in the (contracted) interior of $H_{2}$ by 7 for $H_{2}$.
Subsequently, $x$ never exceeds red degree of $5+1=6$ along $\tau_{1}$ thanks
to again 8.a and (II)’ for $H_{1}$.

We are left with the vertices $y\in V(R_{0}^{1}\cup R_{0}^{2})$ and the
condition (II)’ for $H_{0}$. Assume first $y\not\in V(H_{1})\cap V(H_{2})$. By
8.b, validity of the condition (II)’ is inherited from its validity for
$H_{1}$ or $H_{2}$; this is immediate except possibly for the case of $y\in
V(R_{0}^{1})$ at distance at most $2$ from the sink of $H_{0}$, in which it
suffices to observe that the sinks of $H_{1}$ and $H_{2}$ cannot be farther
from $y$ than the sink of $H_{0}$.

Now, let $y\in V(H_{1})\cap V(H_{2})=V(R^{\prime})$. In this case, $y$ is the
sink of $H_{1}$ or $H_{2}$ by 8.c, and then it receives no red edge from the
other sequence and (II)’ holds. Alternatively, we may have the special case of
$y=z$ (the far end of $R^{\prime}$) and $y\in V(R_{0}^{1})$, in which the
assumption of 8.d applies. Moreover, in this case the sink of $H_{2}$ is
identical to the sink of $H_{0}$, and so at the end of $\tau_{2}$ the vertex
$y$ has at most $2$ red neighbours in the (contracted) interior of $H_{2}$ by
7 for $H_{2}$. Subsequently, along $\tau_{1}$, the number of red neighbours of
$y$ in the interior of $H_{1}$ always stays at most $3$ by (II)’ for $H_{1}$
(since $y$ is at distance $2$ from the sink of $H_{1}$). Altogether, this
means at most $2+3=5$ red neighbours in the interior of $H_{0}$ along whole
$\tau^{\prime}$, as needed in (II)’ for $H_{0}$.

Verification of the conditions (I)’ and (II)’ along $\tau^{\prime}$ is
finished.

We continue contractions from the trigraph $G^{2}$ to $G^{3}$ along a special
${\cal L}$-respecting partial contraction sequence $\tau_{3}$ as follows. Let
$W$ denote the exterior vertices of $H_{0}$, and
$U^{\prime}:=V(G^{2})\setminus(V(R_{0}^{1}\cup R_{0}^{2})\cup W)$ be the
vertices of $G^{2}$ that stem by contractions from the interior of $H_{0}$. If
the sink $s_{0}$ of $H_{0}$ is identical to the sinks of $H_{1}$ and of
$H_{2}$, and $s_{0}\in L_{\ell}$, then we have up to $5$ vertices in
$U^{\prime}\cap L_{\ell+1}[G^{2}]$, and we iteratively (in any order) contract
those pairs of them with the same adjacency relation to $s_{0}$. This
preserves validity of the condition (II)’ for $H_{0}$, and regarding (I)’ we
use 5, according to which the red neighbours of the contracted vertices from
$U^{\prime}\cap L_{\ell+1}[G^{2}]$ are only in the layer $\ell+2$ and we
clearly have $|(V(G^{2})\setminus W)\cap L_{\ell+2}[G^{2}]|\leq 5$ by (III)’
for $H_{1}$ and $H_{2}$. If the sink $s_{2}$ of $H_{2}$ belongs to
$V(R_{0}^{2}-s_{0})$, and $s_{2}\in L_{p}$, then we contract the up to two
vertices of $U^{\prime}\cap L_{p+1}[G^{2}]$ into one. This adds one red edge
to $s_{2}$, but this is safe by 7 for $H_{1}$ since $1+1<3$. Again, validity
of the conditions (I)’ and (II)’ along $\tau_{3}$ is easily preserved. In all
other cases we leave $\tau_{3}$ empty.

Then we construct an ${\cal L}$-respecting partial contraction sequence
$\tau_{4}$ from $G^{3}$ to $G^{4}$. Let
$U_{0}:=V(G^{3})\setminus(V(R_{0}^{1}\cup R_{0}^{2})\cup W)$ be the vertices
of $G^{3}$ that are or stem by contractions from the interior of $H_{0}$. Let
$U_{3}:=U_{0}\cap V(R^{\prime})$, and for $i=1,2$ let $U_{i}\subseteq U_{0}$
be the vertices that are or stem by contractions from the interior of $H_{i}$.
For an informal illustration, $(U_{1},U_{2},U_{3})$ is “nearly” a partition of
$U_{0}$, except that $U_{0}\cap L_{\ell+1}[G^{3}]$ may belong to both $U_{1}$
and $U_{2}$ due to the contractions in $\tau_{3}$. Note that $\big{|}U_{2}\cap
L_{p}[G^{3}]\big{|}\leq 1$ for all $p\geq\ell+2$, by $\tau_{3}$, and similarly
$\big{|}U_{1}\cap L_{p}[G^{3}]\big{|}\leq 1$ for all $p\geq\ell+2$ except when
$p$ is the layer next to the sink of $H_{1}$ (then it is $\cdot\leq 2$), and
$\big{|}U_{3}\cap L_{p}[G^{3}]\big{|}\leq 1$ since $R^{\prime}$ is
$r$-geodesic. Furthermore, $U_{3}\cap L_{\ell+1}[G^{3}]=\emptyset$ as ensured
by the sequence $\tau_{3}$.

The sequence $\tau_{4}$ is going to contract each layer of $U_{2}\cup U_{3}$
into one vertex, starting from the farthest layer till layer $\ell+2$.
Formally, let $d:=\max\\{i:(U_{2}\cup U_{3})\cap
L_{i}[G^{3}]\not=\emptyset\\}$. For $i=d,d-1,\ldots,\ell+2$ in this order, if
$\big{|}(U_{2}\cup U_{3})\cap L_{i}[G^{3}]\big{|}>1$, then $\tau_{4}$
contracts these two vertices in layer $i$. That is all for $\tau_{4}$, and we
now verify the conditions (I)’ and (II)’ for any trigraph $G^{\prime}$ along
$\tau_{4}$. Let $H_{0}^{\prime}:=G^{\prime}-W$ be the corresponding trigraph
contracted from $H_{0}$, and let $U_{3}^{\prime}$ be the vertices of
$G^{\prime}$ that stem by $\tau_{4}$-contactions from $U_{2}\cup U_{3}$. We
consider all possibly affected vertices of $H_{0}^{\prime}$ as follows:

  * •

The sink $s_{0}$ of $H_{0}$ (which is the sink of $H_{0}^{\prime}$, too) has
got no red edge.

  * •

For $x\in V(R_{0}^{2})\setminus\\{s_{0}\\}$, where $x\in L_{p}[G^{\prime}]$,
we have no red neighbours in $L_{p-1}[G^{\prime}]$ by (V)’ applied to $H_{2}$.
In $L_{p+1}[G^{\prime}]$, there is always at most one red neighbour of $x$ by
the contraction process of $\tau_{3}.\tau_{4}$, except when $x$ is the sink of
$H_{2}$ and a second red neighbour of $x$ may exist in $U_{1}$. Hence, (II)’
is true for $x$.

  * •

For $x\in V(R_{0}^{1})\setminus\\{s_{0}\\}$, where $x\in L_{p}[G^{\prime}]$,
we distinguish two subcases. If $x\in V(H_{2})$, then $\tau_{4}$ does not
contract in the neighbourhood of $x$ (and there is nothing to solve), except
when $x$ is also the sink of $H_{1}$ – then $x$ has at most two (two if
$p=\ell+2$) red neighbours in $U_{2}\cap L_{p-1}[G^{\prime}]$ and an
additional one in contracted $U_{3}^{\prime}\cap L_{p+1}[G^{\prime}]$.

Secondly, if $x\in V(H_{1})\setminus V(H_{2})$, then $x$ has at most two red
neighbours in layer $p-1$, that is one in $U_{1}\cap L_{p-1}[G^{\prime}]$ and
one possibly in $U_{3}^{\prime}\cap L_{p-1}[G^{\prime}]$. In addition to that,
$x$ may have one red neighbour in $U_{1}\cap L_{p+1}[G^{\prime}]$, but no red
neighbour in $(U_{2}\cup U_{3})\cap L_{p+1}[G^{\prime}]$ and no such in
$U_{3}^{\prime}\cap L_{p+1}[G^{\prime}]$ – the latter is due to (V)’ applied
to $H_{1}$.

In both subcases, we have that (II)’ is true for $x$.

  * •

If $x\in U_{1}\cap L_{p}[G^{\prime}]$ and $p\geq\ell+2$, then $x$ cannot be
adjacent to vertices in $U_{2}\cup V(R_{0}^{2})$ since $H_{1}$ was properly
separated. There are at most $4$ red neighbours of $x$ in $(V(R_{0}^{1})\cup
U_{1}\cup U_{3}\cup U_{3}^{\prime})\cap L_{p-1}[G^{\prime}]$ (two of which may
be in $U_{1}\cap L_{p-1}[G^{\prime}]$). Additionally, there are up to $2$ red
neighbours of $x$ in $(V(R_{0}^{1})\cup U_{1})\cap L_{p+1}[G^{\prime}]$, but
$x$ cannot be a neighbour of the vertex of $U_{3}^{\prime}\cap
L_{p+1}[G^{\prime}]$ due to (V)’ applied to $H_{1}$. We have that (I)’ is true
for $x$.

  * •

If $x\in(U_{1}\cup U_{2})\cap L_{\ell+1}[G^{\prime}]$, then $x$ is not
contracted by $\tau_{4}$, and $x$ has potential red neighbours only in
$L_{\ell+2}[G^{\prime}]\cap V(H_{0}^{\prime})$ of at most $6$ vertices. So,
(I)’ is true for $x$.

  * •

It remains to consider $x\in(U_{2}\cup U_{3}\cup U_{3}^{\prime})\cap
L_{p}[G^{\prime}]$ where $p\geq\ell+2$. Since $H_{2}$ is properly separated,
and by (V)’ applied to $H_{1}$, there is no red edge from $x$ to
$(V(R_{0}^{1})\cup U_{1})\cap L_{p-1}[G^{\prime}]$. For the rest, there are
hence at most $4$ red neighbours of $x$ in $(U_{2}\cup U_{3}\cup
U_{3}^{\prime})\cap L_{p-1}[G^{\prime}]$. There is also no red edge from $x$
to $V(R_{0}^{2})\cap L_{p+1}[G^{\prime}]$ by (V)’ applied to $H_{2}$. If
$x\not\in U_{3}^{\prime}$, there are at most $2$ red neighbours of $x$ in
layer $p+1$, and otherwise there can be up to $3$ red neighbours of $x$ there
in $(V(R_{0}^{1})\cup U_{1}\cup U_{3}^{\prime})\cap L_{p+1}[G^{\prime}]$.

The latter subcase indicates a possible problem of $x\in U_{3}^{\prime}$
reaching the red degree of $4+3>6$, but for this to actually happen, it would
have to be $|U_{2}\cap L_{p-1}[G^{\prime}]|=2$, meaning that $p=\ell+2$, and
$x$ would need to have a red edge to $V(R_{0}^{1})\cap L_{p+1}[G^{\prime}]$,
meaning that there was such a black edge in $G^{3}$ and so already in $G$.
This would be the case of a split cycle $D$ resolved in the initial step of
the proof by another decomposition, and hence this cannot be true here. Again,
(I)’ holds for $x$.

We continue from the trigraph $G^{4}$ to $G^{5}$ with an ${\cal L}$-respecting
partial contraction sequence $\tau_{5}$ as follows. We recall the set $U_{1}$
from the previous phase which stays the same in $G^{4}$, and the set
$U_{3}^{\prime}$ as those vertices of $G^{4}$ which are in or stem by
contractions from $U_{2}\cup U_{3}$ of $G^{3}$. The purpose of $\tau_{5}$ is
similar to that of the previous special sequence $\tau_{3}$; to contract the
possible pair of vertices of $U_{1}$ which are neighbours of the sink of
$H_{1}$. Let $s_{1}$ denote the sink of $H_{1}$, and assume $s_{1}\in
L_{p}[G^{4}]$. If $p=\ell$ or $|U_{1}\cap L_{p+1}[G^{4}]|\leq 1$, then
$\tau_{5}$ is empty. Otherwise, if $p=\ell+1$, then $\tau_{5}$ simply
contracts the vertex pair in $U_{1}\cap L_{p+1}[G^{4}]$. If $p>\ell+1$, then
$\tau_{5}$ contracts the single vertex $z\in U_{3}^{\prime}\cap
L_{p+1}[G^{4}]$ with one and then with the other one of the two vertices of
$U_{1}\cap L_{p+1}[G^{4}]$.

We verify validity of the conditions (I)’ and (II)’ along $\tau_{5}$. In the
case of $p=\ell+1$, the only vertex with possibly increased red degree is
$s_{1}$. However, in this case $s_{1}$ has no red neighbour in layer
$p-1=\ell$ and at most one in layer $p+1$ by the analysis of $\tau_{4}$. After
$\tau_{5}$, the red degree of $s_{1}$ is thus at most $1+1=2$ which is good
for (II)’. In the case of $p>\ell+1$, the potential red neighbours of the
vertices being contracted with $z$ are the at most three vertices of
$V(R_{0}^{1}\cup R_{0}^{2}\cup U_{3}^{\prime})\cap L_{p-1}[G^{4}]$ plus the at
most three vertices of $V(R_{0}^{1}\cup U_{1}\cup U_{3}^{\prime})\cap
L_{p+1}[G^{4}]$ (recall the previous analysis of $\tau_{4}$), which sums to
the red degree at most $6$ along $\tau_{5}$ and is good for (I)’. Furthermore,
for each of these considered six vertices, $z$ has been counted as their red
neighbour in the previous analysis of $\tau_{4}$, and so their maximum red
degree does not increase along $\tau_{5}$.

At last, we construct an ${\cal L}$-respecting partial contraction sequence
$\tau_{6}$ from $G^{5}$ to $G^{6}$. We denote by $U_{4}$ the set of vertices
of $G^{5}$ including $U_{1}\cap V(G^{5})$ and the possible vertex resulting by
the contractions of $\tau_{5}$, and by
$U_{5}:=V(G^{5})\setminus(V(R_{0}^{1}\cup R_{0}^{2})\cup W\cup U_{4})$ the set
of those vertices of $G^{5}$ which stem by contractions from $U_{2}\cup U_{3}$
of $G^{3}$ in $\tau_{4}$ and are not touched by $\tau_{5}$. The sequence
$\tau_{5}$ is going to contract each layer of $U_{4}\cup U_{5}$ into one
vertex, starting from the farthest layer till layer $\ell+2$. Formally, let
$d:=\max\\{i:(U_{4}\cup U_{5})\cap L_{i}[G^{5}]\not=\emptyset\\}$. For
$i=d,d-1,\ldots,\ell+2$ in this order, if $\big{|}(U_{4}\cup U_{5})\cap
L_{i}[G^{5}]\big{|}>1$, then $\tau_{5}$ contracts the pair of vertices of
$(U_{4}\cup U_{5})\cap L_{i}[G^{5}]$.

We now verify the conditions (I)’ and (II)’ for any trigraph $G^{\prime}$
along $\tau_{6}$. Let $U_{5}^{\prime}$ denote the set of vertices of
$G^{\prime}$ that stem by $\tau_{6}$-contactions from $U_{4}\cup U_{5}$. We
perform an analogous case analysis of all possibly affected vertices:

  * •

The sink $s_{0}$ of $H_{0}$ has again got no red edge.

  * •

For $x\in V(R_{0}^{2})\setminus\\{s_{0}\\}$, where $x\in L_{p}[G^{\prime}]$,
we have no red neighbours in $L_{p-1}[G^{\prime}]$ by (V)’, and there are at
most $2$ candidates for a red neighbour of $x$ in $U_{5}^{\prime}\cap
L_{p+1}[G^{\prime}]$ (this is after a $\tau_{6}$-contaction in layer $p+1$).
Hence, (II)’ is true for $x$.

  * •

For $x\in V(R_{0}^{1})\setminus\\{s_{0}\\}$, where $x\in L_{p}[G^{\prime}]$,
and after a $\tau_{6}$-contaction in layer $p+1$, the vertex $x$ has at most
one red neighbour in layer $p+1$, in $U_{5}^{\prime}\cap L_{p+1}[G^{\prime}]$.
In layer $p-1$, there is possibly one red neighbour in $(U_{5}\cup
U_{5}^{\prime})\cap L_{p-1}[G^{\prime}]$ and one in $U_{4}\cap
L_{p-1}[G^{\prime}]$. Together, (II)’ is true for $x$.

  * •

If $x\in(U_{1}\cup U_{3}^{\prime})\cap L_{\ell+1}[G^{\prime}]$, then $x$ is
not contracted by $\tau_{5}$, and (I)’ is true for $x$ as previously.

  * •

It remains to consider $x\in(U_{4}\cup U_{5}\cup U_{5}-^{\prime})\cap
L_{p}[G^{\prime}]$ where $p\geq\ell+2$, and after a $\tau_{6}$-contaction in
layer $p+1$. The only possible red neighbours of $x$ in layer $p+1$ are in
$(V(R_{0}^{1})\cup U_{5}^{\prime})\cap L_{p+1}[G^{\prime}]$ which has at most
$2$ vertices. There is again no red edge from $x$ to $V(R_{0}^{2})\cap
L_{p+1}[G^{\prime}]$ by property (V)’. In layer $p-1$, there are altogether at
most $4$ vertices in $(V(R_{0}^{1}\cup R_{0}^{2})\cup U_{5}\cup
U_{5}^{\prime})\cap L_{p-1}[G^{\prime}]$. So, the bound on red degree at most
$6$ holds and (II)’ is true for $x$.

The last step in the proof of 8 is to observe that the concatenated sequence
$\tau_{0}:=(\tau^{\prime}.\tau_{3}.\tau_{4}.\tau_{5}.\tau_{6})$, with the
outcome $G^{6}$ as above, satisfies also the condition (III)’. Lemma 3.1 is
thus proved.

######  Proof 3.4 (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, and then construct a left-aligned BFS
tree $T\subseteq G$ again in linear time by 2. In the rest, we
straightforwardly implement the recursive 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 of the lemma, specifically in 8. Note
that we again do not need at all to construct the intermediate trigraphs along
the constructed contraction sequence. Hence this proof is the same as that of
Theorem 1.1.

##  4 Conclusion

We have significantly improved the best upper bound on the twin-width of
planar graphs, and we seem to be approaching its true maximum value on planar
graphs. While some arguments in the proof of Lemma 2.1 are still loose and can
be further improved by one or two down, there are several specific situations
in the proof in which one cannot go lower than $9$, e.g., in the “game ending”
trigraphs in Figure 3. Though, we have no specific conjecture about what the
true maximum can be.

We have also given an upper bound on the twin-width of bipartite planar
graphs, which have not yet been specifically targetted by twin-width research.
The bound of $6$ again seems to approach the true maximum value on bipartite
planar graphs and, in particular, there does not seem to be room for further
improvement in the proof of Lemma 3.1.

The natural next step of our research is to have a closer look at suitable
lower-bound planar examples. Another natural direction of research is to
extend this result to other graph classes which are related to planar graphs,
and especially to those classes for which explicit twin-width upper bounds
have already been given using the product-structure machinery (e.g., for
$k$-planar graphs).

## 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.  arXiv:2204.11495.
  * [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] 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.