# Graph Product Structure for $h$-Framed Graphs

Michael A. Bekos1, Giordano Da Lozzo2, Petr Hliněný3, Michael Kaufmann4

1University of Ioannina, Ioannina, Greece
<EMAIL_ADDRESS>
2Department of Engineering, Roma Tre University, Italy
<EMAIL_ADDRESS>
3Masaryk University, Brno, Czech Republic
<EMAIL_ADDRESS>
4University of Tübingen, Tübingen, Germany
<EMAIL_ADDRESS>
###### Abstract

Graph product structure theory expresses certain graphs as subgraphs of the
strong product of much simpler graphs. In particular, an elegant formulation
for the corresponding structural theorems involves the strong product of a
path and of a bounded treewidth graph, and allows to lift combinatorial
results for bounded treewidth graphs to graph classes for which the product
structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4),
22:1-38, 2020].

In this paper, we join the search for extensions of this powerful tool beyond
planarity by considering the $h$-framed graphs, a graph class that includes
$1$-planar, optimal $2$-planar, and $k$-map graphs (for appropriate values of
$h$). We establish a graph product structure theorem for $h$-framed graphs
stating that the graphs in this class are subgraphs of the strong product of a
path, of a planar graph of treewidth at most $3$, and of a clique of size
$3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1$. This allows us to improve over the
previous structural theorems for $1$-planar and $k$-map graphs. Our results
constitute significant progress over the previous bounds on the queue number,
non-repetitive chromatic number, and $p$-centered chromatic number of these
graph classes, e.g., we lower the currently best upper bound on the queue
number of $1$-planar graphs and $k$-map graphs from $495$ to $81$ and from
$32225k(k-3)$ to $61k$, respectively. We also employ the product structure
machinery to improve the current upper bounds of twin-width of planar and
$1$-planar graphs from $183$ to $37$, and from $O(1)$ to $80$, respectively.
All our structural results are constructive and yield efficient algorithms to
obtain the corresponding decompositions.

##  1 Introduction

Graph product structure theory [DBLP:journals/jacm/DujmovicJMMUW20] was
recently introduced and is receiving considerable attention, as it gives deep
insights that allow a host of mathematical and algorithmic tools to be
applied. Despite being a relatively new development, it is having significant
impact [Banff2021]; initially, it was introduced to settle a long-standing
conjecture by Heath, Leighton and Rosenberg [DBLP:journals/siamdm/HeathLR92]
related to the queue number of planar graphs
[DBLP:journals/jacm/DujmovicJMMUW20], but recently it has been exploited to
solve several other combinatorial problems that were open for years, e.g., it
was used to prove that planar graphs have bounded non-repetitive chromatic
number [DBLP:journals/jacm/DujmovicJMMUW20], to improve the best known bounds
for $p$-centered colorings of planar graphs and graphs excluding any fixed
graph as a subdivision [DBLP:conf/soda/DebskiFMS20], to find shorter adjacency
labelings of planar graphs [DBLP:conf/soda/BonamyGP20], and to find
asymptotically optimal adjacency labelings of planar graphs
[DBLP:conf/focs/DujmovicEGJMM20].

In its simplest form, the product structure theorem states that every planar
graph is a subgraph of the strong product of a path and of a planar graph of
treewidth at most 6 [DBLP:journals/jacm/DujmovicJMMUW20,
DBLP:journals/corr/abs-2108-00198]. The bound on the treewidth can be improved
by allowing more than two graphs in the strong product, as it is known that
every planar graph is a subgraph of the strong product of a path, of a
$3$-cycle and of a planar graph of treewidth at most $3$
[DBLP:journals/jacm/DujmovicJMMUW20]. These theorems are attractive, since
they describe planar graphs in terms of graphs of bounded treewidth, which are
considered much simpler than the planar ones. Furthermore, they enable
combinatorial results that hold for graphs of bounded treewidth to be
generalised for planar graphs and, more in general, for graphs where similar
structural theorems can be obtained.

Analogous are known for graphs of bounded Euler genus
[DBLP:journals/jacm/DujmovicJMMUW20], apex-minor-free graphs
[DBLP:journals/jacm/DujmovicJMMUW20], graphs with bounded degree in minor
closed classes [DBLP:journals/cpc/DujmovicEMWW22], and graphs in non-minor
closed classes [DBLP:journals/corr/abs-1907-05168]; see
[DBLP:journals/corr/abs-2001-08860] for a survey. Related to our work are the
structural theorems for $k$-planar and $k$-map graphs (the former ones are the
graphs that can be drawn with at most $k$ crossings per edge, whereas the
latter ones are the contact-graphs of regions homeomorphic to closed disks).
In particular, it is known that every $k$-planar graph is a subgraph of the
strong product of a path, of a graph of treewidth at most
$\frac{1}{6}(k+4)(k+3)(k+2)-1$, and of a clique on $18k^{2}+48k+30$ vertices,
while every $k$-map graph is a subgraph of the strong product of a path, of a
graph of treewidth at most $9$, and of a clique on $21k(k-3)$ vertices
[DBLP:journals/corr/abs-1907-05168].

Our contribution. In this work, our focus is on the class of $h$-framed
graphs, which were recently introduced as a notable subclass of $k$-planar and
$k$-map graphs (for appropriate values of $k$)
[DBLP:conf/compgeom/BekosLGGMR20]; a graph is _$h$ -framed_, if it admits a
drawing on the Euclidean plane whose uncrossed edges induce a biconnected
spanning plane graph with faces of size at most $h$. Since any $h$-framed
graph is $O(h^{2})$-planar, it follows that every $h$-framed graph is a
subgraph of a path, of a graph with treewidth $O(h^{6})$ and of a clique of
size $O(h^{4})$. Our main contribution is to show the following structural
result (which lowers the treewidth to $O(1)$ –also achieving planarity– and
the size of the involved clique to $O(h)$): Every $h$-framed graph is a
subgraph of the strong product of a path, of a planar graph of treewidth at
most 3, and of a clique on $3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1$
vertices; see Theorem 2. Note that, since any planar graph is a subgraph of
some triangulation (and thus of a $3$-framed graph), for $h=3$ we have that
planar graphs are subgraphs of $H\boxtimes P\boxtimes K_{3}$, which coincides
with the product structure theorem for planar graph proved in
[DBLP:journals/jacm/DujmovicJMMUW20]. Furthermore, we provide an alternative
formulation, where the role played by a path is instead played by the $\lfloor
h/2\rfloor$-th power of a path, which allows us to further reduce the size of
the clique involved in the product to $\max(3,h-2)$; see Theorem 8. Our
algorithms provide improved upper bounds on the queue number, on the non-
repetitive chromatic number, and on the $p$-centered chromatic number of
$h$-framed graphs that are linear in $h$ (while the ones that can be derived
from the result in [DBLP:journals/corr/abs-1907-05168] are at least quadratic
in $h$); see Theorem 10, Corollary 16, and Lemma 17, respectively. Finally, by
extending the product structure machinery, we are able to give an efficient
construction to obtain an improved bound on the twin-width of planar graphs
and an explicit, linear in $h$, upper bound on the twin-width of $h$-framed
graphs, while the current-best explicit upper bound derives from the one for
$k$-planar graphs and it is hence exponential in $O(h^{2})$
[DBLP:journals/jacm/BonnetKTW22, DBLP:journals/corr/abs-2202-11858]; see
Theorem 19 and Theorem 22 respectively.

Consequences on related graph classes. Since $1$-planar and optimal $2$-planar
graphs are subgraphs of $4$\- and $5$-framed graphs [DBLP:conf/gd/AlamBK13,
DBLP:conf/compgeom/Bekos0R17], and since $k$-map graphs are subgraphs of
$2k$-framed graphs [DBLP:journals/corr/abs-2003-07655,
DBLP:conf/compgeom/BekosLGGMR20], the product structure theorems mentioned
above imply significant improvements on the current best bounds for the
following parameters; for definitions, see Section 4.

  * •

Queue number: Using Theorem 2, we improve the best-known upper bound on the
queue number of $k$-map graphs from $32225k(k-3)$
[DBLP:journals/corr/abs-1907-05168] to $61k$ (Corollary 11), whereas, using
Theorem 8, we lower the best-known upper bounds on the queue number of
$1$-planar and optimal $2$-planar graphs from $495$ and $3267$, respectively,
both to $81$ (Theorem 14).

  * •

Non-repetitive chromatic number: Theorem 2 allows us to improve the best-known
upper bound on the non-repetitive chromatic number of $k$-map graphs from
$21\cdot 4^{10}\cdot k(k-3)$ [DBLP:journals/corr/abs-1907-05168] to
$256(3k+\lfloor 2k/3\rfloor-1)$, whereas for the class of $1$-planar graphs
our improvement is from $30\cdot 4^{4}$ to $6\cdot 4^{4}$, which is a bound
that notably holds also for optimal $2$-planar graphs (Corollary 16).

  * •

$p$-centered chromatic number: Theorem 2 allows us to improve the best-known
upper bound on the non-repetitive chromatic number of $k$-map graphs from
$O(k^{2}p^{10})$ [DBLP:journals/corr/abs-1907-05168] to $O(kp^{3}\log p)$,
whereas for the class of $1$-planar graphs our improvement is from $O(p^{4})$
to $O(p^{3}\log p)$, and this bound also holds for optimal $2$-planar graphs
(Corollary 18).

  * •

Twin-width: Theorem 19 improves the current-best upper bound on the twin-width
of planar graphs from $183$ [DBLP:journals/corr/abs-2201-09749] to $37$. For
the class of $1$-planar and optimal $2$-planar graphs, Theorem 22 improves the
bound from $O(1)$ [DBLP:journals/jacm/BonnetKTW22] to $80$, whereas our
improvement for $k$-map graphs is limited to certain value of $k$, as these
graphs have bounded twin-width independently of $k$
[DBLP:journals/jacm/BonnetKTW22].

##  2 Preliminaries

(a)

(b)

Figure 1: Illustration of: (a) a $4$-framed topological graph whose skeleton
edges (crossing edges) are black (blue), and (b) the strong product
$X\boxtimes Y$ of a planar graph $X$ (red) and a path $Y$ (blue).

For standard graph-theoretic terminology and notation we refer the reader,
e.g., to [DBLP:books/daglib/0030488].

Graphs. A graph is _simple_ if it contains neither loops nor multi-edges. For
a general graph $G$ (not-necessarily simple), let $\mathrm{si}(G)$ denote the
_simplification_ of $G$, i.e., the simple graph obtained from $G$ by removing
all loops and replacing each bunch of parallel edges with a single edge. For
any $i\geq 1$, the _$i$ -th power_ $G^{i}$ of an graph $G$ is the graph with
the same vertex set as $G$, in which two vertices are adjacent if and only if
they are at distance at most $i$ in $G$. Clearly, $G\subseteq G^{i}$. A graph
$H$ is a _minor_ of a graph $G$, if $H$ can be obtained from a subgraph of $G$
by contracting edges.

Topological graphs. A _topological graph_ is a graph drawn on the plane such
that any two edges cross in at most one point and no edge crosses itself. In
this paper, we will solely consider topological graphs in which no two
adjacent edges cross and no three edges cross in the same point (in the
literature, such drawings are commonly referred to as “simple”). A _plane
graph_ is a topological graph with no crossing edges. A graph is _$k$ -planar_
if it is isomorphic to a topological graph in which each edge crosses at most
$k$ other edges. Furthermore, a $k$-planar graph of maximum density is called
_optimal_. A _$k$ -map graph_ is one that admits a _$k$ -map_, i.e., a contact
representation on the sphere, where each vertex is a region isomorphic to a
closed disk and no more than $k$ regions share the same boundary point. Given
a topological graph $G$, the subgraph $\operatorname{sk}(G)$ of a topological
graph $G$ consisting of all its vertices and uncrossed edges is the _skeleton_
of $G$; refer to Fig. 1(a). A topological graph $G$ whose skeleton
$\operatorname{sk}(G)$ is biconnected is called _$h$ -framed_
[DBLP:conf/compgeom/BekosLGGMR20], if all the faces of $\operatorname{sk}(G)$
have size at most $h$, and _internally $h$-framed_, if all the faces of
$\operatorname{sk}(G)$, except for possibly one, have size at most $h$. The
importance of this class lies in the following connections with $k$-planar and
$k$-map graphs [DBLP:journals/corr/abs-2003-07655,
DBLP:conf/compgeom/BekosLGGMR20]. Optimal $1$-planar and optimal $2$-planar
graphs are $4$\- and $5$-framed, respectively, while general $1$-planar graphs
can be augmented to $8$-framed graphs, if multi-edges are forbidden, or to
$4$-framed graphs, if multi-edges are allowed. Finally, note that any $k$-map
graph is a subgraph of a $2k$-framed graph.

Treewidth. Let $(\mathcal{X},T)$ be a pair such that
$\mathcal{X}=\\{X_{1},X_{2},\dots,X_{\ell}\\}$ is a collection of subsets of
vertices of a graph $G$, called _bags_ , and $T$ is a tree whose nodes are in
one-to-one correspondence with the elements of $\mathcal{X}$. The pair
$(\mathcal{X},T)$ is a _tree-decomposition_ of $G$ if it satisfies the
following two conditions: (i) for every edge $(u,v)$ of $G$, there exists a
bag $X_{i}\in\mathcal{X}$ that contains both $u$ and $v$, and (ii) for every
vertex $v$ of $G$, the set of nodes of $T$ whose bags contain $v$ induces a
non-empty subtree of $T$. The _width_ of a tree-decomposition
$(\mathcal{X},T)$ of $G$ is $\max_{i=1}^{\ell}{|X_{i}|}-1$, while the
_treewidth_ $\mathrm{tw}(G)$ of $G$ is the minimum width over all tree-
decomposition of $G$.

Quotient graph. For a graph $G$ and a partition ${\mathcal{P}}$ of $V(G)$, the
_quotient of $G$ by ${\mathcal{P}}$_, denoted by $G/{\mathcal{P}}$, is a graph
containing a vertex $v_{P}$ for each part $P$ in $\mathcal{P}$ (we say that
$v_{P}$ _stems from_ $P$) and an edge $(v_{P^{\prime}},v_{P^{\prime\prime}})$
if and only if there exists a vertex in $P^{\prime}$ adjacent to a vertex in
$P^{\prime\prime}$ in $G$. Note that, $G/{\mathcal{P}}$ is a minor of $G$, if
every part in ${\mathcal{P}}$ induces a connected subgraph of $G$.

Strong product. The _strong product_ of two graphs $X$ and $Y$, denoted by
$X\boxtimes Y$, is the graph whose vertex-set $V(X\boxtimes Y)$ is the
Cartesian product $V(X)\times V(Y)$, such that there exists an edge in
$E(X\boxtimes Y)$ between the vertices $\langle x_{1},y_{1}\rangle,\langle
x_{2},y_{2}\rangle\in V(X\boxtimes Y)$ if and only if one of the following
occurs: (a) $x_{1}=x_{2}$ and $(y_{1},y_{2})\in E(Y)$, (b) $y_{1}=y_{2}$ and
$(x_{1},x_{2})\in E(X)$, or (c) $(x_{1},x_{2})\in E(X)$ and $(y_{1},y_{2})\in
E(Y)$; see Fig. 1(b). Dujmovic et al. [DBLP:journals/jacm/DujmovicJMMUW20,
DBLP:journals/corr/abs-1907-05168] and Ueckerdt, Wood, and Yi
[DBLP:journals/corr/abs-2108-00198] showed the following main graph product
structure results.

######  Theorem 1 (Dujmovic et al. [DBLP:journals/jacm/DujmovicJMMUW20,
DBLP:journals/corr/abs-1907-05168], Ueckerdt et al.
[DBLP:journals/corr/abs-2108-00198]).

For a graph $G$, the next hold:

  1. a.

If $G$ is planar, then $G\subseteq P\boxtimes H$, for a path $P$ and a planar
graph $H$ with $\mathrm{tw}(H)\leq 6$.

  2. b.

If $G$ is planar, then $G\subseteq P\boxtimes H\boxtimes K_{3}$, for a path
$P$ and a planar graph $H$ with $\mathrm{tw}(H)\leq 3$.

  3. c.

If $G$ is $1$-planar, then $G\subseteq P\boxtimes H\boxtimes K_{30}$, for a
path $P$ and a planar graph $H$ with $\mathrm{tw}(H)\leq 3$.

  4. d.

If $G$ is $k$-planar with $k>1$, then $G\subseteq P\boxtimes H\boxtimes
K_{18k^{2}+48k+30}$, for a path $P$ and a graph $H$ with
$\mathrm{tw}(H)\leq\frac{1}{6}(k+4)(k+3)(k+2)-1$.

  5. e.

If $G$ is a $k$-map graph, then $G\subseteq P\boxtimes H\boxtimes
K_{21k(k-3)}$, for a path $P$ and a graph $H$ with $\mathrm{tw}(H)\leq 9$.

Layering. Consider a graph $G$. A _layering_ of $G$ is an ordered partition
$(V_{0},V_{1},\dots)$ of $V(G)$ such that, for every edge $(v,w)$ of $G$ with
$v\in V_{i}$ and $w\in V_{j}$, it holds $|i-j|\leq 1$. If $i=j$, then $(v,w)$
is an _intra-level edge_ ; otherwise, $(v,w)$ is an _inter-level edge_. Each
part $V_{i}$ is called a _layer_. Let $T$ be a BFS-tree of $G$ rooted at a
vertex $r$. The _BFS layering_ of $G$ _determined by $T$_ is the layering
$(V_{0},V_{1},\ldots)$ of $G$ such that $V_{i}$ contains all vertices of $G$
at distance $i$ from $r$. Given a partition $\mathcal{P}$ of $V(G)$ and a
layering $\mathcal{L}$ of $G$, the _layered width of $\mathcal{P}$ with
respect to $\mathcal{L}$_ is the size of the largest set obtained by
intersecting a part in $\mathcal{P}$ and a layer in $\mathcal{L}$. The
_layered width_ of $\mathcal{P}$ is the minimum layered width of $\cal P$ over
all layerings of $G$.

##  3 Computing the Product Structure

This section is devoted to the proof of a product structure theorem for
$h$-framed graphs, summarized in the next theorem; several applications of
this result are presented in Section 4.

######  Theorem 2 (Product Structure Theorem for $h$-Framed Graphs).

Let $G$ be a not-necessarily simple $h$-framed graph with $h\geq 3$. Then,
$\mathrm{si}(G)$ is a subgraph of the strong product $H\boxtimes P\boxtimes
K_{3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1}$, where $H$ is a planar graph
with $\mathrm{tw}(H)\leq 3$ and $P$ is a path.

The algorithm supporting Theorem 2 is going to recursively decompose the graph
$G$ into parts with special properties, such that the resulting quotient graph
will be $H$, and the additional properties of the constructed partition will
imply the claimed product structure. We start with a technical setup followed
by the core recursion in Lemma 4.

Layering $\mathbf{G}$. Let $T$ be a BFS tree of $\operatorname{sk}(G)$ rooted
at an arbitrary vertex $r$ incident to the outer face of
$\operatorname{sk}(G)$. For an arbitrary $H$ and its implicitly fixed BFS tree
$T^{\prime}\subseteq H$ (such as $H=\operatorname{sk}(G)$ and $T^{\prime}=T$
in our case), we call a path $P\subseteq\operatorname{sk}(G)$ _vertical_ if
$P$ is a subpath of some root-to-leaf path of $T^{\prime}$. Let
$\mathcal{L}=(V_{0},V_{1},\ldots,V_{b})$ be the BFS layering of
$\operatorname{sk}(G)$ determined by $T$. Observe that, if $P$ is a vertical
path in $\operatorname{sk}(G)$, then $P$ intersects every part of
${\mathcal{L}}$ in at most one vertex. Given $\mathcal{L}$, we define a new
ordered partition $\mathcal{W}=(W_{0},W_{1},\dots,W_{\ell})$ of the vertex set
of $G$ with $\ell=\big{\lceil}b/\lfloor\frac{h}{2}\rfloor\big{\rceil}-1$, by
merging consecutive $\lfloor\frac{h}{2}\rfloor$-tuples of layers of
${\mathcal{L}}$. This is done as follows. For $i=0,1,\ldots,\ell$, we let
$W_{i}:=\bigcup_{j=0}^{\lfloor h/2\rfloor-1}V_{i\lfloor h/2\rfloor+j}$
(assuming $V_{x}=\emptyset$ if $x>b$). Then,
${\mathcal{W}}:=(W_{0},W_{1},\ldots,W_{\ell})$ is a layering of $G$, as we
formally prove below.

######  Property 3.

${\mathcal{W}}:=(W_{0},W_{1},\ldots,W_{\ell})$ is a layering of $G$.

###### Proof.

As for the edges of $\operatorname{sk}(G)$, we have that intra-level edges of
$\cal L$ are also intra-level edges of $\cal W$, whereas inter-level edges of
$\cal L$ are either intra-level edges or inter-level edges of $\cal W$. Next,
we argue about the crossing edges of $G$. First, observe that each such an
edge is a chord in some face of $\operatorname{sk}(G)$. Also, every chord of a
face $f$ of $\operatorname{sk}(G)$ has its ends at distance at most
$\lfloor\frac{h}{2}\rfloor$ along $f$. This implies that $G$ does not contain
an edge with $(u,v)$ with $u\in W_{i}$ and $v\in W_{j}$ with $|i-j|>1$, which
in turn implies that $\mathcal{W}$ is a layering of $G$. ∎

Partitioning $\mathbf{G}$. The core of our algorithm is a construction of a
special partition ${\mathcal{R}}$ of $V(G)$ such that $H=G/{\mathcal{R}}$ is a
planar graph with $\mathrm{tw}(H)\leq 3$, and the layered width of
${\mathcal{R}}$ with respect to ${\mathcal{W}}$ is not large. Our recursive
decomposition of $G$ is analogous to the one in
[DBLP:journals/jacm/DujmovicJMMUW20] (as applied to planar graphs); however
several non-trivial changes are needed to exploit the existence of the
underlying (plane) skeleton of $G$. The algorithm starts from the outer face
and recursively “dive” into gradually-shrinking areas of $G$.

Central in our approach is the following notion. For a cycle
$C\subseteq\operatorname{sk}(G)$, 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$. Consider a subset
$U\subseteq V(G)$. For the partition ${\mathcal{L}}$ (resp., the partition
${\mathcal{W}}$), the _width of $U$ with respect to ${\mathcal{L}}$_ (resp.
_to ${\mathcal{W}}$_), denoted by $\lambda_{{\mathcal{L}}}(U)$ (resp. by
$\lambda_{{\mathcal{W}}}(U)$), is the largest size of a set obtained by
intersecting $U$ and a part of $\mathcal{L}$ (resp. of ${\mathcal{W}}$). We
are now ready to present our main technical lemma.

######  Lemma 4.

Let $G$ be an $h$-framed graph with $h\geq 3$ and let ${\mathcal{L}}$ be a
BFS-layering of $G$. Also, let $C$ be a cycle in $\operatorname{sk}(G)$, and
let $G_{C}$ be the subgraph of $G$ bounded by $C$. Further, for some
$k\in\\{1,2,3\\}$, let $P_{1},\ldots,P_{k}$ be paths belonging to $C$ such
that $\mathcal{R}^{0}=\\{X_{i}:X_{i}:=V(P_{i}),1\leq i\leq k\\}$ is a
partition of $V(C)$. Then, it is possible to construct in quadratic time a
_good_ partition ${\mathcal{R}}^{\prime}$ of $V(G_{C})$, i.e., one that
satisfies the following properties:

  1. 1.

$\mathcal{R}^{\prime}\supseteq{\mathcal{R}}^{0}$, and for every part
$X\in\mathcal{R}^{\prime}\setminus{\mathcal{R}}^{0}$, there exist
$q\in\\{1,2,3\\}$ and $X^{\prime}\subseteq X$ such that111The somehow
technical Property 1 of Lemma 4 will imply that
$\lambda_{{\mathcal{W}}}(X)\leq 3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1$ in
the proof of Theorem 2, but we will also make use of the stated more detailed
treatment.

     * •

$X\setminus X^{\prime}$ is a union of the vertex sets of at most $q$ vertical
paths of $\operatorname{sk}(G)$, and so, in particular,
$\lambda_{{\mathcal{L}}}(X\setminus X^{\prime})\leq q$, and

     * •

$|X^{\prime}|\leq h-3$ if $q=1$, $|X^{\prime}|\leq\lfloor(h-1)/2\rfloor-1$ if
$q=2$, and $|X^{\prime}|\leq\lfloor h/3\rfloor-1$ if $q=3$.

  2. 2.

the quotient graph $H^{\prime}=G_{C}/{\mathcal{R}}^{\prime}$ is a planar graph
with $\mathrm{tw}(H^{\prime})\leq 3$, and

  3. 3.

the vertices of $H^{\prime}$ that stem from $X_{i}$, with $1\leq i\leq k$, are
incident to the same face of $H^{\prime}$ and induce a clique (i.e., either a
vertex, or an edge, or a triangle).

###### Proof.

We prove Lemma 4 by providing a recursive procedure describe in the following.
In the base case of the recursion occurs when $V(G_{C})=V(C)$ (i.e., there are
no vertices in the interior of $C$ and the edges in $E(G_{C})\setminus E(C)$
are chords of $C$). In this case, the algorithm returns the partition
${\mathcal{R}}^{\prime}={\mathcal{R}}^{0}$, which is clearly good since the
graph $H^{\prime}$ is a plane clique of size $k$ whose vertices stem from the
parts of ${\mathcal{R}}^{0}$. Note that, if $|E(G_{C})\setminus E(C)|=0$, then
$V(G_{C})=V(C)$, since $G_{C}$ cannot have isolated vertices. In the recursive
step of the algorithm, we assume that there exist vertices and edges of
$G_{C}$ that lie in the interior of $C$. Our aim is to recurse on instances
that contain fewer edges in the interior, but not on the boundary, of the
cycle bounding their outer face. We first need to handle a possible degenerate
case222Such a case does not explicitly occur in the planar proof of
[DBLP:journals/jacm/DujmovicJMMUW20], but the implicit case of a so-called
[DBLP:journals/jacm/DujmovicJMMUW20] “tripod” with degenerate legs is
analogous to what we are defining here. of $G_{C}$. Recall that, since $G$ is
$h$-framed, all bounded faces of $G_{C}\cap\operatorname{sk}(G)$ have length
at most $h$.

(a)

(b)

(c)

Figure 2: Illustrations of graph $C\cup D$ for the separable case of $G_{C}$
(Definition 1). The number $a$ of $\tau$-faces is $4$ in (a) and $1$ in (b).
(c) A case when Property 2 of Definition 1 is not met (by $\tau_{4}$).

######  Definition 1.

We say that $G_{C}$ is _separable_ if the following conditions hold (see Fig.
2):

  1. 1.

The plane graph $G_{C}\cap\operatorname{sk}(G)$ contains a bounded face
$\sigma_{0}$ that intersects $C$ in $a\geq 1$ disjoint subpaths (some of the
paths may consist of single vertices). Denoting by $D$ the facial cycle of
$\sigma_{0}$, let $\tau_{1},\ldots,\tau_{a}$ be the bounded faces of the plane
graph $C\cup D$ other than $\sigma_{0}$.

  2. 2.

For each $\tau_{j}$, with $j=1,\ldots,a$, the boundary of $\tau_{j}$ is a
cycle $C_{j}$ of $\operatorname{sk}(G)$, at most two parts of
${\mathcal{R}}^{0}$ intersect $C_{j}$, and every part of ${\mathcal{R}}^{0}$
intersecting $C_{j}$ does so in a single subpath.333A part of
${\mathcal{R}}^{0}$ indeed may intersect the boundary $C_{j}$ of $\tau_{j}$ in
two subpaths (see Fig. 2(c)). This, however, can happen only if $k\leq 2$.

Separable case. Suppose that $G_{C}$ is separable and let $G_{j}$,
$j=1,\ldots,a$, denote the subgraph of $G_{C}$ bounded by the facial cycle
$C_{j}$ of $\tau_{j}$. Note that, if $a=1$, we have $|V(D)\cap V(C)|\geq 2$,
since otherwise the face $\tau_{1}$ would not be bounded by a cycle as
required by Definition 1. This implies that $|E(G_{j})\setminus
E(C_{j})|<|E(G_{C})\setminus E(C)|$ (even when $a=1$). Also, let $Y$ denote
the vertices of $D$ that do not belong to $C$, i.e., $Y=V(D)\setminus V(C)$;
refer to the hollow vertices of Fig. 2. By the previous, we have
$|Y|\leq|D|-2\leq h-2$. For $j=1,\ldots,a$, let ${\mathcal{R}}^{0}_{j}$ be the
partition of $V(C_{j})$ consisting of the set $Y_{j}=Y\cap V(C_{j})$, if it is
not empty, and of the sets $X^{j}_{i}=X_{i}\cap V(C_{j})$, $i=1,\dots,k$, if
$X^{j}_{i}$ is not empty; by Property 2 of Definition 1, $R^{0}_{j}$ consists
of at most three parts. Therefore, by a recursive application of our
algorithm, each graph $G_{j}$, $j=1,\ldots,a$, admits a good partition
$\mathcal{R}_{j}\supseteq{\mathcal{R}}^{0}_{j}$ of $V(G_{j})$. We construct a
partition ${\mathcal{R}}^{\prime}$ of $V(G_{C})$ by putting into
${\mathcal{R}}^{\prime}$ the parts of ${\mathcal{R}}_{0}$, the set $Y$ (if
non-empty), and the recursively obtained parts of each $G_{j}$ that do not
touch $C_{j}$; formally,
${\mathcal{R}}^{\prime}={\mathcal{R}}_{0}\cup\\{Y\\}\cup\bigcup_{j=1,\ldots,a}({\mathcal{R}}_{j}\setminus{\mathcal{R}}^{0}_{j})$,
or
${\mathcal{R}}^{\prime}={\mathcal{R}}_{0}\cup\bigcup_{j=1,\ldots,a}({\mathcal{R}}_{j}\setminus{\mathcal{R}}^{0}_{j})$
if $Y=\emptyset$. Note that ${\mathcal{R}}^{\prime}$ is indeed a partition of
$V(G_{C})$, since each vertex of $G_{C}$ that lies in the interior of $C$ must
belong either to $Y$ or to a part
$X\in{\mathcal{R}}_{j}\setminus{\mathcal{R}}^{0}_{j}$, for some
$j\in\\{1,\dots,a\\}$. To prove that ${\mathcal{R}}^{\prime}$ is good, we need
a preliminary property given below.

######  Property 5.

Under the conditions of Lemma 4, no vertex of any part from
${\mathcal{R}}^{\prime}\setminus{\mathcal{R}}^{0}$ is adjacent to a vertex of
$V(G)\setminus V(G_{C})$.

###### Proof.

Since ${\mathcal{R}}^{0}$ partitions $V(C)$, and $C$ is a cycle in
$\operatorname{sk}(G)$, the drawing of $C$ is an uncrossed simple closed curve
in the topological graph $G$, and hence, by the Jordan curve theorem, no edge
of $G$ can have one end in $V(G_{C})\setminus V(C)$ and the other end in
$V(G)\setminus V(G_{C})$. ∎

We are now ready to show that the constructed partition
${\mathcal{R}}^{\prime}$ is good.

######  Claim 6.

The partition ${\mathcal{R}}^{\prime}$ constructed for the separable case of
$G_{C}$ is good.

###### Proof.

For our proof, we use Property 5 mentioned above, which we can further assume
that it holds also for the recursive calls. First, we look at Property 1 of
Lemma 4: this property holds true for every
$X\in{\mathcal{R}}^{\prime}\setminus({\mathcal{R}}_{0}\cup\\{Y\\})$ by the
recursive construction, and for $X=Y$ we pick any $y\in Y$ and set
$Y^{\prime}=Y\setminus\\{y\\}$, and by the previous we get
$|Y^{\prime}|\leq|Y|-1\leq h-2-1=h-3$ and $Y\setminus Y^{\prime}=\\{y\\}$ is a
trivial vertical path.

It remains to analyze planarity and treewidth of the quotient graph
$H^{\prime}$. Recall that we have recursively obtained the planar quotient
graphs $H_{j}:=G_{j}/{\mathcal{R}}_{j}$, for $j\in\\{1,\dots,a\\}$, and we may
assume, from the recursive invocation of Property 3, that each $H_{j}$ is a
plane topological graph with the vertices stemming from the parts of
${\mathcal{R}}^{0}_{j}$ on the outer face. For further reference, we call
these vertices stemming from ${\mathcal{R}}^{0}_{j}$ the _connectors_ of
$H_{j}$. By Property 5 following a recursive invocation of Lemma 4, no
vertices of $H_{j}$ other than the connectors will be adjacent to vertices of
$H^{\prime}$ outside of $H_{j}$.

We start with drawing a plane $(k+1)$-clique $Q$ on the vertices stemming from
the non-empty parts in ${\mathcal{R}}^{0}\cup\\{Y\\}$. If $k=2$, then at most
two of the graphs $G_{j}$ with $j\in\\{1,\dots,a\\}$ intersect both parts of
${\mathcal{R}}^{0}$, and for them we embed the corresponding (at most two)
plane graphs $H_{j}$ into the two triangular faces of $Q$, such that the
vertices of $Q$ are naturally identified with the connectors of $H_{j}$. The
remaining quotient graphs $H_{j}$ are then embedded into the drawing easily,
since the connectors of each of them is identified with only one or two
vertices of $Q$. Likewise, the desired plane drawing of $H^{\prime}$ is
trivial if $k=1$. If $k=3$, then each pair of parts of ${\mathcal{R}}^{0}$ is
intersected together by at most one of the graphs $G_{j}$, and then we embed
the plane quotient graph $H_{j}$ into the corresponding triangular face of
$Q$, with the appropriate identification of the connectors of $H_{j}$ as in
the case of $k=2$. Again, the remaining quotient graphs $H_{j}$ are embedded
easily.

Altogether, we have obtained a plane drawing of $H^{\prime}$ such that the
vertices stemming from the parts of ${\mathcal{R}}^{0}$ are on the same face;
in particular, for $k=3$, this is the triangular face of $Q$ not containing
the vertex which stems from the part $Y$. Moreover, the $k$ parts of
${\mathcal{R}}^{0}$ are indeed pairwise adjacent in $G_{C}$ already by edges
of $C$. We have thus verified Property 3 of Lemma 4, and it remains to verify
Property 2 in the aspect of treewidth of $H^{\prime}$. We have recursively
obtained, for each $j\in\\{1,\dots,a\\}$, a tree-decomposition
${\mathcal{T}}_{j}$ of the graph $H_{j}$, such that (by a folklore property of
tree-decompositions) the clique of the vertices which stem from
${\mathcal{R}}_{j}^{0}$ is contained in a node $\nu_{j}$ of it. We create a
new decomposition ${\mathcal{T}}$ of $H^{\prime}$ from the disjoint union of
${\mathcal{T}}_{j}$ over $j=1,\ldots,a$ by adding a new node $\nu$, holding
the bag of vertices $V(Q)$ and adjacent exactly to all $\nu_{j}$. Further, for
$i=1,\dots,k$, we rename each vertex of $\mathcal{T}_{j}$ that stems from
$X^{j}_{i}$, with $i=1,\dots,a$, as the vertex in $Q$ that stems from $X_{i}$
and, for $i=1,\dots,a$, we rename each vertex of $\mathcal{T}_{j}$ that stems
from $Y_{i}$ as the vertex in $Q$ that stems from $Y$. This is a valid tree-
decomposition by Property 5, and it is of width at most $3$ by Property 2 and
the fact that $|V(Q)|-1=k\leq 3$. ∎

General case.

(a)

(b)

(c)

Figure 3: Illustrations of graph $C\cup D$ for the general case of $G_{C}$,
for $k=1$ (a) and $k=2$ (b)(c).

Now we move to the general (i.e., not-necessarily separable) case of $G_{C}$
in Lemma 4. If $\mathbf{k=1}$, we pick the bounded face $\sigma_{0}$ of
$G_{C}\cap\operatorname{sk}(G)$ incident to the single edge of $E(C)\setminus
E(P_{1})$; refer to Fig. 3(a). The face $\sigma_{0}$ then witnesses the
separable case for $G_{C}$, by Definition 1, which is solved as above. If
$\mathbf{k=2}$, then we pick $e_{0}\in E(C)$ as one of the edges joining
$P_{1}$ and $P_{2}$ on $C$, and $\sigma_{0}$ as the bounded face of
$G_{C}\cap\operatorname{sk}(G)$ incident to $e_{0}$; see Figs. 3(b) and 3(c).
Then we are back to the separable case for $G_{C}$ with $\sigma_{0}$, by
Definition 1.

In the remainder, we assume $\mathbf{k=3}$. First, we color every vertex $v$
of $G_{C}$ by the color $i\in\\{1,2,3\\}$ if the (unique) path in the BFS tree
$T$ from $v$ to the root $r$ hits $V(P_{i})$ before possibly hitting other
parts of ${\mathcal{R}}^{0}$. In particular, the vertices of $P_{i}$ are
colored $i$. Our aim is to find, in the plane graph
$F:=G_{C}\cap\operatorname{sk}(G)$, a bounded face $\sigma_{1}$ containing
vertices of all the three colors on its boundary. There our arguments divert
from those used in [DBLP:journals/jacm/DujmovicJMMUW20]—since $F$ is generally
not a near-triangulation, and we additionally need that the face $\sigma_{1}$
intersects the boundary cycle $C$ at most once (which requires additional
care). We next prove that there exists a cycle $R$ bounding a bounded face
$\sigma_{1}$ of $F$, such that $V(R)$ contains all three of our colors, and
$R$ intersects $C$ in at most one connected piece. Furthermore, the colors on
$R$ appear in three consecutive sections. To show this claim, we need the next
definition.

(a)

(b)

(c)

(d)

Figure 4: Illustrations for: (a) Graph $F$ and a zone $F_{1}$. (b) Graph
$F_{3}$. (c) The tri-colored face $\sigma_{3}$ in $F_{3}$. (d) The desired
face $\sigma_{1}$ in $F$.

######  Definition 2.

A plane subgraph $F_{1}\subseteq F$ is a _zone of $F$_ if the following hold
(see Fig. 4(a)):

  * •

every vertex in $V(F_{1})\cap V(C)$ is of degree at least $2$ in $F_{1}$,

  * •

no vertex in $V(F)\setminus V(F_{1})$ is adjacent to a vertex in
$V(F_{1})\setminus V(C)$, and

  * •

in the plane drawing of $F_{1}$ inherited from $G_{C}$, every vertex from
$V(F)\setminus V(F_{1})$ is drawn in the outer face of $F_{1}$.

Note that, similarly to Definition 1, if a facial cycle $D$ in $F$ intersects
$C$ in two or more places, then each of the remaining bounded faces of the
plane subgraph $C\cup D$ bounds a zone of $F$. We say that the face of $D$
_divides_ $F$ into these zones.

For our proof, we pick $F_{1}$ as an inclusion-minimal zone of $F$ such that
$V(F_{1})$ intersects all three parts of ${\mathcal{R}}^{0}$ (i.e., $F_{1}$
meets all three colors on $C$). We claim that we can assume that there is no
bounded face $\sigma_{0}$ of $F_{1}$ such that $\sigma_{0}$ intersects $C$ in
at least two disjoint subpaths. On the contrary, suppose that such
$\sigma_{0}$ exists in $F_{1}$. Then $F_{1}$ can be divided into smaller zones
which, by the minimality of $F_{1}$, each intersects at most two parts of
${\mathcal{R}}^{0}$. However, the same then holds for the zones into which
$\sigma_{0}$ divides the whole $F$, and so $\sigma_{0}$ witnesses the case of
separable $G_{C}$ already solved, as can be easily checked from Definition 1.
We take the graph $C\cup F_{1}$ and temporarily replace (i.e., “shortcut”)
each maximal path of $C-E(F_{1})$ by a single new edge. Let $F_{2}$ be the
resulting graph (so, $V(F_{1})=V(F_{2})$), and $F_{3}$ be an arbitrary
completion of $F_{2}$ to a plane near-triangulation on the same vertex set,
i.e., obtained by adding edges into the bounded faces of $F_{2}$; refer to
Fig. 4(b). Now, in the inherited coloring of $V(F_{3})\subseteq V(G_{C})$, the
outer face of $F_{3}$ sees all three colors in a way expected by Sperner’s
Lemma444We adopt the following well-known variant of Sperner’s Lemma: Let $G$
be a near-triangulation whose vertices are colored with three colors, where
the vertices of the cycle $C$ bounding the outer face of $G$ belonging to each
color class form a single subpath of $C$. Then $G$ contains an internal face
whose vertices have all the three colors [DBLP:books/daglib/0019107]., and by
this lemma we can thus find a tri-colored triangular face $\sigma_{3}$ of
$F_{3}$; refer to Fig. 4(c). By planarity of $F$ and $F_{3}$, there is a
unique face $\sigma_{1}$ of $F$ containing $\sigma_{3}$; refer Fig. 4(d). Let
$R\subseteq V(F)$ denote the facial cycle of $\sigma_{1}$ ($R$ is a cycle
since the skeleton $\operatorname{sk}(G)$ is $2$-connected). We have that
$V(R)$ contains all three of our colors, and $R$ intersects $C$ in at most one
connected piece by our choice of $F_{1}$. Furthermore, the colors on $R$
appear in three consecutive sections since the paths of the BFS tree $T$ do
not cross in the plane graph $F$. This concludes the proof of our initial
claim.

(a) Case C.1

(b) Case C.2

(c) Case C.3

(d) Case C.3

Figure 5: Illustrations for the representatives $t_{1}$, $t_{2}$, and $t_{3}$,
and the vertical paths $R_{1}$, $R_{2}$, and $R_{3}$. The vertices of $R$
bound the gray shaded region. $R^{\prime}$ is depicted with black thick edges.

Next, consider the set $V(R)\cap V(C)$. If this set contains all three colors,
then all three colors occur on the path $R_{0}:=C\cap R$, and one of them, say
color $1$, occurs only on internal vertices of $R_{0}$ (and nowhere else on
$C$). In this case, the face $\sigma_{1}$ again witnesses the case of
separable $G_{C}$ with $a=1$ which is solved as above. If, instead, the set
$V(R)\cap V(C)$ does not contain all three colors, then we choose on $R$
representatives – vertices $t_{i}\in V(R)$ of color $i$ where $i=1,2,3$, as in
one of the following three possible cases of $V(R)\cap V(C)$ (refer to Figs. 5
and 5(d)):

  1. C.1

If $V(R)\cap V(C)$ contains two colors, say $1$ and $2$, we choose
$t_{1},t_{2}\in V(R)\cap V(C)$ as neighbors on $C$ and $t_{3}\in V(R)\setminus
V(C)$ arbitrarily; refer to Fig. 5(a).

  2. C.2

If $V(R)\cap V(C)$ contains one color, say $1$, we choose $t_{1}\in V(R)\cap
V(C)$ arbitrarily and pick $t_{2},t_{3}\in V(R)\setminus V(C)$ such that
$t_{2}t_{3}\in E(R)$ (this is unique). Furthermore, up to symmetry between the
colors $2$ and $3$, we may assume that the distance on $R$ between $t_{2}$ and
$V(C)$ is not smaller than the distance on $R$ between $t_{3}$ and $V(C)$;
refer to Fig. 5(b).

  3. C.3

If $V(R)\cap V(C)=\emptyset$, then, up to symmetry between the colors, we may
assume that the color $3$ occurs in $V(R)$ no more times than each of the
colors $1$ and $2$. We then choose $t_{3}\in V(R)$ arbitrarily (of color $3$),
and set $t_{1}$ and $t_{2}$ to the two (unique) vertices colored $1$ and $2$
on $R$ that are neighbors of vertices of color $3$ on $R$; refer to Figs. 5(c)
and 5(d).

For $i=1,2,3$, let $R_{i}$ denote the unique vertical path in $T$ from $t_{i}$
to $V(P_{i})$; see Figs. 5 and 5(d). Note that some vertices $t_{i}$ may lie
on $C$, and then $R_{i}=t_{i}$ is a single-vertex path. Let $Q$ be the subpath
of $R$ with the ends $t_{1}$ and $t_{2}$ and avoiding $t_{3}$. We define
$R^{\prime}\subseteq R$ as the subpath or cycle (in the case $R^{\prime}=R$)
obtained from $R$ by deleting all internal vertices of $Q$. Finally, we set
$R^{+}:=R^{\prime}\cup R_{1}\cup R_{2}\cup R_{3}$ which is a connected
subgraph of $F$ ($R^{+}$ will play the same role here as the so-called tripods
in [DBLP:journals/jacm/DujmovicJMMUW20]).

Observe that $C\cup R^{+}$ is a $2$-connected plane graph (in each of the
three cases above), which has $a\in\\{2,3\\}$ bounded faces
$\tau_{1},\ldots,\tau_{a}$ that are moreover distinct from $\sigma_{1}$ in the
case of $R^{\prime}=R$; for the latter see Fig. 5(c). We denote by $C_{j}$,
$j\in\\{1,\ldots,a\\}$, the facial cycle of $\tau_{j}$. It is now important to
notice that each cycle $C_{j}$ intersects at most two parts of
${\mathcal{R}}^{0}$, which follows from our “multi-colored” choice of
$t_{1},t_{2},t_{3}$ and $R_{1},R_{2},R_{3}$ in all three cases. Furthermore,
every two parts of ${\mathcal{R}}^{0}$ are together intersected by at most one
of $C_{j}$.

We next proceed similarly as in the separable case above. Let $G_{j}\subsetneq
G_{C}$, $j\in\\{1,\ldots,a\\}$, be the strict subgraph of $G_{C}$ bounded by
$C_{j}$, and let ${\mathcal{R}}^{0}_{j}$ be the partition of $V(C_{j})$
consisting of $V(C_{j})\setminus V(C)$ and of the non-empty parts $X\cap
V(C_{j})$ over $X\in{\mathcal{R}}^{0}$. So, $|{\mathcal{R}}^{0}_{j}|\leq 3$.
Therefore, by a recursive application of our algorithm, we may assume that
each graph $G_{j}$ admits a good partition
$\mathcal{R}_{j}\supseteq{\mathcal{R}}^{0}_{j}$ of $V(G_{j})$, with
$j=1,\ldots,a$.

We construct a partition ${\mathcal{R}}^{\prime}\supseteq{\mathcal{R}}^{0}$ of
$V(G_{C})$ similarly as before; besides ${\mathcal{R}}^{0}$ we add the set
$Z:=V(R^{+})\setminus V(C)\not=\emptyset$ as whole, and the recursively
obtained parts of each $G_{j}$ that do not touch $C_{j}$. Formally,
${\mathcal{R}}^{\prime}={\mathcal{R}}_{0}\cup\\{Z\\}\cup\bigcup_{j=1,\ldots,a}({\mathcal{R}}_{j}\setminus{\mathcal{R}}^{0}_{j})$.
Note that ${\mathcal{R}}^{\prime}$ is a partition of $V(G_{C})$ —in
particular, each vertex of $G_{C}$ which is not on $C$ must belong either to
$Z$ or to a part $X\in{\mathcal{R}}_{j}\setminus{\mathcal{R}}^{0}_{j}$, for
some $j\in\\{1,\dots,a\\}$, by induction. We next show that the constructed
partition ${\mathcal{R}}^{\prime}$ is good.

######  Claim 7.

The partition ${\mathcal{R}}^{\prime}$ constructed for the general case of
$G_{C}$ is good.

###### Proof.

Property 1 of Lemma 4 holds true for every
$X\in{\mathcal{R}}^{\prime}\setminus({\mathcal{R}}_{0}\cup\\{Z\\})$ by
recursion. For $X=Z$ we argue as follows. We choose $Z^{\prime}:=Z\setminus
V(R_{1}\cup R_{2}\cup R_{3})\subseteq R^{\prime}$, and argue according to the
Cases (C.1)–(C.3) that we distinguished for $V(R)\cap V(C)$. In the Case
(C.1), i.e., $t_{1},t_{2}\in V(C)$, we have $V(R_{1}\cup R_{2})\cap
Z=\emptyset$, and so $Z\setminus Z^{\prime}=V(R_{3})$ where $R_{3}$ is
vertical in $\operatorname{sk}(G)$ and $\lambda_{{\mathcal{L}}}(Z\setminus
Z^{\prime})=1$. In this case we also have $|Z^{\prime}|\leq|R|-3\leq h-3$, as
desired. In the Cases (C.2) and (C.3), we similarly have that $Z\setminus
Z^{\prime}$ is made of $2$ and $3$ vertical paths, respectively, and the
bounds on $\lambda_{{\mathcal{L}}}(Z\setminus Z^{\prime})$ follow from that.
In the Case (C.2) we also get
$|Z^{\prime}|\leq\lfloor\frac{1}{2}(|V(R)|-1)\rfloor-1\leq\lfloor\frac{1}{2}(h-1)\rfloor-1$
as desired, since the distance from $t_{3}$ to $V(C)$ on $R$ is not more than
$\frac{1}{2}(|V(R)|-1)$. In the Case (C.3) we have that there are at most
$\frac{1}{3}|V(R)|$ vertices of color $3$ on $R$ (which stay in $Z^{\prime}$
except the end of $R_{3}$), and so
$|Z^{\prime}|\leq\lfloor\frac{1}{3}|V(R)|\rfloor-1\leq\lfloor\frac{h}{3}\rfloor-1$.

We now turn the attention to the quotient graph $H:=H^{\prime}$. Recall that
we have recursively obtained the planar quotient graphs
$H_{j}:=G_{j}/{\mathcal{R}}_{j}$, for $j\in\\{1,\dots,a\\}$, and we may
assume, from the recursive invocation of Property 3, that each $H_{j}$ is a
plane topological graph with the vertices stemming from the parts of
${\mathcal{R}}^{0}_{j}$ on the outer face. We again call these vertices
stemming from ${\mathcal{R}}^{0}_{j}$ the connectors of $H_{j}$, and we have
from Property 5 that no vertices of $H_{j}$ other than the connectors are
adjacent to vertices of $H$ outside of $H_{j}$.

As previously, the graph $H$ consists of a $4$-clique $Q$ on the vertices
which stem from the four parts of ${\mathcal{R}}^{0}\cup\\{Z\\}$, and of the
union of the graphs $H_{j}$, with $j=1,\ldots,a$, after identification of
their connectors with the vertices of $Q$. Let $z$ be the vertex of $Q$ that
stems from the part $Z$ and $w_{1},w_{2},w_{3}$ be the vertices which stem
from the parts $X_{1},X_{2},X_{3}$ of ${\mathcal{R}}^{0}$. As already noted,
none of the graphs $H_{j}$ contains all three $w_{1},w_{2},w_{3}$ (as its
connectors), and for every pair from $\\{w_{1},w_{2},w_{3}\\}$, say $w_{c}$
and $w_{d}$, at most one of $H_{j}$, $j\in\\{1,\ldots,a\\}$, contains both
$w_{c},w_{d}$ among its connectors. In such case, $H_{j}$ is to be embedded in
the triangular face $\\{w_{c},w_{d},z\\}$ of $Q$. Furthermore, if some
$H_{j}$, $j\in\\{1,\ldots,a\\}$, contains only one of $w_{1},w_{2},w_{3}$ as
its connector, say $w_{b}$, then $H_{j}$ can be embedded in any of the two
triangular faces of $Q$ incident to the edge $\\{w_{b},z\\}$.

Altogether, we have obtained a plane drawing of
$H=G_{C}/{\mathcal{R}}^{\prime}$ such that the vertices $w_{1},w_{2},w_{3}$
stemming from the parts of ${\mathcal{R}}^{0}$ are on the same triangular
face. We have thus verified Property 3, and it remains to verify Property 2 in
the aspect of treewidth of $H$. Again, we have recursively obtained a tree-
decomposition ${\mathcal{T}}_{j}$ of $H_{j}$ for every $j\in\\{1,\dots,a\\}$,
such that the clique of the vertices which stem from ${\mathcal{R}}_{j}^{0}$
is contained in a node $\nu_{j}$ of it. We create a new decomposition
${\mathcal{T}}$ of $H$ from the disjoint union of ${\mathcal{T}}_{j}$ over
$j=1,\ldots,a$ by adding a new node $\nu$, holding the bag of vertices $V(Q)$
and adjacent exactly to all $\nu_{j}$. Further, for $i=1,\dots,k$, we rename
each vertex of $\mathcal{T}_{j}$ that stems from $X^{j}_{i}$, with
$i=1,\dots,a$, as the vertex in $Q$ that stems from $X_{i}$ and, for
$i=1,\dots,a$, we rename each vertex of $\mathcal{T}_{j}$ that stems from
$Y_{i}$ as the vertex in $Q$ that stems from $Y$. This is a valid tree-
decomposition by Property 5, and it is of width $3$ by Property 2 and the fact
that $|V(Q)|-1=3$. ∎

We conclude the proof of Lemma 4 by discussing the time complexity of our
algorithm. All the necessary work needed at each recursive call can be easily
implemented to run in $O(|V(G_{C})|)$ time, by adopting the approach of
[DBLP:journals/corr/abs-2004-02530] to compute $R_{1}$, $R_{2}$ and $R_{3}$ in
the general case (provided that $G$ is a topological $h$-framed graph). Since
the total number of recursive calls is at most linear in $|V(G_{C})|$, the
total running time is thus quadratic in $|V(G_{C})|$. ∎

###### Proof of Theorem 2..

Let $C$ denote the cycle bounding the outer face of $\operatorname{sk}(G)$,
which, by a possible homeomorphism of the sphere, may be assumed to satisfy
$|V(C)|\geq 3$. Based on the BFS tree $T$ of $\operatorname{sk}(G)$ rooted in
a vertex $r\in V(C)$, we define the following partition $\mathcal{R}^{0}$ of
$C$: We split $C$ into a path $P_{1}$ only consisting of the vertex $r$, and
two paths $P_{2}$ and $P_{3}$ of lengths at most $\lfloor\frac{h-1}{2}\rfloor$
and $\lfloor\frac{h}{2}\rfloor$, respectively. This defines the initial setup
of our algorithm which allows us to invoke Lemma 4 (e.g., with $q=2$ and using
trivial single-vertex vertical paths in $P_{2}$ and $P_{3}$). Then, we set
$\mathcal{R}^{0}=\\{V(P_{1}),V(P_{2}),V(P_{3})\\}$ and apply the algorithm
given in the proof of Lemma 4. This way we obtain a good partition
${\mathcal{R}}^{\prime}$ of $V(G_{C})=V(G)$ and graph
$H^{\prime}:=G_{C}/{{\mathcal{R}}^{\prime}}$ in $O(|V(G)|^{2})$ time. Note
that, in general, $G_{C}\not=G$ as $G$ may have edges drawn in the outer face
(bounded by $C$) of $\operatorname{sk}(G)$. However, by setting
$H=H^{\prime}$, we guarantee all edges of $G$ in the outerface of
$\operatorname{sk}(G)$ are “captured”, since the quotient graph $H^{\prime}$
anyway contains a triangle on the vertices that stem from ${\mathcal{R}}_{0}$.
In fact, we have just obtained the graph $H$ with the desired properties,
i.e., $H$ is planar and of $\mathrm{tw}(H)\leq 3$.

What remains to prove is that $G$ indeed is a subgraph of the strong product
$H\boxtimes P\boxtimes K_{3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1}$ for some
path $P$. Recall that the number of layers of the layering ${\mathcal{W}}$ is
$\ell+1$, and that ${\mathcal{W}}$ was obtained by merging consecutive
$\lfloor\frac{h}{2}\rfloor$-tuples of layers of ${\mathcal{L}}$. We set $P$ to
be the path on $\ell+1$ vertices denoted in order by
$p_{0},p_{1},\ldots,p_{\ell}$. To a vertex $v\in V(G)$, we assign the pair
$(t,p_{i})$ where $t\in V(H)$ if $t$ stems from the part of
${\mathcal{R}}^{\prime}$ that $v$ belongs to, and $v\in
W_{i}\in{\mathcal{W}}$. This assignment is sound and unique. If
$vv^{\prime}\in E(G)$ is any edge of $G$, and $v$ and $v^{\prime}$ are
assigned the pairs $(t,p_{i})$ and $(t^{\prime},p_{j})$ as above, then
$tt^{\prime}\in E(H)$ or $t=t^{\prime}$ since $H=G/{\mathcal{R}}^{\prime}$ is
the quotient graph, and $p_{i}p_{j}\in E(P)$ or $i=j$ since ${\mathcal{W}}$ is
a layering of $G$. Using Property 1 of Lemma 4, we furthermore estimate, for
every part $X\in\mathcal{R}^{\prime}$ and its $X^{\prime}\subseteq X$ (cf.
Property 1),

$\displaystyle\lambda_{{\mathcal{W}}}(X)$
$\displaystyle\leq|X^{\prime}|+\lambda_{{\mathcal{L}}}(X\setminus
X^{\prime})\cdot\lfloor h/2\rfloor$ $\displaystyle\leq\max\big{(}h-3+\lfloor
h/2\rfloor,\>\lfloor h/2\rfloor-1+2\lfloor h/2\rfloor,\>\lfloor
h/3\rfloor-1+3\lfloor h/2\rfloor\big{)}$ $\displaystyle\leq 3\lfloor
h/2\rfloor+\lfloor h/3\rfloor-1\,,$

and hence at most $3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1$ vertices of $G$
are assigned to the same pair $(t,p_{i})$. This concludes the proof that
$\mathrm{si}(G)\subseteq H\boxtimes P\boxtimes K_{3\lfloor h/2\rfloor+\lfloor
h/3\rfloor-1}$. ∎

We next present a variant of Theorem 2, which reduces the size of the clique
in the product by replacing the path with a power of it.

######  Theorem 8.

Let $G$ be an $h$-framed graph (where $G$ is not necessarily simple). Then
$\mathrm{si}(G)$ is a subgraph of the strong product of three graphs
$H\boxtimes P^{\lfloor h/2\rfloor}\boxtimes K_{max(3,h-2)}$, where $H$ is a
planar graph with $\mathrm{tw}(H)\leq 3$ and $P$ is a path.

###### Proof.

Recall that ${\mathcal{L}}=(V_{0},V_{1},\ldots,V_{b})$ is a BFS layering of
the skeleton $\operatorname{sk}(G)$, and thus every edge of $G$ has ends in
parts $V_{i},V_{j}\in{\mathcal{L}}$ such that $|i-j|\leq\lfloor h/2\rfloor$.
Hence, we may choose $P$ as the path on $b+1$ vertices
$(p_{0},p_{1},\ldots,p_{b})$, use $P^{\lfloor h/2\rfloor}$, and assign each
vertex $v\in V(G)$ to the pair $(t,p_{i})$ where $t\in V(H)$ if $t$ stems from
the part of ${\mathcal{R}}^{\prime}$ that $v$ belongs to, and $v\in
V_{i}\in{\mathcal{L}}$. Now, the number of vertices of $G$ assigned to the
same pair $(t,p_{i})$ (where $t$ stems from a part $X$) is at most
$\lambda_{{\mathcal{L}}}(X)\leq|X^{\prime}|+\lambda_{{\mathcal{L}}}(X\setminus
X^{\prime})\leq\max(h-3+1,\>\lfloor h/2\rfloor-1+2,\>\lfloor
h/3\rfloor-1+3\big{)}=max(3,h-2)$. This concludes that
$\mathrm{si}(G)\subseteq H\boxtimes P^{\lfloor h/2\rfloor}\boxtimes
K_{\max(3,h-2)}$. ∎

##  4 Consequences of the Product Structure

As mentioned in the introduction, Dujmovic et al.
[DBLP:journals/corr/abs-1907-05168] have derived upper bounds on the queue
number, on the non-repetitive chromatic number, and on the $p$-centered
chromatic number of $k$-planar and $k$-map graphs exploiting Theorem 1. In the
following, we present our improvements to each of these problems.

Queue number. A _queue layout_ of a graph $G$ is a linear order $\sigma$ of
the vertices of $G$ together with an assignment of its edges to sets, called
_queues_ , such that no two edges in the same set nest. The _queue number_
$\mathrm{qn}(G)$ of a graph $G$ is the minimum number of queues over all queue
layouts of $G$. In [DBLP:journals/jacm/DujmovicJMMUW20], Dujmović et al. have
proved the following useful lemma concerning the queue number of graphs that
can be expressed as subgraphs of the strong product of a path $P$, a graph $H$
with queue number $\mathrm{qn}(H)$, and a clique $K_{\ell}$ on $\ell$
vertices.

######  Lemma 9 (Dujmovic et al. [DBLP:journals/jacm/DujmovicJMMUW20]).

If $G\subseteq P\boxtimes H\boxtimes K_{\ell}$ then $\mathrm{qn}(G)\leq
3\ell\,\mathrm{qn}(H)+\lfloor\frac{3}{2}\ell\rfloor$.

Combining Lemma 9 and Theorem 1(d), together with the fact that the queue
number of planar $3$-trees is at most $5$
[DBLP:journals/algorithmica/AlamBGKP20], Dujmović, Morin, and Wood showed the
first constant upper bound on the queue number of $k$-planar graphs
[DBLP:journals/corr/abs-1907-05168], thus resolving a long-standing open
question. Analogously, by combining Lemmata 9 and 2, we obtain the following.

######  Theorem 10.

The queue number of $h$-framed graphs is at most

$15\cdot(3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1)+\lfloor\frac{3}{2}(3\lfloor
h/2\rfloor+\lfloor h/3\rfloor-1)\rfloor.$

Dujmovic et al. [DBLP:journals/jacm/DujmovicJMMUW20] first showed the queue
number of $k$-map graphs is at most $2(98(k+1))^{3}$. Later, by combining
Theorem 1(e) and Lemma 9, Dujmovic et al. [DBLP:journals/corr/abs-1907-05168]
improved this bound to $32225k(k-3)$. By Theorem 10, we improve these bounds
to $61k$ by exploiting the fact that these graphs are subgraphs of $2k$-framed
graphs [DBLP:journals/corr/abs-2003-07655, DBLP:conf/compgeom/BekosLGGMR20].

######  Corollary 11.

The queue number of $k$-map graphs is at most

$15\cdot(3k+\lfloor 2k/3\rfloor-1)+\lfloor\frac{3}{2}(3k+\lfloor
2k/3\rfloor-1)\rfloor.$

For $h\in{4,5}$, Theorem 10 gives us an upper bound of $95$. Since any
$1$-planar graph can be augmented to a (not-necessarily simple) $4$-framed
graph [DBLP:conf/gd/AlamBK13], Theorem 10 improves the current best upper
bound of $1$-planar graphs from $495$ to $95$. Since any optimal $2$-planar
graph is $5$-framed, Theorem 10 improves the current best upper bound on their
queue number from $3267$ (derived from Lemma 9 with $\ell=198$) to $95$. Next,
we show a generalization of Lemma 9 that allows further improvements.

######  Lemma 12.

lemma If $G\subseteq H\boxtimes P^{i}\boxtimes K_{\ell}$ then
$\mathrm{qn}(G)\leq
i\ell+(2i+1)\ell\mathrm{qn}(H)+\lfloor\frac{\ell}{2}\rfloor$.

###### Proof.

For convenience, let ${\cal X}_{j}=H\boxtimes P^{j}\boxtimes K_{\ell}$, with
$1\leq j\leq i$. Observe that the graphs ${\cal X}_{j}$, with $1\leq j\leq i$,
have the same vertex set and ${\cal X}_{j}\subseteq{\cal X}_{j+1}$, with
$1\leq j<i$. Let $P=(p_{1},p_{2},\dots,p_{z})$ and let $\langle
x_{1},x_{2},\dots,x_{q}\rangle$ be the vertex ordering of a
$\mathrm{qn}(H)$-queue layout of $H$. We set $V_{a,b}:=\\{v_{a,b}\\}\times
V(K_{\ell})$, where $v_{a,b}$ denotes the vertex of $V(H)\times V(P)$ that
stems from the vertex $x_{a}$ of $H$ and the vertex $p_{b}$ of $P$. Note that,
the sets $V_{a,b}$ form a partition of $V({\cal X}_{1})$. The following
property follows from the proof of Lemma 9 given in
[DBLP:journals/jacm/DujmovicJMMUW20].

######  Property 13 (Vertex order of Lemma 9).

The queue layout of ${\cal X}_{1}$ in the proof of Lemma 9 is such that, for
any two vertices $u\in V_{a,b}$ and $v\in V_{c,d}$, it holds that $u$ precedes
$v$ in such a layout if and only if one of the following holds: Either $b<d$
or $c=d$ and $a<c$.

Our proof is by induction on $i$. In particular, we will show that ${\cal
X}_{i}$ has a queue layout whose vertex order $\sigma$ satisfies Property 13
and uses at most $i\ell+(2i+1)\ell\mathrm{qn}(H)+\lfloor\frac{\ell}{2}\rfloor$
queues. In the base case $i=1$ and the result follows directly from Lemma 9.
Assume now that $i>1$. Let $\Delta_{i}$ be the graph obtained by removing from
$P^{i}$ the edges that it shares with $P^{i-1}$, i.e.,
$\Delta_{i}=(V(P),E(P^{i})\setminus E(P^{i-1}))$. Clearly, two vertices are
adjacent in $\Delta_{i}$ if and only if they are at distance $i$ in $P$.
Observe now that ${\cal X}_{i}$ is the union of ${\cal X}_{i-1}$ and
$H\boxtimes\Delta_{i}\boxtimes K_{\ell}$. By induction, we have that ${\cal
X}_{i-1}$ admits a queue layout $\Gamma$ whose vertex order satisfies Property
13 and uses at most
$(i-1)\ell+(2i-1)\ell\mathrm{qn}(H)+\lfloor\frac{\ell}{2}\rfloor$ queues.
Therefore, in order to prove the statement, it suffices to show that the edges
of $H\boxtimes\Delta_{i}\boxtimes K_{\ell}$ can be added in $\Gamma$ by using
at most $\ell+2\mathrm{qn}(H)\ell$ queues. To this aim, we classify the edges
of this graph into three sets $E_{|}$, $E_{\textbackslash}$, and $E_{/}$.
Namely, for each edge $(u,v)$ with $u\in V_{a,b}$ and $v\in V_{c,d}$, we have
that:

  * •

$(u,v)\in E_{|}$, if $b=d$;

  * •

$(u,v)\in E_{\textbackslash}$, if $b<d$ and $a<c$; and

  * •

$(u,v)\in E_{/}$, if $b<d$ and $a>c$.

First, we show that the edges in $E_{|}$ can be assigned to at most $\ell$
queues. For this, we recall that the number of queues in a queue layout
coincides with the size of its largest rainbow
[DBLP:journals/siamcomp/HeathR92], where a _rainbow_ is a set of pairwise-
nesting independent edges in a linear order of the vertices. Namely, let
$(u,v)$ and $(u^{\prime},v^{\prime})$ be two edges in $E_{|}$ with $u\in
V_{a_{1},b}$, $v\in V_{a_{2},b}$, $u^{\prime}\in
V_{a_{1}^{\prime},b^{\prime}}$ and $v^{\prime}\in
V_{a_{2}^{\prime},b^{\prime}}$. Assuming w.l.o.g. that $a_{1}\leq
a_{1}^{\prime}$ holds, it follows that these two edges nest in $\sigma$, only
if $b=b^{\prime}$, $a_{1}=a_{1}^{\prime}$, and $a_{2}=a_{2}^{\prime}$. Since
each of the sets $V_{a_{1},b}$ and $V_{a_{2},b}$ contains at most $\ell$
vertices and since the vertices in $V_{a_{1},b}$ precede the vertices of
$V_{a_{2},b}$ in $\sigma$, we have that the maximum rainbow formed by edges in
$E_{|}$ has size at most $\ell$ in $\sigma$. Thus, $\ell$ queues suffice to
embed all such edges in $\Gamma$ [DBLP:journals/siamcomp/HeathR92]. Second, we
that all the edges in $E_{\textbackslash}$ can be assigned to at most
$\ell\mathrm{qn}(H)$ queues. Since the proof that the edges in $E_{/}$ can be
assigned to at most $\ell\mathrm{qn}(H)$ queues is analogous, this concludes
the proof of the lemma. Consider a partition of $E_{\textbackslash}$ into sets
$E_{i}$, with $1\leq i\leq\mathrm{qn}(H)$, such that $E_{i}$ contains all the
edges $(u,v)$ of $E_{\textbackslash}$ such $u\in V_{a,c}$, $v\in V_{c,d}$, and
$(a,c)$ belong to the $i$-th queue of $H$. Next, we show that the edges in
each set $E_{i}$ can be assigned to at most $\ell$ new queues in $\Gamma$.
Consider any two nesting edges $(u,v)$ and $(u^{\prime},v^{\prime})$ in
$E_{i}$ with $u\in V_{a_{1},b_{1}}$, $v\in V_{a_{2},b_{2}}$, $u^{\prime}\in
V_{a_{1}^{\prime},b_{1}^{\prime}}$ and $v^{\prime}\in
V_{a_{2}^{\prime},b_{2}^{\prime}}$. By the definition of $E_{\textbackslash}$,
we have that $a_{1}<a_{2}$, $a_{1}^{\prime}<a_{2}^{\prime}$, $b_{1}<b_{2}$,
and $b_{1}^{\prime}<b_{2}^{\prime}$. Since $(u,v),(u^{\prime},v^{\prime})\in
E(\Delta_{i})$ they have the same span and thus it follows that $(u,v)$ and
$(u^{\prime},v^{\prime})$ nest in $\sigma$ only if (i) $b_{1}=b_{1}^{\prime}$
and $b_{2}=b_{2}^{\prime}$ (that is, $u$ and $u^{\prime}$ (resp. $v$ and
$v^{\prime}$) stem from the same vertex of $\Delta_{i}$) and (ii)
$a_{1}=a_{1}^{\prime}$ or $a_{2}=a_{2}^{\prime}$ (that is, at least one of the
pairs $u,u^{\prime}$ and $v,v^{\prime}$ stem from the same vertex of $H$)
[DBLP:journals/jacm/DujmovicJMMUW20]. Since each of the sets $V_{a_{1},b_{1}}$
and $V_{a_{2},b_{2}}$ contains at most $\ell$ vertices and since the vertices
in $V_{a_{1},b_{1}}$ precede the vertices of $V_{a_{2},b_{2}}$ in $\sigma$, we
have that the maximum rainbow formed by edges in $E_{i}$ has size at most
$\ell$ in $\sigma$. Thus, $\ell$ queues suffice to embed all such edges in
$\Gamma$ [DBLP:journals/siamcomp/HeathR92], and the proof is concluded. ∎

Lemma 12 in conjunction with Theorem 8 yields a quadratic (in $h$) upper bound
on the queue number of $h$-framed graphs. However, for $h\leq 5$, it implies
an improved bound on the queue number of $1$-planar and optimal $2$-planar
graph, which we summarize in the following.

######  Theorem 14.

The queue number of $1$-planar and optimal $2$-planar graphs is at most $81$.

Non-repetitive chromatic number. An _$r$ -coloring_ of a graph $G$ is a
function $\phi:$V(G)$\rightarrow[r]$. A path $p=(v_{1},v_{2},\dots,v_{2\tau})$
is _repetitively colored_ by $\phi$ if $\phi(v_{i})=\phi(v_{i+\tau})$ for
$i=1,2,\dots,\tau$. A coloring $\phi$ of $G$ is _non-repetitive_ if no path of
$G$ is repetitively colored by $\phi$. Clearly, non-repetitive colorings are
_proper_ , i.e., $\phi(u)\neq\phi(v)$ if $u$ and $v$ are adjacent in $G$. The
_non-repetitive chromatic number_ $\pi(G)$ of $G$ is the minimum integer $r$
such that $G$ admits a non-repetitive $r$-coloring. In [2020-non-repetitive],
Dujmovic et al. developed the following lemma to upper-bound the non-
repetitive chromatic number of graphs that can be expressed as subgraphs of
the strong product of a path $P$, a graph $H$ with $\mathrm{tw}(H)$, and a
clique $K_{\ell}$ on $\ell$ vertices.

######  Lemma 15 (Dujmovic et al. [2020-non-repetitive]).

If $G\subseteq P\boxtimes H\boxtimes K_{\ell}$, then $\pi(G)\leq
4^{tw(H)+1}\cdot\ell$.

Using Lemma 15 and Theorem 1(c), Dujmovic et al.
[DBLP:journals/corr/abs-1907-05168] provide an upper bound of $7680$ on the
non-repetitive chromatic number of $1$-planar graphs. Since $1$-planar graphs
are $4$-framed, we improve this bound to $1536$. Using the fact that
$h$-framed graphs are $O(h^{2})$-planar and the bound derived by combining
Lemma 15 and Theorem 1(e), we may conclude that their non-repetitive chromatic
number is bounded (but the bound is super-polynomial in $h$). By Lemma 15 and
Theorem 2, we obtain an upper bound for $h$-framed graphs that is linear in
$h$. Also, since $k$-map graphs are subgraphs of $2k$-framed graphs
[DBLP:journals/corr/abs-2003-07655, DBLP:conf/compgeom/BekosLGGMR20], their
non-repetitive chromatic number is linear in $k$; this is an improvement over
the quadratic bound given in [DBLP:journals/corr/abs-1907-05168].
Specifically, we get the following.

######  Corollary 16.

For a graph $G$, it holds:

  1. (i)

$\pi(G)\leq 4^{4}\cdot 6$, if $G$ is $1$-planar,

  2. (ii)

$\pi(G)\leq 4^{4}\cdot(3k+\lfloor 2k/3\rfloor-1)$, if $G$ is $k$-map, and

  3. (iii)

$\pi(G)\leq 4^{4}\cdot(3\lfloor h/2\rfloor+\lfloor h/3\rfloor-1)$, if $G$ is
$h$-framed.

$p$-centered chromatic number. For any $c,p\in\mathbb{N}$ with $c\geq p$, a
$c$-coloring of a graph $G$ is _$p$ -centered_ if, for every connected
component $X$ of $G$, at least one of the following holds: (i) the vertices of
$X$ are colored with more than $p$ colors, or (ii) there exists a vertex $v$
of $X$ that is assigned a color different from the ones of the remaining
vertices of $X$. For any graph $G$, the _$p$ -centered chromatic number_
$\chi_{p}(G)$ of $G$ is the minimum integer $c$ such that $G$ admits a
$p$-centered $c$-coloring. Pilipczuk and Siebertz showed that
$\chi_{p}(H)\leq\binom{p-t}{t}$ for any graph $H$ of treewidth $t$
[DBLP:journals/jctb/PilipczukS21]. However, for the special case in which $H$
is planar and has treewidth at most $3$, Debski et al.
[DBLP:conf/soda/DebskiFMS20] showed that $\chi_{p}(H)\in O(p^{2}\log p)$.
Also, Debski et al. [DBLP:conf/soda/DebskiFMS20] and Dujmovic et al.
[DBLP:journals/corr/abs-1907-05168] showed that for any subgraph $G$ of
$H\boxtimes P\boxtimes K_{\ell}$ it holds
$\chi_{p}(G)\leq\ell(p+1)\chi_{p}(H)$. For convenience, hereafter we combine
these results to upper-bound the $p$-centered chromatic number of graphs that
can be expressed as subgraphs of the strong product of a path $P$, a graph $H$
with treewidth $\mathrm{tw}(H)$, and a clique $K_{\ell}$ on $\ell$ vertices.

######  Lemma 17 ([DBLP:conf/soda/DebskiFMS20,
DBLP:journals/corr/abs-1907-05168, DBLP:journals/jctb/PilipczukS21]).

If $G\subseteq P\boxtimes H\boxtimes K_{\ell}$, where $\mathrm{tw}(H)\leq 3$,
it holds:

  1. (i)

$\chi_{p}(G)\in O(\ell p^{3}\log p)$, if $H$ is planar, and

  2. (ii)

$\chi_{p}(G)\in O(\ell p^{4})$, if $H$ is not planar.

By Lemma 17.ii and Theorem 1, Dujmovic et al.
[DBLP:journals/corr/abs-1907-05168] showed that $\chi_{p}(G)\in O(p^{4})$ if
$G$ is a $1$-planar graph, $\chi_{p}(G)\in O(k^{2}p(p+k^{3})^{k^{3}})$ if $G$
is a $k$-planar graph, and $\chi_{p}(G)\in O(k^{2}p^{10})$ if $G$ is a $k$-map
graph. Since $h$-framed graphs are $O(h^{2})$-planar, their $p$-centered
chromatic number is $O(h^{4}p(p+h^{6})^{h^{6}})$. By exploiting Theorem 2 and
Lemma 17.i, we get the next.

######  Corollary 18.

For a graph $G$, it holds:

  1. (i)

$\chi_{p}(G)\in O(p^{3}\log p)$, if $G$ is $1$-planar,

  2. (ii)

$\chi_{p}(G)\in O(kp^{3}\log p)$, if $G$ is $k$-map, and

  3. (iii)

$\chi_{p}(G)\in O(hp^{3}\log p)$, if $G$ is $h$-framed.

##  5 Bounding Twin-width

Besides the direct consequences of the product structure theorem(s) surveyed
in Section 4, the construction presented in Section 3 has another strong
implication described next.

Consider only simple graphs for the coming definition.555In 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 neighbors_ and _red degree_ in $G$. We denote the
set of red neighbors of a vertex $v$ by $N_{r}(v)$. 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}$ whose full neighborhood is the union of neighborhoods of $x_{1}$ and
$x_{2}$ in $G$, that is, $N(x_{0})=(N(x_{1})\cup
N(x_{2}))\setminus\\{x_{1},x_{2}\\}$, and the red neighbors $N_{r}(x_{0})$ of
$x_{0}$ inherit all red neighbors of $x_{1}$ and of $x_{2}$ and those in
$N(x_{1})\oplus N(x_{2})$, that is, $N_{r}(x_{0})=\big{(}(N_{r}(x_{1})\cup
N_{r}(x_{2}))\setminus\\{x_{1},x_{2}\\}\big{)}\cup\big{(}N(x_{1})\oplus
N(x_{2})\big{)}$, where $\oplus$ 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_ is
the minimum width over all possible contraction sequences (where for an
ordinary graph, we start with the same trigraph having no red edges). As noted
already in the pioneering paper on this concept
[DBLP:journals/jacm/BonnetKTW22], the twin-width of $k$-planar graphs is
bounded for any fixed $k$ by means of FO transductions (which, therefore,
gives a not-even-asymptotically expressible bound). Explicit asymptotic bounds
for the twin-width of $k$-planar graphs (albeit with $O(k)$ in the exponent,
and so not giving an explicit number for e.g. $k=1$) are in
[DBLP:journals/corr/abs-2202-11858] (with a generalization to higher
surfaces), and specially for planar graphs, the current upper bounds on twin-
width are $583$ in [DBLP:journals/corr/abs-2202-11858] and improved $183$ in
[DBLP:journals/corr/abs-2201-09749]. It is worth to mention that both
[DBLP:journals/corr/abs-2202-11858, DBLP:journals/corr/abs-2201-09749], more
or less explicitly, use the product structure machinery of planar graphs. We
give an improved bound on the twin-width of planar graphs, and new explicit
(non-asymptotic) bounds on the twin-width of $h$-framed and $1$-planar graphs.

######  Theorem 19.

The twin-width of a simple planar graph $G$ is at most $37$.

###### Proof.

We use the refined planar product structure machinery from
[DBLP:journals/corr/abs-2108-00198]. In fact, the outer skeleton of our proof
is the same as in [DBLP:journals/corr/abs-2201-09749, Section 4], but we use a
different invariant “inside”. As in Section 3, we start with a technical setup
(now simplified).

Let $G$ be a simple planar graph, and let $G^{+}\supseteq G$ be an arbitrary
plane triangulation on the same vertex set $V(G^{+})=V(G)$. Let $S$ be the
cycle of the outer face of $G^{+}$ (so, $S$ is a triangle) and $t\in V(S)$.
Consider a BFS tree $T$ of $G^{+}$ (not of $G$) rooted in $t$ and the BFS
layering ${\mathcal{L}}=(V_{0},V_{1},\ldots)$ of $G^{+}$ such that $V_{i}$
contains all vertices of $G^{+}$ at distance $i$ from $t$. 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 _${\mathcal{L}}$ -respecting_ if every step
contracts only pairs belonging to $V_{j}$ for some $j$. To be formally
precise, when $G^{\prime}$ is a trigraph resulting from an
${\mathcal{L}}$-respecting partial contraction sequence of $G$, we should
write $V_{j}[G^{\prime}]$ for the set that stems from $V_{j}=V_{j}[G]$. The
following is immediate and useful to notice:

######  Claim 20.

Let $G^{\prime}$ be a trigraph obtained from $G$ by an
${\mathcal{L}}$-respecting partial contraction sequence. If there is a red
edge in $G^{\prime}$ from $V_{j}[G^{\prime}]$ to $V_{j^{\prime}}[G^{\prime}]$,
then $|j-j^{\prime}|\leq 1$.

The _$G$ -neighborhood of a vertex $x$ in a set $Y$_ is the subset
$Y^{\prime}\subseteq Y$ of those vertices adjacent to $x$ in $G$. Theorem 19
will follow if we (recursively) prove the following:

######  Claim 21.

Let $C$ be a cycle in $G^{+}$, and let $G_{C}$ be the subgraph of $G$ formed
by the vertices and edges along and in the interior of $C$ (i.e., $G_{C}$ is
the subgraph of $G$ bounded by $C$), such that $U:=V(G_{C})\setminus V(C)$
does not contain $t$. Let $a,b\in V(C)$ be arbitrary. Assume that, for some
$1\leq k\leq 5$, the vertex set $V(C)$ is partitioned into $k$ pairwise
disjoint vertical paths $P_{1},\ldots,P_{k}\subseteq C$. Then there exists an
${\mathcal{L}}$-respecting partial contraction sequence of $G$ which contracts
only vertex pairs in $U$, results in a trigraph $G_{0}$, and satisfies the
following:

  1. a)

Each vertex of $V(C)$ has red degree at most $12$ along the sequence, and no
red edge is incident to either of $a,b$;

  2. b)

each vertex that stems from $U$ along the sequence has red degree at most
$37$; and

  3. c)

no two vertices of $V_{j}^{0}:=(V(G_{0})\setminus V(C))\cap V_{j}[G_{0}]$, for
$j=1,2,\ldots$, have the same $G_{0}$-neighborhood in $\\{a,b\\}$. So, in
particular, $|V_{j}^{0}|\leq 4$.

Indeed, we can apply Claim 21 to the outer triangle $S$, obtaining the
trigraph $G_{0}$ along an ${\mathcal{L}}$-respecting sequence, and then
successively (in an arbitrary choice and order of vertex pairs) contract
$V_{0}=\\{t\\}$ with $V_{1}[G_{0}]$ into one vertex, then with $V_{2}[G_{0}]$
into one vertex, with $V_{3}[G_{0}]$, and so on. By Claim 20, we have that
only three layers of ${\mathcal{L}}$ contribute to the maximum red degree,
which is thus at most $(4+2)+4+4-1=13<37$ ($+2$ stands for the two vertices of
$V_{1}$ in $S$) in this remaining contraction sequence of $G_{0}$.

The rest of the proof is devoted to proving Claim 21 by induction on $|U|$. If
$U=\emptyset$, then we are done with the empty contraction sequence and
$G_{0}=G$. Otherwise, we start with a few more basic observations. Since we
are contracting only vertex pairs in $U$, every red edge of $G_{0}$ must have
one or both ends in $U$ (precisely, in a vertex that stems from $U$, but we
slightly abuse the notation to keep it simple). Furthermore, if a red edge of
$G_{0}$ starts in a vertex $w\not\in U$, then $w$ must have been adjacent to
some vertex of $U$ in $G$. Together with the assumed planarity of
$G^{+}\supseteq G$ and its cycle $C$ bounding $U$ in the interior, this
implies that there is no red edge in $G_{0}$ incident to a vertex of
$V(G)\setminus V(G_{C})$, i.e., no red edge “crosses” the cycle $C$ in
$G_{0}$. Although, note that $G_{0}$ is not necessarily planar (in the
interior of $C$).

We use the decomposition argument of [DBLP:journals/corr/abs-2108-00198]
(exactly as [DBLP:journals/corr/abs-2201-09749, Section 4] does). In this
argument, we get a triangle $R_{0}$ of $G^{+}$, and three pairwise disjoint
vertical paths $R_{1},R_{2},R_{3}\subseteq G^{+}$ (possibly degenerate) from
the three vertices of $R_{0}$ to $V(C)$, such that the plane graph $C\cup R$,
where $R:=R_{0}\cup R_{1}\cup R_{2}\cup R_{3}$, has at most three inner faces
(other than $R_{0}$) bounded by the cycles $D_{1},D_{2},D_{3}\subseteq C\cup
R$, and each of $D_{1},D_{2},D_{3}$ intersects at most three of the paths
$P_{1},\ldots,P_{k}$ (and two of $R_{1},R_{2},R_{3}$). Let $G_{D_{i}}$,
$i\in\\{1,2,3\\}$, be the subgraph of $G$ bounded by $D_{i}$. For $i=1,2,3$,
let $r_{i}$ be the end of $R_{i}$ on $C$, and, up to symmetry, assume that
$R_{i}$ is the path disjoint from (“opposite to”) $D_{i}$.

We are going to apply Claim 21 independently to each of $D_{1},D_{2},D_{3}$
with a suitable choice of the two vertices $a,b$ as follows. If the given
$a,b$ belong to the same cycle, say $a,b\in D_{1}$ up to symmetry, then we
choose $a_{1}:=a$, $b_{1}:=b$, $a_{2}:=r_{1}$, $b_{2}:=r_{3}$ and
$a_{3}:=r_{1}$, $b_{3}:=r_{2}$. Otherwise, if, up to symmetry, $a\in D_{2}$
and $b\in D_{3}$, then we choose $a_{2}:=a$, $b_{2}:=r_{1}$, $a_{3}:=r_{1}$,
$b_{3}:=b$ and $a_{1}:=r_{2}$, $b_{1}:=r_{3}$. So, for $i=1,2,3$, we apply
Claim 21 to $D_{i}$ in place of $C$ and to $a_{i},b_{i}$ as previously. This
way we get partial contraction sequences of $G$ down to $G_{i}$. We denote
(cf. Property (c)) by $V_{j}^{i}:=(V(G_{i})\setminus V(D_{i}))\cap
V_{j}[G_{i}]$ the contracted layers in the interior of $D_{i}$. We compose
these three partial sequences one after another (as there is no conflict or
dependence between them), giving us a partial contraction sequence of $G$ to a
trigraph $G_{4}$.

Observe that along the composed sequence from $G$ to $G_{4}$, only vertices of
$V(R)$ could have received red edges from distinct applications of Claim 21 in
the previous paragraph, and these possible duplicities will be managed in our
coming arguments. Specially, every vertex of $V(C)$ has again red degree at
most $12$ – this also holds for the vertices $r_{1},r_{2},r_{3}$ thanks to our
right choice of $a_{i},b_{i}$ (which essentially “prevents”
$r_{1},r_{2},r_{3}$ from getting more red edges from concurrent recursive
calls). Every vertex of $V(R)$ has red degree at most $2\cdot 12=24<37$ along
the sequence, and every other vertex in the interior of $C$ at most $37$,
which is direct from Claim 21. One can say even more; since every vertex of
$V(D_{i})$ is adjacent to at most three of the layers
$V_{j-1}^{i},V_{j}^{i},V_{j+1}^{i}$ for some $j$ (it is a BFS layering of
$G^{+}\supseteq G$) and $|V_{j-1}^{i}|+|V_{j}^{i}|+|V_{j+1}^{i}|\leq 3\cdot
4=12$, we may as well assume (the “worst case” scenario) that all edges from
$V(D_{i})$ to the rest of $G_{D_{i}}$ are red, except for the edges of $a_{i}$
and $b_{i}$. Furthermore, recall that the (up to eight) paths in
${\mathcal{P}}:=\\{P_{1},\ldots,P_{k},\,R_{1},R_{2},R_{3}\\}$ of $G^{+}$ are
vertical, and hence each of them intersects every BFS layer $V_{j}[G_{4}]$ in
at most one vertex.

Subsequently, we will continue with a partial contraction sequence from
$G_{4}$ to the desired outcome $G_{0}$, in order to finish our claim. This
sequence will proceed in two stages, the first one contracting $V(R_{1})$ and
the interior vertices of $D_{2}$ and $D_{3}$ together (taking advantage of the
fact the $r_{1}$ has no red edge in $G_{4}$), and then the second stage
contracting the rest with $V(R_{2})\cup V(R_{3})$ and the interior vertices of
$D_{1}$. Precisely, if $a,b\in D_{1}$ (cf. the above case distinction), we do:

  1. 1.

In the first stage, we proceed layer-by-layer with $j=1,2,3,\ldots$. We first
contract possible pairs of vertices in $V_{j}^{2}$ with the same adjacency
relation to $b_{2}=r_{3}$; this adds up to $2$ red edges incident to
$a_{2}=r_{1}$ and none to $b_{2}$ (and recall that all other edges to
$V(D_{i})$ are already assumed red). Likewise, we contract possible pairs of
vertices in $V_{j}^{3}$ with the same adjacency relation to $b_{3}=r_{2}$,
again adding at most $2$ red edges to $b_{2}=r_{1}$.

Then we have at most $2$ vertices in each of $V_{j}^{2}$ and $V_{j}^{3}$ left,
plus one vertex in $V_{j}\cap V(R_{1})$, and we contract the remaining pairs
among them of the same $G_{4}$-neighborhood to $\\{r_{2},r_{3}\\}$.

Let $D^{\prime}$ denote the sub-cycle of $C\cup R_{2}\cup R_{3}$ bounding
$G_{D_{2}}\cup G_{D_{3}}$. The red degrees on $D^{\prime}$ do not increase in
the described contractions, except that $r_{1}$ receives up to $4$ red edges
from each of three layers possibly adjacent to $r_{1}$, and this gives the red
degree of at most $0+3\cdot 4=12$ for $r_{1}$, which is good. It is more
delicate to bound the red degrees of the interior vertices of $D^{\prime}$
along our partial sequence (in this first stage):

     * •

When processing layer $j$, there are at most $4$ vertices in layer $j-1$ in
the interior of $D^{\prime}$, and at most $7$ in layer $j-1$ on $D^{\prime}$
(one from every vertical path in ${\mathcal{P}}\setminus\\{R_{1}\\}$).

     * •

In the current layer $j$, before the first contraction there, every interior
vertex has at most $4-1=3$ potential red neighbors of the same layer $j$ in
the interior of $D^{\prime}$. Again, there are at most $7$ additional
potential red neighbors in layer $j$ on $D^{\prime}$. The number of potential
interior red neighbors may increase only after the initial contractions inside
$V_{j}^{2}$ and $V_{j}^{3}$ happen, and at that moment we contract down to at
most $4$ vertices in layer $j$ which means at most $3$ red neighbors there,
too.

     * •

In layer $j+1$ we have up to $(2\cdot 4+1)+7=16$ (including on $D^{\prime}$)
potential red neighbors, which altogether bounds the red degree in layer $j$
along the partial sequence to at most $(4+7)+(3+7)+16=37$. Note that this
number of potential red neighbors does not increase when processing layers
higher than $j$.

Let $G_{5}$ be the resulting trigraph of this stage.

  2. 2.

In the second stage, we again proceed by layers $j=1,2,3,\ldots$. We now, in
$G_{5}$, directly contract (in any order) the pairs of vertices of layer $j$
from $V_{j}^{1}$, from $V(R_{2}\cup R_{3})\cap V_{j}$ and from already
contracted $V_{j}^{2}\cup V_{j}^{3}$, which have the same $G_{5}$-neighborhood
in $\\{a,b\\}$. The red degrees on $C$ do not increase any more (i.e., they
stay at $\leq 12$) and $a,b$ do not get any red edge. As for the red degrees
of the interior vertices, we analyse the situation similarly to the previous
point:

     * •

When processing layer $j$, there are at most $4$ vertices in layer $j-1$ in
the interior of $C$, and at most $5$ in layer $j-1$ on $C$ (one from every
vertical path $P_{1},\ldots,P_{k}$).

     * •

In the layers $j$ and $j+1$, we start with at most $(2\cdot 4+2)+5=15$
(including on $C$) vertices which are potential red neighbors, but in layer
$j$ we are just contracting a pair which gives at most $15-1-1=13$ potential
neighbors to a vertex of layer $j$.

     * •

Altogether, we can bound the red degree in layer $j$ along this partial
sequence to at most $(4+5)+(15-2)+15=37$.

We are left with the second case of $a\in D_{2}$ and $b\in D_{3}$, which is
analysed quite similarly to the previous case of $a,b\in D_{1}$, and so we
only sketch the arguments:

  1. 1.

In the first stage, we again proceed layer-by-layer with $j=1,2,3,\ldots$, and
again first contract inside $V_{j}^{2}$ and $V_{j}^{3}$, and then together
with $V(R_{1})\cap V_{j}$, according to the same $G_{4}$-neighborhood in
$\\{a_{2}=a,\>b_{3}=b\\}$. This way $r_{1}$ gets up to $4$ red edges from the
layer $j$, and no other vertex on $D^{\prime}$ gets new red edges.

For the vertices in the interior of $D^{\prime}$, when processing layer $j$,
we again have at most $4+7=11$ potential red neighbors in layer $j-1$, and
initially at most $3+7=10$ such in layer $j$. And again, when we start
contracting vertices across $V_{j}^{2}$ and $V_{j}^{3}$, and with
$V(R_{1})\cap V_{j}$, we have at most $3+7=10$ potential red neighbors in
layer $j$. Together with up to $16$ potential red neighbors in layer $j+1$
(including on $D^{\prime}$), we get red degree $\leq 11+10+16=37$.

  2. 2.

In the second stage, we again proceed by layers $j=1,2,3,\ldots$, and directly
contract current layer $j$ in the interior of $C$ according to the same
$G_{5}$-neighborhood in $\\{a,b\\}$. No new red edge is added to the vertices
on $C$, and $a,b$ stay without any red edge. The count for potential red
neighbors in layers $j-1$, $j$ and $j+1$ again gives the same numbers for the
red degree of vertices in the interior of $C$, namely at most $9+13+15=37$.

We are done with Claim 21, and hence with the proof of the whole theorem. ∎

The fact that, unlike [DBLP:journals/corr/abs-2201-09749], we do not exploit
the planarity of $G$ to obtain the contraction sequence, allows us to get the
following extension of Theorem 19, by adopting into the previous proof the
decomposition technique of Lemma 4 in place of the one of
[DBLP:journals/corr/abs-2108-00198].

######  Theorem 22.

Let $G$ be a simple spanning subgraph of an $h$-framed graph with $h\geq 4$.
Then the twin-width of $G$ is at most $33\lfloor h/2\rfloor+\lfloor
h/3\rfloor+13\leq 17h+13$.

###### Proof.

We follow the main ideas of the proof of Theorem 19, and adapt them to the
recursive decomposition from Lemma 4. Let $G^{+}\supseteq G$ be an $h$-framed
(topological) graph on the same vertex set. As in the proof of Theorem 2, we
fix the outer face of $\operatorname{sk}(G^{+})$ bounded by a cycle $S$, such
that $3\leq|V(S)|\leq h$, and choose $t\in V(S)$. We initially partition the
vertex set of $S$ into three disjoint paths; the path $S_{1}$ only consisting
of the vertex $t$, and two paths $S_{2}$ and $S_{3}$ of lengths at most
$\lfloor\frac{h-1}{2}\rfloor$ and $\lfloor\frac{h}{2}\rfloor$ covering the
rest of $S$. We consider the BFS layering ${\mathcal{L}}=(V_{0},V_{1},\ldots)$
of $\operatorname{sk}(G^{+})$ (where $V_{i}$ contains all vertices at distance
$i$ from $t$). We will use the following special property of paths of
$\operatorname{sk}(G^{+})$ (with respect to fixed ${\mathcal{L}}$):

  1. (V)

A path $P\subseteq\operatorname{sk}(G^{+})$ is _near-vertical_ if, for any
$j\geq 0$, the union $V_{j}\cup V_{j+1}\cup\ldots\cup V_{j+2\lfloor
h/2\rfloor}$ of $2\lfloor h/2\rfloor+1$ consecutive layers of ${\mathcal{L}}$
intersects $V(P)$ in at most $5\lfloor h/2\rfloor+1$ vertices.

Note that each of the paths $S_{1},S_{2},S_{3}$ decomposing $S$ trivially
satisfies Property (V). We have the following natural analogy of Property 3
for an $h$-framed graph $G^{+}$ which also extends to $G$ since every edge of
$G$ has its ends at distance $\leq\lfloor h/2\rfloor$ in
$\operatorname{sk}(G^{+})$:

######  Claim 23.

Let $G^{\prime}$ be a trigraph obtained from $G$ by an
${\mathcal{L}}$-respecting partial contraction sequence. If there is an edge
(in particular, a red edge) in $G^{\prime}$ from $V_{j}[G^{\prime}]$ to
$V_{j^{\prime}}[G^{\prime}]$, then $|j-j^{\prime}|\leq\lfloor h/2\rfloor$.
Consequently, a vertex of $G^{\prime}$ may have its red neighbors in at most
$2\lfloor h/2\rfloor+1\leq h+1$ layers of ${\mathcal{L}}$ (including its own
layer).

The core of our proof is the following recursive claim:

######  Claim 24.

Let $C$ be a cycle in $\operatorname{sk}(G^{+})$ such that $t$ is not in the
interior of $C$, let $G^{+}_{C}$ be the subgraph of $G^{+}$ bounded by $C$,
and $G_{C}:=G^{+}_{C}\cap G$. Let $a,b\in V(C)$ be arbitrary. Let
$U:=V(G_{C})\setminus V(C)$. Assume that, for some $1\leq k\leq 3$, the vertex
set $V(C)$ is partitioned into $k$ pairwise disjoint near-vertical paths
$P_{1},\ldots,P_{k}\subseteq C$ (Property (V)). Then there exists an
${\mathcal{L}}$-respecting partial contraction sequence of $G$ which contracts
only vertex pairs in $U$, results in a trigraph $G_{0}$, and satisfies the
following:

  1. a)

The red degree of each vertex of $V(C)$ is at most $8\lfloor h/2\rfloor+8$
along the sequence and at most $8\lfloor h/2\rfloor+4$ in final $G_{0}$, and
no red edge (ever) is incident to either of $a,b$;

  2. b)

the red degree of vertices stemming from $U$ along the sequence is at most
$33\lfloor h/2\rfloor+\lfloor h/3\rfloor+13$; and

  3. c)

no two vertices of $V_{j}^{0}:=(V(G_{0})\setminus V(C))\cap V_{j}[G_{0}]$, for
$j=1,2,\ldots$, have the same $G_{0}$-neighborhood in $\\{a,b\\}$. So, in
particular, $|V_{j}^{0}|\leq 4$.

Having this at hand, we can easily finish the proof of Theorem 22: We apply
Claim 24 to $C:=S$, and in the resulting trigraph $G_{0}$ we (as in the proof
of Theorem 19) contract $V_{0}[G_{0}]=\\{t\\}$ with $V_{1}[G_{0}]$ into one
vertex, then with $V_{2}[G_{0}]$, with $V_{3}[G_{0}]$, and so on.

By Claim 23, we have that only $(h+1)$ layers of ${\mathcal{L}}$ contribute to
the maximum red degree, which is thus at most $4(h+1)+h-1=5h+3<33\lfloor
h/2\rfloor$ ($+h$ simply estimates the contribution of the whole cycle $S$) in
this remaining contraction sequence of $G_{0}$.

So, the task is to prove Claim 24, which we do by induction as in the proof of
Lemma 4, and using analogous observations. In particular, although our graph
$G$ is not planar in general, its edges cannot cross the cycle $C$ of
$\operatorname{sk}(G^{+})$ by the definition of a skeleton.

From the inductive proof of Lemma 4, we get a subgraph
$R\subseteq\operatorname{sk}(G^{+})\cap G_{C}$ such that $X:=V(R)\setminus
V(C)$ satisfies Property 1 of Lemma 4. Considering the $a\geq 2$ bounded faces
of $C\cup R$ (which is $2$-connected), we denote their bounding cycles by
$D_{1},\ldots,D_{a}$, and say that the cycle $D_{i}$ is _nonempty_ if the
interior of $D_{i}$ contains a vertex of $G_{C}$. We furthermore have (from
the proof) that for each $i\in\\{1,\ldots,a\\}$, the intersection $D_{i}\cap
C$ is a path hitting at most two of the paths $P_{1},\ldots,P_{k}$
partitioning $C$, and that every vertex of $C$ (of $R-V(C)$) belongs to at
most two (three, respectively) nonempty ones of $D_{1},\ldots,D_{a}$. Note
that $a$ may be higher than $3$ (cf. the separable case of Lemma 4). We claim
that the paths $Q_{i}:=(R\cap D_{i})-V(C)$, $i\in\\{1,\ldots,a\\}$, satisfy
Property (V). Since $V(Q_{i})\subseteq V(R)\setminus V(C)=X$, Property (V) is
directly implied by Property 1 of Lemma 4, unless $q=3$ in the latter – then,
the proof of Lemma 4 uses three vertical paths of $\operatorname{sk}(G^{+})$
to make $R$, and only at most two of them belong to $D_{i}$, while the third
one may possibly intersect $D_{i}$ in one vertex (an end). Hence, a union of
$2\lfloor h/2\rfloor+1$ consecutive layers of ${\mathcal{L}}$ intersects
$Q_{i}$ in at most $2(2\lfloor h/2\rfloor+1)$ vertices of the two vertical
paths plus additional (cf. $|X^{\prime}|$ in Property 1) at most
$|X^{\prime}|+1\leq(\lfloor h/3\rfloor-1)+1\leq\lfloor h/2\rfloor-1$ vertices,
which altogether gives $\leq 5\lfloor h/2\rfloor+1$ as desired.

We are going to apply Claim 24 independently to each nonempty one of the
cycles $D_{i}$, $i\in\\{1,\ldots,a\\}$. For that, we first determine the
special pair $a_{i},b_{i}\in V(D_{i})$ anticipated in the claim. If
$V(D_{i})\cap\\{a,b\\}=\emptyset$, then we choose $a_{i}$ and $b_{i}$ as the
ends of the path $D_{i}\cap C$, and we take one or both of $a_{i},b_{i}$
arbitrarily if $D_{i}\cap C$ is one-vertex or empty. If $a,b\in V(D_{i})$,
then we choose $a_{i}=a$ and $b_{i}=b$. If, up to symmetry, $a\in V(D_{i})$
and $b\not\in V(D_{i})$, then we set $a_{i}=a$ and $b_{i}$ as one of the ends
of $D_{i}\cap C$ – we take an arbitrary of the two ends except the special
case described next; if $a\in V(D_{i})$, $b\in V(D_{i^{\prime}})$ and one end
(or both ends) of $D_{i}\cap C$ is an end (ends) of $D_{i^{\prime}}\cap C$,
then we set $b_{i}$ to the end shared with $D_{i^{\prime}}\cap C$ (and the
possible other shared end is set to $b_{i^{\prime}}$). The applications of
Claim 24 to nonempty ones of the cycles $D_{i}$, $i\in\\{1,\ldots,a\\}$,
result in partial contraction sequences of $G$ which compose (independently
one after another) into a partial contraction sequence from $G$ to a trigraph
$G_{1}$.

Let $W_{i}$ denote the set of vertices of $G_{1}$ that stem from the vertices
in $V(G_{D_{i}})\setminus V(D_{i})\subseteq U$ in the previous contractions.
Note that the vertices $a$ and $b$ have no red edges in $G_{1}$, and that
every other vertex of $C$ has red degree as claimed by Property (a) of Claim
24 along the partial sequence to $G_{1}$; the latter holds also for the
vertices $x$ of $C$ which belong to two nonempty cycles of
$D_{1},\ldots,D_{a}$, because $x$ has been set as $a_{i}$ or $b_{i}$ for at
least one of them (and hence received no red edge). A vertex $z\in
V(R)\setminus V(C)$ may belong to at most three nonempty of the cycles
$D_{1},\ldots,D_{a}$, and so by (again) Property (a) of Claim 24, its red
degree along the partial sequence to $G_{1}$ is always at most $3(8\lfloor
h/2\rfloor+8)\leq 33\lfloor h/2\rfloor+6$. No other vertex is supplied with
red edges from more than one of the recursive applications, and so the partial
contraction sequence from $G$ to $G_{1}$ fulfills the red-degree conditions of
Claim 24. Assume, up to symmetry, that $a,b\in V(D_{1})\cup V(D_{2})$. Set
$W_{1}^{\prime}=W_{1}$. For $i:=2,\ldots,a$, we obtain a trigraph $G_{i}$ from
$G_{i-1}$ by the following partial contraction sequence:

  * •

Let $X_{i}=V(R)\setminus(V(D_{i+1})\cup\ldots V(D_{a}))$ and
$Y_{i}=W^{\prime}_{i-1}\cup W_{i}\cup(X_{i}\cap U)$.

  * •

Iteratively, for $j:=1,2,3,\ldots\,$, and over the sets
$N:=\emptyset,\\{a\\},\\{b\\},\\{a,b\\}$, we contract into one vertex the set
$Z_{i,j}^{N}$ where $Z_{i,j}^{N}\subseteq Y_{i}$ is formed by those vertices
which are in layer $j$ of ${\mathcal{L}}$ and have the same
$G_{i-1}$-neighborhood $N$ in $\\{a,b\\}$. Precisely, we pick a vertex of
$Z_{i,j}^{N}$ at random, and successively contract other vertices of
$Z_{i,j}^{N}$ with it in any order.

  * •

We denote by $W_{i}^{\prime}$ the vertices of $G_{i}$ that stem from the
vertices of $Y_{i}$ in the previous.

Importantly, the set $Y_{i}$ in round $i$ captures all vertices which have
participated in a contraction since $G_{1}$, and those which are going to be
contracted in this round. The vertices $a,b$ receive no red edges during this
procedure, and in every round $i$, no red edges are created into the vertices
of $W_{i^{\prime}}$ for any $i^{\prime}>i$ or into $V(G)\setminus V(G_{C})$.
Furthermore, observe that $W_{i}$ has at most $4$ vertices in every layer of
${\mathcal{L}}$ by Property (c) of Claim 24, and likewise $W_{i}^{\prime}$ has
at most $4$ vertices in every layer of ${\mathcal{L}}$ by the condition of
distinct neighborhoods in $\\{a,b\\}$.

The remaining task is to verify the claimed properties of Claim 24 for the
partial contraction sequence from $G_{1}$ to $G_{0}:=G_{a}$ (as described by
the previous paragraph). Property (c) is trivial – we have just contracted the
vertices that way. Regarding Property (b) of Claim 24, we estimate the red
degree of every vertex $z$ in the interior of $C$ along the contraction
subsequence from $G_{i-1}$ to $G_{i}$ (for all $i:=2,\ldots,a$ as above).
First, if $z\in W_{i+1}\cup\ldots\cup W_{a}$, then the red degree of $z$ is as
required from the recursive application of Claim 24 – since no other red edge
to it has been created so far. If $z\in V(R)\setminus Y_{i}$ (in particular,
$z$ has not yet participated in a contraction), then $z$ is incident to at
most three nonempty cycles $D_{i^{\prime}}$, $i^{\prime}\in I^{\prime}$, and
if $\min(I^{\prime})>i$, then no red edge to $z$ has been created since
$G_{1}$ and the red degree of $z$ is as needed. Otherwise, $z$ may have red
edges to at most $2(8\lfloor h/2\rfloor+4)$ vertices of the (at most two) sets
$W_{i^{\prime}}$ where $i^{\prime}\in I^{\prime}$ and $i^{\prime}>i$ by
Property (a) of Claim 24, and to some vertices of $W^{\prime}_{i-1}\cup W_{i}$
(which include all vertices contracted since $G_{1}$). By Claim 23, at most
$2\lfloor h/2\rfloor+1$ layers of ${\mathcal{L}}$ may host red neighbors of
$z$, and $W^{\prime}_{i-1}\cup W_{i}$ has at most $4+4=8$ vertices in each
layer (as observed above), summing to $8(2\lfloor h/2\rfloor+1)$. Altogether,
$2(8\lfloor h/2\rfloor+4)+8(2\lfloor h/2\rfloor+1)=32\lfloor h/2\rfloor+16\leq
33\lfloor h/2\rfloor+\lfloor h/3\rfloor+13$ is an upper bound on the red
degree of $z\in V(R)\setminus Y_{i}$.

Lastly, we have the case of $z\in Y_{i}$. By the definition of $Y_{i}$, there
can be no red edge from $z$ to $W_{i+1}\cup\ldots\cup W_{a}$. Potential red
neighbors of $z$ in $V(C)\cup V(R)$ are estimated as follows. Again, by Claim
23, at most $2\lfloor h/2\rfloor+1$ layers of ${\mathcal{L}}$ may host red
neighbors of $z$. Consequently, the number of such red neighbors in $V(C)$ is
at most $3(5\lfloor h/2\rfloor+1)$ by Property (V), and in $V(R)$ it is at
most $3(2\lfloor h/2\rfloor+1)+\lfloor h/3\rfloor-1$ by Property 1 of Lemma 4.
Note that the previous estimate accounts also for the vertices of $V(R)$ in
$Y_{i}$, and so the remaining red neighbors of $z$ must belong to
$W^{\prime}_{i-1}\cup W_{i}$, which we bound in the next paragraph.

Assume that we are now contracting in layer $j$ of ${\mathcal{L}}$ (see the
above contraction procedure) and that $z$ belongs to layer $j^{\prime}$. Then,
by Claim 23, red neighbors of $z$ may lie in layer $j^{\prime}$ and in the
$\lfloor h/2\rfloor$ previous and $\lfloor h/2\rfloor$ next layers. If
$j^{\prime}\leq j$, then in the $\lfloor h/2\rfloor$ previous layers,
$W^{\prime}_{i-1}\cup W_{i}$ has already been contracted down to at most $4$
vertices per layer, and hence the number of red neighbors of $z$ in
$W^{\prime}_{i-1}\cup W_{i}$ is at most $4\lfloor h/2\rfloor+8(\lfloor
h/2\rfloor+1)=12\lfloor h/2\rfloor+8$. If $j^{\prime}>j$, then $z$ has not
participated yet in a contraction between $W^{\prime}_{i-1}$ and $W_{i}$, and
so $z$ has no red neighbors of layers $\geq j^{\prime}$ in $W_{i}$ if $z\in
W^{\prime}_{i-1}$ (in $W^{\prime}_{i-1}$ if $z\in W_{i}$, resp.). Therefore,
this time the number of red neighbors of $z$ in $W^{\prime}_{i-1}\cup W_{i}$
is at most $4(\lfloor h/2\rfloor+1)+8\lfloor h/2\rfloor=12\lfloor
h/2\rfloor+4$. Summing the previous terms together, the red degree of $z\in
Y_{i}$ is always at most $3(5\lfloor h/2\rfloor+1)+3(2\lfloor
h/2\rfloor+1)+\lfloor h/3\rfloor-1+12\lfloor h/2\rfloor+8=33\lfloor
h/2\rfloor+\lfloor h/3\rfloor+13$.

At last, we check Property (a) of Claim 24. This has already been verified for
$G_{1}$ above. However, it will be useful to understand this bound on the red
degrees of $V(C)$ in $G_{1}$ in closer detail. To recapitulate, a vertex $z\in
V(C)$ can have, in $G_{1}$, red neighbors in at most $2\lfloor h/2\rfloor+1$
layers of ${\mathcal{L}}$ by Claim 23, and at the same time in vertices that
belong to at most one of the sets $W_{1},\ldots,W_{a}$ by our choice of
$a_{i},b_{i}$ in the recursive applications of Claim 24. Furthermore, each set
$W_{i}$ has at most $4$ vertices in one layer of ${\mathcal{L}}$ (see above),
and this leads to the upper bound of $4(2\lfloor h/2\rfloor+1)=8\lfloor
h/2\rfloor+4$.

We are going to argue that at every step along the contraction subsequence
from $G_{i-1}$ to $G_{i}$ (for all $i:=2,\ldots,a$ as above), a vertex $z\in
V(C)$ has at most $4$ red neighbors (in $Y_{i}$) in every layer of
${\mathcal{L}}$ except the layer $j$ which is currently being contracted (cf.
the sets $Z_{i,j}^{N}$ above). For layers $j^{\prime}<j$, this is trivial
since our contraction subsequence has left only at most $4$ vertices (by four
distinct neighborhoods in $\\{a,b\\}$) as potential red neighbors. For layers
$j^{\prime}>j$ we have, by the previous arguments about $G_{1}$, that red
neighbors of $z$ are either in $W_{i-1}^{\prime}$ or in $W_{i}$, but not in
both, and so the upper bound of $4$ again follows. In layer $j$, the order of
contractions in the sets $Z_{i,j}^{N}$ ensure that at most one new red edge
adds to $z$ for each of the four choices of $N$ (and, of course, these
potentially added edges are again dismissed after $Z_{i,j}^{N}$ is contracted
into one vertex). By a rough estimate, $z$ has at most $4+4=8$ red neighbors
in layer $j$, together at most $4\cdot 2\lfloor h/2\rfloor+8=8\lfloor
h/2\rfloor+8$, as desired. At the end of this subsequence, that is in $G_{i}$,
the latter bound readily decreases to $8\lfloor h/2\rfloor+4$. We are done
with a proof of Claim 24, and hence finished the proof of the theorem. ∎

######  Corollary 25.

The twin-width of simple $1$-planar and optimal $2$-planar graphs is at most
$80$.

We point out that Theorem 22 implies an improvement on the twin-width of
$k$-map graphs only up to a certain $k$, as these graphs have bounded twin-
width independently of $k$ [DBLP:journals/jacm/BonnetKTW22].

##  6 Conclusions

Our structural results are constructive and can easily be implemented to run
in quadratic time, provided that the input graph is a topological $h$-framed
graph. A major open question is to obtain a speed up in these constructions.
The recent algorithmic advances in [DBLP:journals/corr/abs-2202-08870,
DBLP:journals/corr/abs-2004-02530] may lead to linear-time implementations.
Another important open problem is whether each $k$-planar graph is a subgraph
of the strong product of a path, a (planar) graph of constant treewidth, and a
clique of size linear in $k$, as our results suggest that such a structure
might be possible.

## References

  * [1] Martin Aigner and Günter M. Ziegler.  Proofs from THE BOOK (3. ed.).  Springer, 2004.
  * [2] Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, and Sergey Pupyrev.  Queue layouts of planar 3-trees.  Algorithmica, 82(9):2564–2585, 2020.  doi:10.1007/s00453-020-00697-4.
  * [3] Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov.  Straight-line grid drawings of 3-connected 1-planar graphs.  In Stephen K. Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of LNCS, pages 83–94. Springer, 2013.  URL: https://doi.org/10.1007/978-3-319-03841-4_8, doi:10.1007/978-3-319-03841-4\\_8.
  * [4] Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi N. Raftopoulou.  Book embeddings of nonplanar graphs with small faces in few pages.  CoRR, abs/2003.07655, 2020.  arXiv:2003.07655.
  * [5] Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou.  On optimal 2- and 3-planar graphs.  In Boris Aronov and Matthew J. Katz, editors, SoCG, volume 77 of LIPIcs, pages 16:1–16:16. Schloss Dagstuhl, 2017.  URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.16, doi:10.4230/LIPIcs.SoCG.2017.16.
  * [6] Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi N. Raftopoulou.  Book embeddings of nonplanar graphs with small faces in few pages.  In SoCG, volume 164 of LIPIcs, pages 16:1–16:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [7] Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk.  Shorter labeling schemes for planar graphs.  In Shuchi Chawla, editor, SODA, pages 446–462. SIAM, 2020.  URL: https://doi.org/10.1137/1.9781611975994.27, doi:10.1137/1.9781611975994.27.
  * [8] É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.
  * [9] É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.
  * [10] Prosenjit Bose, Pat Morin, and Saeed Odak.  An optimal algorithm for product structure in planar graphs.  CoRR, abs/2202.08870, 2022.  URL: https://arxiv.org/abs/2202.08870, arXiv:2202.08870.
  * [11] Michal Debski, Stefan Felsner, Piotr Micek, and Felix Schröder.  Improved bounds for centered colorings.  In Shuchi Chawla, editor, SODA, pages 2212–2226. SIAM, 2020\.  URL: https://doi.org/10.1137/1.9781611975994.136, doi:10.1137/1.9781611975994.136.
  * [12] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [13] Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David Wood.  Planar graphs have bounded nonrepetitive chromatic number.  Advances in Combinatorics, Mar 2020.  URL: http://dx.doi.org/10.19086/aic.12100, doi:10.19086/aic.12100.
  * [14] Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin.  Adjacency labelling for planar graphs (and beyond).  In FOCS. IEEE, 2020.  URL: https://doi.org/10.1109/FOCS46700.2020.00060, doi:10.1109/FOCS46700.2020.00060.
  * [15] Vida Dujmovic, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood.  Clustered 3-colouring graphs of bounded degree.  Comb. Probab. Comput., 31(1):123–135, 2022.  URL: https://doi.org/10.1017/S0963548321000213, doi:10.1017/S0963548321000213.
  * [16] 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.
  * [17] Vida Dujmovic, Pat Morin, and David R. Wood.  Graph product structure for non-minor-closed classes.  CoRR, abs/1907.05168, 2020.  URL: http://arxiv.org/abs/1907.05168, arXiv:1907.05168.
  * [18] Zdenek Dvořák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu, and David R. Wood.  Notes on graph product structure theory.  CoRR, abs/2001.08860, 2020.  URL: https://arxiv.org/abs/2001.08860, arXiv:2001.08860.
  * [19] Lenwood S. Heath, Frank Thomson Leighton, and Arnold L. Rosenberg.  Comparing queues and stacks as mechanisms for laying out graphs.  SIAM J. Discrete Math., 5(3):398–412, 1992.  doi:10.1137/0405031.
  * [20] Lenwood S. Heath and Arnold L. Rosenberg.  Laying out graphs using queues.  SIAM J. Comput., 21(5):927–958, 1992.  doi:10.1137/0221055.
  * [21] Hugo Jacob and Marcin Pilipczuk.  Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs.  CoRR, abs/2201.09749, 2022.  URL: https://arxiv.org/abs/2201.09749, arXiv:2201.09749.
  * [22] Pat Morin.  A fast algorithm for the product structure of planar graphs.  CoRR, abs/2004.02530, 2020.  URL: https://arxiv.org/abs/2004.02530, arXiv:2004.02530.
  * [23] Pat Morin, Vida Dujmović, Sergey Norin, and David Wood.  Graph product structure theory.  Banff Int., Nov. 21-26 2021.
  * [24] Michal Pilipczuk and Sebastian Siebertz.  Polynomial bounds for centered colorings on proper minor-closed graph classes.  J. Comb. Theory, Ser. B, 151:111–147, 2021.  URL: https://doi.org/10.1016/j.jctb.2021.06.002, doi:10.1016/j.jctb.2021.06.002.
  * [25] Torsten Ueckerdt, David R. Wood, and Wendy Yi.  An improved planar graph product structure theorem.  CoRR, abs/2108.00198, 2021.  URL: https://arxiv.org/abs/2108.00198, arXiv:2108.00198.