11institutetext: Department of Computer Science, University of Tübingen,
Tübingen, Germany
11email<EMAIL_ADDRESS>22institutetext: Theoretical
Computer Science, Osnabrück University, Osnabrück, Germany
22email<EMAIL_ADDRESS>33institutetext: School of Applied
Mathematics and Physical Sciences, NTUA, Athens, Greece
33email<EMAIL_ADDRESS>
# On the Queue Number of Planar Graphs

Michael A. Bekos 11 Martin Gronemann 22 Chrysanthi N. Raftopoulou 33

###### Abstract

A $k$-queue layout is a special type of a linear layout, in which the linear
order avoids $(k+1)$-rainbows, i.e., $k+1$ independent edges that pairwise
form a nested pair. The optimization goal is to determine the queue number of
a graph, i.e., the minimum value of $k$ for which a $k$-queue layout is
feasible. Recently, Dujmović et al. [J. ACM, 67(4), 22:1-38, 2020] showed that
the queue number of planar graphs is at most $49$, thus settling in the
positive a long-standing conjecture by Heath, Leighton and Rosenberg. To
achieve this breakthrough result, their approach involves three different
techniques: (i) an algorithm to obtain straight-line drawings of outerplanar
graphs, in which the $y$-distance of any two adjacent vertices is $1$ or $2$,
(ii) an algorithm to obtain $5$-queue layouts of planar $3$-trees, and (iii) a
decomposition of a planar graph into so-called tripods. In this work, we push
further each of these techniques to obtain the first non-trivial improvement
of the upper bound on queue number of planar graphs from $49$ to $42$.

###### Keywords:

Queue layouts, Planar graphs, Queue number

##  1 Introduction

Linear layouts of graphs have a long tradition of study in different contexts,
including graph theory and graph drawing, as they form a framework for
defining different graph-theoretic parameters with several applications; see,
e.g., [9]. In this regard, one seeks to find a total order of the vertices of
a graph that reaches a certain optimization goal [3, 7, 19]. In this work, we
focus on a well-studied type of linear layouts, called queue layout [12, 17,
18, 21], in which the goal is to minimize the size of the largest rainbow,
namely, a set of independent edges that are pairwise nested. Equivalently, the
problem asks for a linear order of the vertices and a partition of the edges
into a minimum number of queues (called queue number), such that no two
independent edges in the same queue are nested [18]; see Fig. 1(b).

Queue layouts of graphs were introduced by Heath and Rosenberg [18] in 1992 as
the counterpart of stack layouts (widely known also as book embeddings), in
which the edges must be partitioned into a minimum number of stacks (called
stack number), such that no two edges in the same stack cross [6]; see Fig.
1(c). Since their introduction, queue layouts of graphs have been a fruitful
subject of intense research with several important milestones over the years
[1, 2, 4, 13, 17, 21, 22]; for an introduction, we refer the interested reader
to [15].

The most intriguing problem in this research field is undoubtedly the problem
of specifying the queue number of planar graphs, that is, the maximum queue
number of a planar graph. This problem dates back to a conjecture by Heath,
Leighton and Rosenberg, who in 1992 conjectured that the queue number of
planar graphs is bounded [17]. Notably, despite the different efforts [2, 8,
10], this conjecture remained unanswered for more than two decades. That only
changed in 2019 with a breakthrough result of Dujmović, Joret, Micek, Morin,
Ueckerdt and Wood [11], who managed to settle in the positive the conjecture,
as they showed that the queue number of planar graphs is at most $49$. The
best-known corresponding lower bound is $4$ due to Alam et al. [1].

It is immediate to see, however, that the gap between the currently best-known
lower and upper bounds is rather large, which implies that the exact queue
number of planar graphs is, up to the point of writing, still unknown. Note
that this is in contrast with the maximum stack number of planar graphs, which
was recently shown to be exactly $4$ [5, 23]. Also, the existing gap in the
bounds on the queue number of planar graphs gives the intuition that it is
unlikely the upper bound of $49$ by Dujmović at al. [11] to be tight, even
though in the last two years no improvement appeared in the literature.

(a)

(b) 2-queue layout

(c) 2-stack layout

Figure 1:  (a) The octahedron graph and (b)-(c) different linear layouts of
it.

#### Our contribution.

We verify the aforementioned intuition by reducing the upper bound on the
queue number of planar graphs from $49$ to $42$ (see Theorem 5.1 in Section
5). To achieve this, we present improvements to each of the following three
main techniques involved in the approach by Dujmović at al. [11]:  (i) an
algorithm to obtain straight-line drawings of outerplanar graphs, in which the
$y$-distance of any two adjacent vertices is $1$ or $2$ [14]; see Section 4.1,
(ii) an algorithm to obtain $5$-queue layouts of planar $3$-trees [1]; see
Section 4.2, and  (iii) a decomposition of a planar graph into so-called
tripods [11]; see Section 4.3.  Although we assume familiarity with these
techniques, we outline in Section 3 their most important aspects; also, for
preliminary notions and standard terminology refer to Section 2.

##  2 Preliminaries

A drawing of a graph maps each vertex to a distinct point of the Euclidean
plane and each edge to a Jordan curve connecting its endpoints. A drawing of a
graph is planar, if no two edges cross (expect at common endpoints). A graph
that admits a planar drawing is called planar. A planar drawing partitions the
plane into topologically connected regions called faces; its unbounded one is
called outer. A combinatorial embedding of a planar graph is an equivalence
class of planar drawings that are pairwise topologically equivalent, i.e.,
they define the same set of faces up to an orientation-preserving
homeomorphism of the plane. A planar graph together with a combinatorial
embedding is a plane graph. A graph that admits a planar drawing, in which all
vertices are incident to its outer face, is called outerplanar. It is known
that outerplanar graphs have treewidth at most $2$. A planar graph with
treewidth at most $3$ is commonly referred to as a planar $3$-tree. Planar
$3$-trees are subgraphs of maximal planar $3$-trees, where such an $n$-vertex
graph is either a $3$-cycle, if $n=3$, or has a degree-$3$ vertex whose
deletion yields a maximal planar $3$-tree with $n-1$ vertices, if $n>3$.

A vertex order $\prec$ of a simple undirected graph $G$ is a total order of
its vertices, such that for any two vertices $u$ and $v$ of $G$, $u\prec v$ if
and only if $u$ precedes $v$ in the order. Let $F$ be a set of $k\geq 2$
independent edges $(u_{i},v_{i})$ of $G$, that is,
$F=\\{(u_{i},v_{i});\;i=1,\ldots,k\\}$. If $u_{1}\prec\ldots\prec u_{k}\prec
v_{k}\prec\ldots\prec v_{1}$, then we say that the edges of $F$ form a
$k$-rainbow, while if $u_{1}\prec v_{1}\prec\ldots\prec u_{k}\prec v_{k}$,
then the edges of $F$ form a $k$-necklace. The edges of $F$ form a $k$-twist,
if $u_{1}\prec\ldots\prec u_{k}\prec v_{1}\prec\ldots\prec v_{k}$; see Fig. 2.
Two independent edges that form a $2$-rainbow ($2$-necklace, $2$-twist) are
referred to as nested (disjoint, crossing, respectively).

(a)

(b)

(c)

Figure 2: Illustration of (a) a $3$-rainbow, (b) a $3$-necklace, and (c) a
$3$-twist.

A $k$-queue layout of a graph consists of a vertex order $\prec$ of $G$ and a
partition of the edge-set of $G$ into $k$ sets of pairwise non-nested edges,
called queues. A preliminary result by Heath and Rosenberg [18] states that a
graph admits a $k$-queue layout if and only if it admits a vertex order in
which no $(k+1)$-rainbow is formed. The queue number of a graph $G$, denoted
by $\mathrm{qn}(G)$, is the minimum $k$, such that $G$ admits a $k$-queue
layout. Accordingly, the queue number of a class of graphs is the maximum
queue number over all its members.

##  3 Sketch of the involved techniques

In the following, we sketch the main aspects of the three algorithms mentioned
in Section 1 that are involved in the approach by Dujmović et al. [12] to
achieve the bound of $49$ on the queue number of planar graphs. The first is
an algorithm by Dujmović, Pór, and Wood [14] to compute $2$-queue layouts of
outerplanar graphs (Section 3.1). The second one is by Alam et al. [1] to
compute $5$-queue layouts of planar $3$-trees (Section 3.2). The last one is
the actual algorithm by Dujmović et al. [12] to compute $49$-queue layouts of
planar graphs (Section 3.3).

###  3.1 Outerplanar Graphs

The main ingredient of the algorithm by Dujmović, Pór and Wood [14] is an
algorithm to obtain a straight-line drawing $\Gamma(G)$ of a maximal
outerplane graph $G$ whose output can be transformed into a $2$-queue layout
of $G$. The recursive construction of $\Gamma(G)$ maintains the following
invariant properties:

  1. (O.1)

The cycle delimiting the outerface consists of two strictly $x$-monotone
paths, referred to as upper and lower envelopes, respectively.

  2. (O.2)

The $y$-coordinates of the endvertices of each edge differ by either one
(span-$1$ edge) or two (span-$2$ edge).

(a)

(b)

Figure 3: Introducing a degree-$2$ vertex $v$ along the upper envelope, when
its two neighbors $u$ and $w$ are connected with (a) a span-1 edge, and (b) a
span-2 edge.

To maintain (O.1) and (O.2), Dujmović et al. adopt an approach in which at
each recursive step a vertex of degree $2$ is added to the already constructed
drawing; see Fig. 3. The base of the recursion consists of a triangle111In
[14], Dujmović et al. consider a single edge at the base of the recursion. To
ease the presentation, we slightly modify their approach. that can be
trivially drawn with two span-$1$ edges and one span-$2$ edge satisfying
Invariants (O.1) and (O.2). Assume that $G$ has $n>3$ vertices. Since $G$ is
biconnected outerplane, it contains a vertex $v$ of degree $2$. Removing $v$
yields a biconnected outerplane graph $G^{\prime}$ with $n-1$ vertices, which
recursively admits a drawing $\Gamma(G^{\prime})$ satisfying Invariants (O.1)
and (O.2). By Invariant (O.1), none of the edges in $\Gamma(G^{\prime})$ is
drawn vertically. To obtain drawing $\Gamma(G)$ of $G$ vertex $v$ is
introduced in $\Gamma(G^{\prime})$ as follows. Let $u$ and $w$ be the
neighbors of $v$ in $G$. Since $G$ is maximal outerplane, $(u,w)$ is an edge
of $G$ that lies on the outerface of $\Gamma(G^{\prime})$. By Invariant (O.2),
$(u,w)$ is either a span-$1$ or a span-$2$ edge. Assume that $(u,w)$ is along
the upper envelope of $\Gamma(G^{\prime})$; the case where it is along the
lower envelope is symmetric. Assume first that $(u,w)$ has span $1$ in
$\Gamma(G^{\prime})$ and w.l.o.g. that $y(u)=y(w)+1$. Then, vertex $v$ is
placed such that $y(v)=y(u)+1$ and $x(v)=\frac{1}{2}(x(u)+x(w))$; see Fig.
3(a). Hence, $(u,v)$ and $(v,w)$ have span $1$ and $2$, respectively, which
implies that Invariant (O.2) is maintained. Since edge $(u,w)$ of the upper
envelope of $\Gamma(G^{\prime})$ is replaced by the $x$-monotone path
$u\rightarrow v\rightarrow w$ in $\Gamma(G)$, Invariant (O.1) is also
maintained. Assume now that $(u,w)$ has span $2$ in $\Gamma(G^{\prime})$ and
w.l.o.g. that $y(u)=y(w)+2$. Then, vertex $v$ is placed such that
$y(v)=y(u)-1$ and $x(v)=\frac{3x(u)+x(w)}{4}$; see Fig. 3(b). This implies
that both edges $(u,v)$ and $(v,w)$ have span $1$. Similarly to the previous
case, one can argue that Invariants (O.1) and (O.2) are maintained. Drawing
$\Gamma(G)$ is transformed to a $2$-queue layout of $G$ as follows:

  1. (i)

for any two vertices $u$ and $v$ of $G$, $u\prec v$ if and only if either
$y(u)>y(v)$, or $y(u)=y(v)$ and $x(u)<x(v)$ in $\Gamma(G)$,

  2. (ii)

edge $(u,v)$ is assigned to the first (second) queue if it has span $1$ ($2$,
respectively) in $\Gamma(G)$.

###  3.2 Planar 3-trees

Alam et al. [1] adopt a peeling-into-levels approach [16] to produce a
$5$-queue layout of a maximal plane $3$-tree $H$. Initially, the vertices of
$H$ are partitioned into levels $L_{0},\ldots,L_{\lambda}$ with $\lambda\geq
1$, such that $L_{0}$-vertices are incident to the outer face of $H$, while
$L_{i+1}$-vertices are in the outer face of the subgraph of $H$ obtained by
the removal of all vertices in $L_{0},\ldots,L_{i}$. The edges of $H$ are
partitioned into level and binding, depending on whether their endpoints are
on the same or on consecutive levels. As each connected component of the
subgraph $H_{i}$ of $H$ induced by the edges of level $L_{i}$ is an internally
triangulated outerplane graph, it is embeddable in two queues. This implies
that each connected component $c$ of $H_{i+1}$ (which is outerplane) lies in
the interior of a triangular face of $H_{i}$, therefore there are exactly
three vertices of $H_{i}$ that are connected to $c$. The constructed $5$-queue
layout of $H$ satisfies the following invariant properties:

  1. (T.1)

The linear order ${\prec_{\mathrm{\tiny H}}}$ is such that all vertices of
level $L_{j}$ precede all vertices of level $L_{j+1}$ for every
$j=0,\ldots,\lambda-1$;

  2. (T.2)

Vertices of each connected component of level $L_{j}$ appear consecutively in
${\prec_{\mathrm{\tiny H}}}$ for every $j=0,\ldots,\lambda$;

  3. (T.3)

Level edges of each of the levels $L_{0},\ldots,L_{\lambda}$ are assigned to
two queues denoted by ${\mathcal{Q}}_{0}$ and ${\mathcal{Q}}_{1}$;

  4. (T.4)

For every $j=0,\ldots,\lambda-1$, the binding edges between $L_{j}$ and
$L_{j+1}$ are assigned to three queues ${\mathcal{Q}}_{2}$,
${\mathcal{Q}}_{3}$ and ${\mathcal{Q}}_{4}$ as follows. For each connected
component $c$ of $H_{j+1}$, let $x$, $y$ and $z$ be its three neighbors in
$H_{j}$ so that $x\;{\prec_{\mathrm{\tiny H}}}\;y\;{\prec_{\mathrm{\tiny
H}}}\;z$. Then, the binding edges between $L_{j}$ and $L_{j+1}$ incident to
$c$ are assigned to ${\mathcal{Q}}_{2}$, ${\mathcal{Q}}_{3}$ and
${\mathcal{Q}}_{4}$ if they lead to $x$, $y$ and $z$, respectively.

###  3.3 General Planar Graphs

Central in the algorithm by Dujmović et al. [12] is the notion of
$H$-partition222To avoid confusion with notation used earlier, note that, in
the scope of the algorithm by Dujmović et al. [12], graph $H$ denotes a plane
$3$-tree, as we will shortly see., defined as follows. Given a graph $G$, an
$H$-partition of $G$ is a partition of the vertices of $G$ into sets $A_{x}$
with $x\in V(H)$, called bags, such that for each edge $(u,v)$ of $G$ with
$u\in A_{x}$ and $v\in A_{y}$ either $x=y$ holds or $(x,y)$ is an edge of $H$.
In the former case, $(u,v)$ is called intra-bag edge, while in the latter case
inter-bag. A BFS-layering of $G$ is a partition
$\mathcal{L}=(V_{0},V_{1},\ldots)$ of its vertices according to their distance
from a specific vertex $r$ of $G$, i.e., it is a special type of
$H$-partition, where $H$ is a path and each bag $V_{i}$ corresponds to a
layer. In this regard, an intra-bag edge is called intra-layer, while an
inter-bag edge is called inter-layer 333Dujmović et al. [12] refer to the
intra- and inter-layer edges as intra- and inter-level edges, respectively. We
adopt the terms intra- and inter-layer edges to avoid confusion with the
different type of leveling used in the algorithm of Alam et al. [1].. An
$H$-partition has layered-width $\ell$ with respect to a BFS-layering
$\mathcal{L}$ if each bag of $H$ has at most $\ell$ vertices on each layer of
$\mathcal{L}$.

(a) Intra-bag edges

(b) Inter-bag edges

Figure 4: Illustration of (a) Intra-bag edges; the intra-layer ones are red,
while the inter-layer ones are blue, and (b) inter-bag edges; the intra-layer
ones are green, while the inter-layer ones are purple (forward) and orange
(backward).

######  Lemma 1 (Dujmović et al. [12]).

For all graphs $G$ and $H$, if $H$ admits a $k$-queue layout and $G$ has an
$H$-partition of layered-width $\ell$ with respect to some layering
$\mathcal{L}=(V_{0},V_{1},\ldots)$ of $G$, then $G$ admits a $(3\ell
k+\lfloor\frac{3}{2}\ell\rfloor)$-queue layout using vertex order
$\overrightarrow{V_{0}},\overrightarrow{V_{1}},\dots$, where
$\overrightarrow{V_{i}}$ is some order of $V_{i}$. In particular,

$\mathrm{qn}(G)\leq 3\ell\,\mathrm{qn}(H)+\lfloor\tfrac{3}{2}\ell\rfloor.$ (1)

In the proof of Lemma 1, the order of the vertices of $G$ on each layer of
$\mathcal{L}$ is defined as follows. Let $x_{1},\dots,x_{h}$ be the vertices
of $H$ as they appear in a $k$-queue layout $\mathit{QL}(H)$ of $H$ and let
$A_{x_{1}},\dots,A_{x_{h}}$ be the corresponding bags of the $H$-partition.
Then, the order $\overrightarrow{V_{i}}$ of each layer $V_{i}$ with $i\geq 0$
is:

$\overrightarrow{V_{i}}=A_{x_{1}}\cap V_{i},A_{x_{2}}\cap
V_{i},\dots,A_{x_{h}}\cap V_{i}$

where each subset $A_{x_{j}}\cap V_{i}$ is ordered arbitrarily. This gives the
total order ${\prec_{\mathrm{\tiny G}}}$ for the vertices of $G$. The edge-to-
queue assignment, which completes the construction of the queue layout
$\mathit{QL}(G)$ of $G$, exploits the following two properties:

  1. (P.1)

Two intra-bag edges nest in ${\prec_{\mathrm{\tiny G}}}$, only if they belong
to the same bag; see blue and red edges in Fig. 4(a).

  2. (P.2)

Two inter-layer edges nest in ${\prec_{\mathrm{\tiny G}}}$, only if their
endpoints belong to the same pair of consecutive layers of $\mathcal{L}$; see
blue, purple and orange edges in Fig. 4.

For the edge-to-queue assignment, the edges of $G$ are classified into four
categories given by the bags of the $H$-partition and the layers of
$\mathcal{L}$. We start with edges whose endpoints belong to the same bag
(i.e., intra-bag edges); see Fig. 4(a).

  1. (E.1)

Intra-layer intra-bag edges of $G$ are assigned to at most
$\lfloor\frac{\ell}{2}\rfloor$ queues, as the queue number of $K_{\ell}$ is
$\lfloor\frac{\ell}{2}\rfloor$ [16]; see red edges in Fig. 4(a).

  2. (E.2)

Inter-layer intra-bag edges of $G$ are assigned to at most $\ell$ queues, as
the queue number of $K_{\ell,\ell}$ is $\ell$, when all vertices of the first
bipartition precede those of the second; see blue edges in Fig. 4(a).

The remaining edges of $G$ connect vertices of different bags (i.e., inter-bag
edges); see Fig. 4(b). We further partition the inter-layer inter-bag edges
into two categories. Let $(u,v)$ be an inter-layer inter-bag edge with $u\in
A_{x}\cap V_{i}$ and $v\in A_{y}\cap V_{i+1}$, for some $i\geq 0$. Then
$(u,v)$ is forward, if $x\;{\prec_{\mathrm{\tiny H}}}\;y$ holds in
$\mathit{QL}(H)$; otherwise, it is backward; see purple and orange edges in
Fig. 4(b), respectively. For all inter-bag edges, in total, $3\ell k$ queues
suffice (see [12, Lemma 9] for details).

  1. (E.3)

Intra-layer inter-bag edges of $G$ are assigned to at most $\ell k$ queues; on
each layer, an edge of $H$ corresponds to a subgraph of $K_{\ell,\ell}$, where
the first bipartition precedes the second; see green edges in Fig. 4(b).

  2. (E.4)

Forward inter-layer inter-bag edges of $G$ are assigned to at most $\ell k$
queues; for two consecutive layers, an edge of $H$ corresponds to a subgraph
of $K_{\ell,\ell}$, where the first bipartition precedes the second; see
purple edges of Fig. 4(b).

  3. (E.5)

Symmetrically all backward inter-layer inter-bag edges of $G$ are assigned to
at most $\ell k$ queues; see orange edges in Fig. 4(b).

The next property follows from the proof of Lemma 9 in [12]:

  1. (P.3)

For $1\leq i\leq r$, let $(u_{i},v_{i})$ be an edge of $G$, such that
$u_{i}\;{\prec_{\mathrm{\tiny G}}}\;v_{i}$, $u_{i}\in A_{x_{i}}$ and $v_{i}\in
A_{y_{i}}$. If all these $r$ edges belong to one of (E.3)-(E.5) and form an
$r$-rainbow in ${\prec_{\mathrm{\tiny G}}}$, while edges
$(x_{1},y_{1}),\ldots,(x_{r},y_{r})$ of $H$ are assigned to the same queue in
$\mathit{QL}(H)$, then $r\leq\ell$ and either $u_{1},\ldots,\allowbreak u_{r}$
or $v_{1},\ldots,v_{r}$ belong to the same bag of the $H$-partition of $G$.

If $G$ is maximal plane, few more ingredients are needed to apply Lemma 1. A
vertical path of $G$ in a BFS-layering $\mathcal{L}$ is a path
$P=v_{0},\dots,v_{k}$ of $G$ consisting only of edges of the BFS-tree of
$\mathcal{L}$ and such that if $v_{0}$ belongs to $V_{i}$ in $\mathcal{L}$,
then $v_{j}$ belongs to $V_{i+j}$, with $j=1,\ldots,k$. Further, we say that
$v_{0}$ and $v_{k}$ are the first and last vertices of $P$. A tripod of $G$
consists of up to three pairwise vertex-disjoint vertical paths in
$\mathcal{L}$ whose last vertices form a clique of size at most $3$ in $G$. We
refer to this clique as the base of the tripod. Dujmović et al. [12] showed
that for any BFS-layering $\mathcal{L}$, $G$ admits an $H$-partition with the
following properties:

  1. (P.4)

$H$ is a planar $3$-tree and thus $\mathit{QL}(H)$ is a $k$-queue layout with
$k\leq 5$ [1].

  2. (P.5)

Its layered-width $\ell$ is at most $3$, since each bag induces a tripod in
$G$, whose base is a triangular face of $G$, if it is a $3$-clique.

Properties (P.4) and (P.5) along with Eq. 1 imply that the queue number of
planar graphs is at most $3\cdot 3\cdot 5+\lfloor\tfrac{3}{2}\cdot
3\rfloor=49$.

##  4 Refinements of the involved techniques

In this section, we present refinements of the algorithms outlined in Section
3 that will allow us to reduce the upper bound on the queue number of planar
graphs.

###  4.1 Outerplanar Graphs

We modify the algorithm by Dujmović et al. [14] outlined in Section 3.1 to
guarantee two additional properties (stated in Lemma 2) of the outerplanar
drawing. To this end, besides Invariants (O.1) and (O.2), we maintain a third
one:

  1. (O.3)

The lower envelope consists of a single edge.

To maintain Invariant (O.3), we observe that a biconnected maximal outerplane
graph with at least four vertices contains at least two non-adjacent
degree-$2$ vertices. Let $x$ be such a degree-$2$ vertex of $G$, which we
assume to be fixed in the recursive construction of $\Gamma(G)$. In
particular, by our previous observation, we can always remove a degree-$2$
vertex that is different from $x$ at every recursive step. This ensures that
$x$ will eventually appear in the triangle $\mathcal{T}$ that is drawn at the
base of the recursion. We draw $\mathcal{T}$, such that $x$ is its bottommost
vertex while its two incident edges are of span-1 and span-2 as follows. Let
$y$ and $z$ be the other two vertices of $\mathcal{T}$. We draw $x$, $y$ and
$z$ at $(2,0)$, $(0,1)$ and $(1,2)$, respectively. This implies that $(x,y)$
forms the lower envelope of $\mathcal{T}$, while $(y,z)$ and $(z,x)$ form the
upper one. This guarantees that Invariant (O.3) is maintained at the base of
the recursion. Assume now that drawing $\Gamma(G^{\prime})$ obtained by
removing $v$ from $G$ satisfies Invariant (O.3), such that the edge $(x,y)$ of
$\mathcal{T}$ forms the lower envelope of $\Gamma(G^{\prime})$. Since $(x,y)$
belongs to the outer face of $G$, it follows that $v$ is incident to two
vertices of the upper envelope of $\Gamma(G^{\prime})$. So, after the addition
of $v$ to $\Gamma(G^{\prime})$ in order to obtain $\Gamma(G)$, edge $(x,y)$
forms the lower envelope of $\Gamma(G)$, as desired.

Let $\langle u,v,w\rangle$ be a face of $\Gamma(G)$ such that $y(u)-y(w)=2$
and $y(u)-y(v)=y(v)-y(w)=1$. We refer to vertices $u$, $v$ and $w$ as the top,
middle and bottom vertex of the face, respectively444Alam et al. [1] refer to
the middle vertex of a triangular face in $\Gamma(G)$ as its anchor.. Further,
we say that face $\langle u,v,w\rangle$ is a bottom, side and top triangle for
vertices $u$, $v$ and $w$, respectively.

In the next lemma, we prove two properties of drawing $\Gamma(G)$. Part (a) of
Lemma 2 requires Invariant (O.3), i.e., it does not necessarily hold for all
drawings obtained by the algorithm by Dujmović et al. [14]. On the other hand,
part (b) of Lemma 2 holds for drawings that do not necessarily satisfy
Invariant (O.3), i.e., it is a property of the original algorithm by Dujmović
et al. [14].

######  Lemma 2.

Let $\Gamma(G)$ be an outerplanar drawing satisfying Invariants (O.1)–(O.3) of
a biconnected maximal outerplane graph $G$. Then, each vertex of $G$ is

  1. (a)

the top vertex of at most two triangular faces of $\Gamma(G)$ and

  2. (b)

the side vertex of at most two triangular faces of $\Gamma(G)$.

###### Proof.

For (a), consider a vertex $u$ of $G$. If $u$ is the top vertex of a face,
then $u$ is incident to a span-$2$ edge $(u,v)$ with $y(u)>y(v)$. By Invariant
(O.3), $u$ is a successor of $v$ in the recursive approach by Dujmović et al.
[14], i.e., when $u$ is placed in $\Gamma(G)$, vertex $v$ belongs to the upper
envelope. We now claim that $u$ cannot be incident to two edges $(u,v)$ and
$(u,v^{\prime})$ with the properties mentioned above; this claim implies the
lemma. Assuming the contrary, by Invariant (O.2), when $u$ is placed in
$\Gamma(G)$ at most one edge incident to $u$ has span $2$. So, at most one of
$(u,v)$ and $(u,v^{\prime})$ is drawn when $u$ is placed in $\Gamma(G)$, which
implies that at least one of $v$ and $v^{\prime}$, say $v^{\prime}$, is a
successor of $u$. Thus, $y(u)<y(v^{\prime})$ holds; a contradiction.

For (b), assume for a contradiction that $G$ contains a vertex $u$, which is
the side vertex of three triangular faces, say $\mathcal{T}_{1}$,
$\mathcal{T}_{2}$ and $\mathcal{T}_{3}$, of $\Gamma(G)$. For a significantly
small constant $\varepsilon>0$, let $p_{1}=(x(u)-\varepsilon,y(u))$ and
$p_{2}=(x(u)+\varepsilon,y(u))$, and consider the two horizontal rays $r_{1}$
and $r_{2}$ emanating from vertex $u$, such that $r_{1}$ and $r_{2}$ contain
points $p_{1}$ and $p_{2}$, respectively. Since $u$ is side vertex for
$\mathcal{T}_{1}$, $\mathcal{T}_{2}$ and $\mathcal{T}_{3}$, it follows by
Invariant (O.2) that the span-$2$ edge of each of $\mathcal{T}_{1}$,
$\mathcal{T}_{2}$ and $\mathcal{T}_{3}$ crosses either $r_{1}$ or $r_{2}$; by
the choice of $\varepsilon$, we may assume that if a span-$2$ edge of one of
$\mathcal{T}_{1}$, $\mathcal{T}_{2}$ and $\mathcal{T}_{3}$ crosses $r_{1}$
($r_{2}$), then point $p_{1}$ ($p_{2}$, respectively) lies in the interior of
it. On the other hand, by outerplanarity, each of the points $p_{1}$ and
$p_{2}$ can be contained in at most one of $\mathcal{T}_{1}$,
$\mathcal{T}_{2}$ and $\mathcal{T}_{3}$; a contradiction. ∎

###  4.2 Planar 3-trees

To maintain Invariant (T.3), Alam et al. [1] use the algorithm by Dujmović et
al. [14] to assign the level edges of $L_{0},\ldots,L_{\lambda}$ of the input
plane $3$-tree $H$ to two queues ${\mathcal{Q}}_{0}$ and ${\mathcal{Q}}_{1}$,
since on each level these edges induce a (not necessarily connected)
outerplane graph. Unlike in the original algorithm, in our approach we adopt
the modification for the algorithm by Dujmović et al. [14] introduced in
Section 4.1. As Invariants (O.1) and (O.2) are preserved, queues
${\mathcal{Q}}_{0}$ and ${\mathcal{Q}}_{1}$ suffice.

To maintain Invariant (T.4), Alam et al. [1] adopt the following assignment
scheme for the binding edges between $L_{j}$ and $L_{j+1}$ to queues
${\mathcal{Q}}_{2}$, ${\mathcal{Q}}_{3}$ and ${\mathcal{Q}}_{4}$, for each
$j=0,\ldots,\lambda-1$. Consider a binding edge $(u,v)$ with $u\in L_{j}$ and
$v\in L_{j+1}$. Then, vertex $u$ belongs to a connected component $C_{u}$ of
the subgraph $H_{j}$ of $H$ induced by the level-$L_{j}$ vertices, while
vertex $v$ belongs to a connected component $\mathcal{C}_{v}$ of $H_{j+1}$.
Further, $C_{u}$ is outerplane and its $2$-queue layout has been computed by
the algorithm by Dujmović et al. [14], while $C_{v}$ resides in the interior
of a triangular face $\mathcal{T}_{v}$ of $C_{u}$ in the embedding of $H$,
such that $u$ is on the boundary of $\mathcal{T}_{v}$. In the edge-to-queue
assignment scheme by Alam et al. [1], edge $(u,v)$ is assigned to
${\mathcal{Q}}_{2}$, ${\mathcal{Q}}_{3}$ or ${\mathcal{Q}}_{4}$ if and only if
$u$ is the top, middle or bottom vertex of $\mathcal{T}_{v}$, respectively
[1]. For a vertex $u\in L_{j}$ with $j=0,\ldots,\lambda-1$, we denote by
$N_{2}(u)$, $N_{3}(u)$ and $N_{4}(u)$ the neighbors of $u$ in $L_{j+1}$ such
that the edges connecting them to $u$ are assigned to queue
${\mathcal{Q}}_{2}$, ${\mathcal{Q}}_{3}$ and ${\mathcal{Q}}_{4}$,
respectively. The next property follows from Lemma 2.

######  Lemma 3.

For $j=0,\ldots,\lambda-1$, let $u\in L_{j}$ be a vertex of $H$ in our
modification of the peeling-into-levels approach by Alam et al. [1]. Then, the
vertices of $N_{2}(u)$ precede those of $N_{3}(u)$, and the vertices of
$N_{2}(u)$ (or of $N_{3}(u)$) belong to at most two connected components of
$H_{j+1}$ (residing within distinct faces of $H_{j}$).

###### Proof.

The first part of the lemma is proven in [1]. For the second part, consider a
binding edge $(u,v)$ with $v\in N_{2}(u)$; a similar argument applies when
$v\in N_{3}(u)$. Thus, $u$ is the top vertex of the triangular face
$\mathcal{T}_{v}$ of $H_{j}$, in which the connected component $C_{v}$ of
$H_{j+1}$ that contains $v$ resides. Since by Lemma 2(a) vertex $u$ can be the
top vertex of at most two triangular faces of $H_{j}$, there exist at most two
connected components of $H_{j+1}$, to which vertex $v$ can belong. ∎

###  4.3 General Planar Graphs

Dujmović et al. [12] recursively compute the bags (i.e., the tripods) of the
$H$-partition. Each newly discovered tripod $\tau$ is adjacent to at most
three other tripods $\tau_{1}$, $\tau_{2}$ and $\tau_{3}$ already discovered.
We say that $\tau_{1}$, $\tau_{2}$ and $\tau_{3}$ are the parents of $\tau$;
see Fig. 5(a). Also, each non-empty vertical path of $\tau$ is connected to
only one of its parents via an edge of the BFS-tree used to construct the BFS-
layering $\mathcal{L}$ (black in Fig. 5(a)). This property gives rise to at
most three sub-instances (gray in Fig. 5(a)), which are processed recursively
to compute the final tripod decomposition.

Note that, in general, one or more vertical paths of a tripod may have no
vertices; see Fig. 5(b). However, by an appropriate augmentation of the input
graph we can avoid considering this degenerate case explicitly. More
precisely, we first compute a BFS tree $T$ of $G$ rooted at a vertex of the
outer face. We next augment $G$ by adding a triangle $f^{*}$ in the interior
of each face $f$ of $G$. By an appropriate triangulation, we can obtain a
triangulated plane graph $G^{*}$ that contains $G$ as a subgraph, such that
each of the newly introduced vertices of $f^{*}$ can be added as a leaf of $T$
to derive a BFS tree $T^{*}$ of $G^{*}$. In this way, each original face $f$
of $G$ gets three leaves of $T^{*}$ inside it, one attached to each vertex of
$f$. By computing a tripod decomposition of $G$ using the tree $T$, one
obtains a collection of tripods. Each of these tripods has a “base”, which is
a triangular face $f$ of $G$. We produce a tripod decomposition of $G^{*}$
with respect to $T^{*}$ by extending each tripod with base $f$ so that its
base is $f^{*}$. In this way, we derive a tripod decomposition of $G^{*}$, in
which every tripod has three non-empty vertical paths, as desired. Hence,
without loss of generality, we assume in the following that in the tripod
decomposition no vertical path of a tripod is empty.

For $i\in\\{1,2,3\\}$, let $p_{i}^{1}$, $p_{i}^{2}$ and $p_{i}^{3}$ be the
three vertical paths of tripod $\tau_{i}$. Up to renaming, we assume that
$\tau$ lies in the cycle bounded by (parts of) $p_{1}^{1}$, $p_{1}^{2}$,
$p_{2}^{1}$, $p_{2}^{2}$, $p_{3}^{1}$ and $p_{3}^{2}$ as in Fig. 5(a). The
next properties follow by planarity and the BFS-layering:

(a) $\tau$ shares no vertex with $\tau_{1}$, $\tau_{2}$, $\tau_{3}$

(b) $\tau$ shares a vertex with $\tau_{3}$

(c)

Figure 5:  (a), (b) Tripod $\tau$ with parents $\tau_{1}$, $\tau_{2}$ and
$\tau_{3}$. (c) Illustration for (P.6) and (P.8).

  1. (P.6)

There is no edge connecting a vertex of $\tau$ to a vertex of $p_{i}^{3}$ for
$i=1,2,3$; see the dotted edge in Fig. 5(c).

  2. (P.7)

Let $v_{i}^{p}$ be the vertex of vertical path $p$ of $\tau$ on layer $V_{i}$
of $\mathcal{L}$. For two vertical paths $p$ and $q$ of $\tau$, edge
$(v_{i}^{p},v_{j}^{q})$ belongs to $G$ only if $|i-j|\leq 1$.

  3. (P.8)

For vertical paths $p$ and $q$ of $\tau$, at most one of the edges
$(v_{i}^{p},v_{i+1}^{q})$ and $(v_{i+1}^{p},v_{i}^{q})$ exists in $G$; see the
dashed edges of Fig. 5(c).

Note that (P.6)–(P.8) hold even if $\tau$ has less than three parents, or if
the cycle bounding the region of $\tau$ does not contain two vertical paths of
each parent tripod.

In the original algorithm by Dujmović et al. [12], each vertex $v_{\tau}$ in
$H$ corresponds to a tripod $\tau$ in $G$, and an edge
$(v_{\tau},v_{\tau^{\prime}})$ exists in $H$, if $\tau$ is a parent of
$\tau^{\prime}$ in $G$, or vice versa. Also, $H$ is a connected partial planar
$3$-tree, which is arbitrarily augmented to a maximal planar $3$-tree
$H^{\prime}$ (to compute a 5-queue layout of it). Here, we adopt a particular
augmentation to guarantee an additional property for the graph $H^{\prime}$
(see Lemma 4). Similarly to the original approach, we contract the vertices of
each tripod $\tau$ of $G$ to a single vertex $v_{\tau}$. However, in our
modification, we keep self-loops that occur when an edge of $G$ has both
endpoints in $\tau$ (unless this edge belongs to one of its vertical paths),
as well as, parallel edges that occur when two vertices of $\tau$ have a
common neighbor not in $\tau$. Two important properties of this contraction
scheme that follow directly from planarity are given below; see Fig. 6.

  1. (P.9)

The edges around each contracted vertex $v_{\tau}$ appear in the same
clockwise cyclic order as they appear in a clockwise traversal along $\tau$ in
$G$.

  2. (P.10)

The edges having at least one endpoint on the same vertical path of $\tau$
appear consecutively around $v_{\tau}$; see Fig. 6(b).

(a)

(b)

Figure 6:  (a) A tripod $\tau$ in $G$ where the edges incident to its three
vertical paths are drawn dotted, and (b) the result after contracting $\tau$
to $v_{\tau}$.

To guarantee simplicity, we focus on homotopic self-loops and pairs of
parallel edges, which contain no vertex either in the interior or in the
exterior region that they define. We remove such self-loops and keep one copy
of such parallel edges. Then, we subdivide each self-loop twice, and for each
edge with multiplicity $m>1$, we subdivide all but one of its copies. In this
way, each vertex $v_{\tau}$ corresponding to a tripod $\tau$ in $G$ always
lies in the interior of a separating $3$-cycle $C$ that contains all the
vertices corresponding to its parent tripods on its boundary. To see this,
observe that if $\tau$ has three parent $\tau_{1}$, $\tau_{2}$ and $\tau_{3}$,
then $C$ is formed by $v_{\tau_{1}}$, $v_{\tau_{2}}$ and $v_{\tau_{3}}$, such
that $v_{\tau}$ is connected to each of them. If $\tau$ has two parent
$\tau_{1}$ and $\tau_{2}$, then $C$ is formed by $v_{\tau_{1}}$,
$v_{\tau_{2}}$ and a subdivision vertex, such that $v_{\tau}$ is connected to
$v_{\tau_{1}}$ and $v_{\tau_{2}}$. Finally, if $\tau$ has only one parent
$\tau_{1}$, then $C$ is formed by $v_{\tau_{1}}$ and two subdivision vertices,
such that $v_{\tau}$ is connected to $v_{\tau_{1}}$. Since subdivision
vertices are of degree $2$, the result is a simple (possibly not maximal)
planar 3-tree, which is a supergraph of $H$. To derive $H^{\prime}$, we
augment it to maximal by adding edges, while maintaining its embedding [20].

######  Lemma 4.

Let $v_{\tau}$ and $v_{\tau_{p}}$ be two vertices of $H^{\prime}$ that
correspond to a tripod $\tau$ and to a parent tripod $\tau_{p}$ of $\tau$ in
$G$. If $L_{i}$ and $L_{j}$ are the levels of $v_{\tau}$ and $v_{\tau_{p}}$ in
the peeling-into-levels approach for $H^{\prime}$, then $i\geq j$.

###### Proof.

Let $C$ be the inclusion-minimal separating $3$-cycle of $H^{\prime}$
containing $v_{\tau}$ in its interior and all vertices that correspond to the
parent tripods of $\tau$ on its boundary. Let $L_{k}$, $L_{l}$ and $L_{m}$ be
the levels of the three vertices of $C$, with $k\leq l\leq m$, in the peeling-
into-levels approach for $H^{\prime}$. As $\tau_{p}$ is a parent of $\tau$,
$j\in\\{k,l,m\\}$ holds. Since $C$ is a $3$-cycle and since each edge in the
peeling-into-level approach is either level or binding, $m\leq k+1$ holds. The
fact that $v_{\tau}$ lies in the interior of $C$ and is connected to each of
the vertices in $H^{\prime}$ corresponding to its parent tripods in $G$,
implies that $v_{\tau}$ is on level $L_{k+1}$, i.e., $i=k+1$. So, $j\leq m\leq
k+1=i$ holds. ∎

As in the original algorithm by Dujmović et al. [12], we compute a $5$-queue
layout $\mathit{QL}(H^{\prime})$ of $H^{\prime}$. However, we use our
modification of the algorithm by Alam et al. [1] described in Section 4.2.
Denote by $x_{1},\dots,x_{h}$ the vertices of the subgraph $H$ of $H^{\prime}$
as they appear in $\mathit{QL}(H^{\prime})$ (i.e., we ignore subdivision
vertices introduced when augmenting $H$ to $H^{\prime}$) and by
${\mathcal{Q}}_{0},\ldots,{\mathcal{Q}}_{4}$ the queues of
$\mathit{QL}(H^{\prime})$ as described in Invariants (T.1)–(T.4). To compute
the linear layout $\mathit{QL}(G)$ of $G$, we use Lemma 1, which orders the
vertices of each layer $V_{i}$, with $i\geq 0$, of $\mathcal{L}$ as:

$\overrightarrow{V_{i}}=A_{x_{1}}\cap V_{i},A_{x_{2}}\cap
V_{i},\dots,A_{x_{h}}\cap V_{i},$

where $A_{x_{1}},\ldots,A_{x_{h}}$ are the bags (i.e., the tripods) of the
$H$-partition of $G$. Unlike in the original algorithm, we do not order the
vertices in each subset $A_{x_{j}}\cap V_{i}$, with $j\in\\{1,\ldots,h\\}$,
arbitrarily. Instead, we carefully choose their order; we describe this choice
in the rest of this section. Let $\tau$ be the tripod of bag $A_{x_{j}}$.
Then, $A_{x_{j}}\cap V_{i}$ contains at most one vertex of each vertical path
of $\tau$. We will order the three vertical paths of $\tau$, which defines the
order of the (at most three) vertices of $A_{x_{j}}\cap V_{i}$ for every
$i\geq 0$.

Let $L_{l}$ be the level of $v_{\tau}$ in the peeling-into-levels of
$H^{\prime}$, with $0\leq l<\lambda$. By Lemma 3, there are at most four
connected components $c_{s}^{1}$, $c_{s}^{2}$, $c_{t}^{1}$ and $c_{t}^{2}$ of
the subgraph $H_{l+1}^{\prime}$ of $H^{\prime}$ induced by the vertices of
$L_{l+1}$, such that the edges connecting $v_{\tau}$ to vertices of
$c_{s}^{1}$ and $c_{s}^{2}$ ($c_{t}^{1}$ and $c_{t}^{2}$) belong to
${\mathcal{Q}}_{2}$ (${\mathcal{Q}}_{3}$, respectively). Let $c$ be one of
$c_{s}^{1}$, $c_{s}^{2}$, $c_{t}^{1}$ and $c_{t}^{2}$; $c$ may contain
vertices that correspond to tripods in $G$ (i.e., not to subdivisions
introduced while augmenting $H$ to $H^{\prime}$). We refer to the union of
these vertices of $G$ as the tripod-vertices of $c$. By Invariant (T.1),
$v_{\tau}$ precedes the vertices of $c_{s}^{1}$, $c_{s}^{2}$, $c_{t}^{1}$ and
$c_{t}^{2}$ in $\mathit{QL}(H^{\prime})$. Also by (T.2), we may assume that
the vertices of $c_{s}^{1}$ ($c_{t}^{1}$) precede those of $c_{s}^{2}$
($c_{t}^{2}$, respectively). Additionally, Lemma 3 ensures that the vertices
of $c_{s}^{2}$ precede those of $c_{t}^{1}$.

Since an edge $(v_{\tau},v_{\tau^{\prime}})$ exists in $H$, if $\tau$ is a
parent of $\tau^{\prime}$, or vice versa, by Lemma 4, for each vertex
$v_{\tau^{\prime}}$ of $H$ that is a neighbor of $v_{\tau}$ in one of
$c_{s}^{1}$, $c_{s}^{2}$, $c_{t}^{1}$ and $c_{t}^{2}$, it follows that $\tau$
is a parent of $\tau^{\prime}$. By Property (P.6), there is a vertical path of
$\tau$ in $G$, say $p$ ($q$), such that no tripod-vertex of $c_{s}^{2}$
($c_{t}^{2}$, respectively) is adjacent to it in $G$. Note that $p$ and $q$
might be the same vertical path of $\tau$.

We now describe the order of the three vertical paths of $\tau$. We only
specify the first one; the other two can be arbitrarily ordered:  (i) if the
tripod-vertices of $c_{s}^{1}$ and $c_{s}^{2}$ are connected to all three
vertical paths of $\tau$ in $G$, then $p$ is the first vertical path of
$\tau$;  (ii) if the tripod-vertices of $c_{t}^{1}$ and $c_{t}^{2}$ are
connected to all three vertical paths of $\tau$ in $G$, then $q$ is the first
vertical path of $\tau$;  (iii) otherwise, any vertical path of $\tau$ can be
first.  Before proving formally that Cases (i) and (ii) cannot apply
simultaneously (which implies that the order of the vertical paths of $\tau$
is well defined), we state two important implications of the described choice
for the first vertical path of $\tau$.

  1. (P.11)

Under our assumption that all vertices of $c_{s}^{1}$ precede those of
$c_{s}^{2}$, if tripod-vertices of $c_{s}^{1}$ and $c_{s}^{2}$ are connected
to all three vertical paths of $\tau$, then tripod-vertices of $c_{s}^{2}$ are
not connected to the first vertical path of $\tau$.

  2. (P.12)

Also, under our assumption that all vertices of $c_{t}^{1}$ precede those of
$c_{t}^{2}$, if tripod-vertices of $c_{t}^{1}$ and $c_{t}^{2}$ are connected
to all three vertical paths of $\tau$, then tripod-vertices of $c_{t}^{2}$ are
not connected to the first vertical path of $\tau$.

(a)

(b)

(c)

Figure 7:  Illustrations for: (a)-(b) the fact that Cases (i) and (ii) in the
selection of the first vertical path of $\tau$ cannot apply simultaneously,
and (c) the proof of Lemma 5.

We now prove that Cases (i) and (ii) in the selection of the first vertical
path of $\tau$ cannot apply simultaneously. Assume for a contradiction that
the tripod-vertices of $c_{s}^{1}$ and $c_{s}^{2}$ are connected to all three
vertical paths of $\tau$, and also that the tripod-vertices of $c_{t}^{1}$ and
$c_{t}^{2}$ are connected to all three vertical paths of $\tau$. Since
$v_{\tau}$ is the top vertex of the two triangular faces $f_{t}^{1}$ and
$f_{t}^{2}$ that contain $c_{t}^{1}$ and $c_{t}^{2}$ in their interior in
$\Gamma(H^{\prime}_{l})$, it follows that the edges connecting $v_{\tau}$ to
$c_{t}^{1}$ and $c_{t}^{2}$ appear consecutively around $v_{\tau}$ in the
cyclic order of the binding edges between levels $L_{l}$ and $L_{l+1}$ of
$H^{\prime}$; refer to the blue edges of Fig. 7(a). Also, since $v_{\tau}$ is
the side vertex of the two triangular faces $f_{s}^{1}$ and $f_{s}^{2}$ that
contain $c_{s}^{1}$ and $c_{s}^{2}$ in their interior in
$\Gamma(H^{\prime}_{l})$, we may assume w.l.o.g. that the edges connecting
$v_{\tau}$ to $c_{s}^{1}$ immediately precede the edges connecting $v_{\tau}$
to $c_{t}^{1}$ and $c_{t}^{2}$, while the edges connecting $v_{\tau}$ to
$c_{s}^{2}$ immediately follow them; refer to the green edges of Fig. 7(a)
(note that since we have assumed that the vertices of $c_{s}^{1}$ precede the
vertices of $c_{s}^{2}$, our assumption on the order of the edges around
$v_{\tau}$ is a property of the algorithm by Alam et al. [1]). Now, if the
tripod-vertices of $c_{s}^{1}$ and $c_{s}^{2}$ are connected to all three
vertical paths of $\tau$, and the same holds for the tripod-vertices of
$c_{t}^{1}$ and $c_{t}^{2}$, then Property (P.10) implies that in $G$ the
edges connecting vertices of $\tau$ to tripod-vertices of $c_{t}^{1}$ and
$c_{t}^{2}$ alternate with edges connecting vertices of $\tau$ to tripod-
vertices of $c_{s}^{1}$ and $c_{s}^{2}$; see e.g. Fig. 7(b). Hence, the cyclic
order of the edges around $v_{\tau}$ in $H^{\prime}$ is not the same as the
cyclic order of the edges incident to vertices of $\tau$ along a clockwise
traversal of $\tau$ in $G$, contradicting Property (P.9). Hence, Case (i) and
(ii) cannot apply simultaneously, as we initially claimed.

##  5 Reducing the bound

To reduce the bound, we turn our attention to the analysis of the required
number of queues for the intra-bag inter-layer edges (E.2), as well as for the
inter-bag edges (i.e., either intra-layer (E.3) or inter-layer (E.4)–(E.5))
given by Dujmović et al. [12]; refer to Section 3.3. For intra-bag inter-layer
edges (E.2), the original algorithm by Dujmović et al. [12] uses three queues,
since $\ell=3$; see blue edges in Fig. 4(a). We prove that no three intra-bag
inter-layer edges form a $3$-rainbow, implying that the upper bound on the
queue number of planar graphs can be improved from $49$ to $48$.

######  Lemma 5.

In the queue layout computed by our modification of the algorithm by Dujmović
et al. [12], no three intra-bag inter-layer edges of $G$ form a $3$-rainbow.

###### Proof.

Assume to the contrary that there exist three such edges $(u_{1},v_{1})$,
$(u_{2},v_{2})$ and $(u_{3},v_{3})$ forming a $3$-rainbow in $\mathit{QL}(G)$
so that
$u_{1}\prec_{G}u_{2}\prec_{G}u_{3}\prec_{G}v_{3}\prec_{G}v_{2}\prec_{G}v_{1}$.
By (P.1) these edges belong to the same bag $A$ of the $H$-partition, while by
(P.2) their endpoints belong to two consecutive layers $V_{i}$ and $V_{i+1}$
of $\mathcal{L}$. Due to the order, $u_{1},u_{2},u_{3}\in V_{i}$ and
$v_{1},v_{2},v_{3}\in V_{i+1}$. The order of $A\cap V_{i}$ and $A\cap V_{i+1}$
is $u_{1}\prec_{G}u_{2}\prec_{G}u_{3}$ and
$v_{3}\prec_{G}v_{2}\prec_{G}v_{1}$; see Fig. 7(c). Let $p_{1}$, $p_{2}$ and
$p_{3}$ be the first, second and third vertical paths of tripod $\tau$ forming
$A$. Then, $(u_{1},v_{3})\in p_{1}$, $(u_{2},v_{2})\in p_{2}$ and
$(u_{3},v_{1})\in p_{3}$. However, $(u_{1},v_{1})$ and $(u_{3},v_{3})$
contradict (P.8). ∎

For inter-bag edges (E.3)–(E.5), the algorithm by Dujmović et al. [12] uses
$3\cdot 15$ queues, since $k=5$ and $\ell=3$; see green, purple and orange
edges in Fig. 4(b). We exploit (P.3) to prove that $3\cdot 13$ queues suffice.
This further improves the upper bound on the queue number of planar graphs
from $48$ to $42$.

######  Lemma 6.

In the queue layout computed by our modification of the algorithm by Dujmović
et al. [12], the inter-bag edges of $G$ do not form a $40$-rainbow.

###### Proof.

To prove the statement, it suffices to show that the inter-bag edges of $G$
that belong to each of (E.3)–(E.5) form at most a $13$-rainbow. We focus on
the edges of (E.3), that is, on the intra-layer inter-bag edges of $G$; the
other two types of edges, i.e., forward and backward inter-layer inter-bag
edges, can be treated similarly. We partition the edges of (E.3) into five
subsets $E_{3}^{0},\ldots,E_{3}^{4}$, such that for $i=0,\ldots,4$, set
$E_{3}^{i}$ contains the following subset of (E.3)-edges of $G$:

$E_{3}^{i}=\\{(u,v)\in\mbox{\ref{e:out_b_in_l}}:u\in A_{x},v\in
A_{y},(x,y)\in{\mathcal{Q}}_{i}\\}.$

By Property (P.3), the edges of $E_{3}^{i}$ can form at most a $3$-rainbow
(this property actually implies the initial bound of $15$ queues for all
intra-layer inter-bag edges of $G$ by Dujmović et al. [12]). We next prove
that neither the edges of $E_{3}^{2}$ nor the edges of $E_{3}^{3}$ form a
$3$-rainbow, which yields the desired reduction from $15$ to $13$ on the size
of the maximum rainbow formed by the edges of (E.3). Assume that this is not
true, say for the edges of $E_{3}^{2}$; a symmetric argument applies for the
edges of $E_{3}^{3}$. Let $(u_{1},v_{1})$, $(u_{2},v_{2})$ and $(u_{3},v_{3})$
be three edge of $E_{3}^{2}$ that form a $3$-rainbow, such that
$u_{1}\prec_{G}u_{2}\prec_{G}u_{3}\prec_{G}v_{3}\prec_{G}v_{2}\prec_{G}v_{1}$.
Since $(u_{1},v_{1})$, $(u_{2},v_{2})$ and $(u_{3},v_{3})$ are (E.3)-edges,
i.e., intra-layer edges, their endpoints $u_{1}$, $u_{2}$, $u_{3}$, $v_{1}$,
$v_{2}$ and $v_{3}$ all belong to the same layer of the BFS-layering of
$G$555Note that if we had assumed that $(u_{1},v_{1})$, $(u_{2},v_{2})$ and
$(u_{3},v_{3})$ belonged to one of (E.4) or (E.5), i.e., inter-layer edges,
vertices $u_{1}$, $u_{2}$ and $u_{3}$ would all belong to one layer, while
vertices $v_{1}$, $v_{2}$ and $v_{3}$ would belong to the next layer. In what
follows, we will only use the fact that vertices $u_{1}$, $u_{2}$ and $u_{3}$
belong to the same layer and that vertices $v_{1}$, $v_{2}$ and $v_{3}$ belong
to the same layer, without discriminating whether the two layers are the same
or not.. Assuming that $u_{i}\in A_{x_{i}}$ and $v_{i}\in A_{y_{i}}$, it
follows that $(x_{i},y_{i})$ is an edge of $H$ assigned to ${\mathcal{Q}}_{2}$
and $x_{i}\prec_{H}y_{i}$. By Property (P.3), either $x_{1}=x_{2}=x_{3}$ or
$y_{1}=y_{2}=y_{3}$ holds. First, we prove that $x_{1}=x_{2}=x_{3}$ always
holds. Assume for a contradiction that, w.l.o.g., $x_{1}\neq x_{2}$. Then,
$y=y_{1}=y_{2}=y_{3}$ holds. Since the edges of ${\mathcal{Q}}_{2}$ are
binding in the peeling-into-levels decomposition of $H^{\prime}$ and since
$x_{1}\prec_{H}x_{2}\prec_{H}y$, vertices $x_{1}$ and $x_{2}$ belong to level
$L_{j}$ of $H^{\prime}$, while $y$ belongs to level $L_{j+1}$, for some $0\leq
j<\lambda$. By Property (T.4), $y$ has only one neighbor on level $L_{j}$ such
that the edge connecting $y$ to this neighbor is assigned to
${\mathcal{Q}}_{2}$. This contradicts the fact that both edges $(x_{1},y)$ and
$(x_{2},y)$ are assigned to ${\mathcal{Q}}_{2}$, since $x_{1}\neq x_{2}$.
Hence $x=x_{1}=x_{2}=x_{3}$ holds.

Now, since the edges of ${\mathcal{Q}}_{2}$ are binding in the peeling-into-
levels decomposition of $H^{\prime}$, and since, for $i=1,2,3$ ,
$x\prec_{H}y_{i}$, it follows that vertex $x$ belongs to level $L_{j}$ of
$H^{\prime}$, while vertex $y_{i}$ belongs to level $L_{j+1}$, for some $0\leq
j<\lambda$. Let $\tau$ be the tripod of bag $A_{x}$ and let $\tau_{1}$,
$\tau_{2}$, $\tau_{3}$ be the tripods of $A_{y_{1}}$, $A_{y_{2}}$ and
$A_{y_{3}}$, respectively. Note that vertices $y_{1}$, $y_{2}$ and $y_{3}$ are
not necessarily distinct, that is, the corresponding tripods $\tau_{1}$,
$\tau_{2}$ and $\tau_{3}$ are not necessarily pairwise different. However,
since $u_{1}\prec_{G}u_{2}\prec_{G}u_{3}$, and since $u_{1}$, $u_{2}$ and
$u_{3}$ belong to the same layer in the BFS-layering $\mathcal{L}$ of $G$, we
can conclude that $u_{1}$, $u_{2}$ and $u_{3}$ belong to $p_{1}$, $p_{2}$ and
$p_{3}$, respectively, where $p_{1}$, $p_{2}$ and $p_{3}$ are the first,
second and third vertical paths of $\tau$. Since, for $i=1,2,3$, the edge
$(x,y_{i})$ belongs to $H$, it follows that $\tau$ is a parent tripod of
$\tau_{i}$ or vice versa. Since $x$ belongs to level $L_{j}$ of $H^{\prime}$
and vertices $y_{1}$, $y_{2}$ and $y_{3}$ belong to level $L_{j+1}$, by Lemma
4 we conclude that $\tau$ is a parent tripod of $\tau_{1}$, $\tau_{2}$ and
$\tau_{3}$. By Lemma 3, there exist at most two connected components
$c_{s}^{1}$ and $c_{s}^{2}$ of $H^{\prime}_{j+1}$, such that the edges
connecting $x$ to vertices of $c_{s}^{1}$ and $c_{s}^{2}$ have been assigned
to ${\mathcal{Q}}_{2}$. W.l.o.g, by Invariant (T.2) we assume that all
vertices of $c_{s}^{1}$ (if any) precede those of $c_{s}^{2}$ (if any).

We first argue that not all vertices $y_{1}$, $y_{2}$ and $y_{3}$ belong to
only one of $c_{s}^{1}$ or $c_{s}^{2}$, which further implies that both
components $c_{s}^{1}$ and $c_{s}^{2}$ exist. Assume to the contrary that
$y_{1}$, $y_{2}$ and $y_{3}$ belong to $c_{s}^{1}$; a similar argument applies
for $c_{s}^{2}$. By Property (P.6), tripod-vertices of component $c_{s}^{1}$
are not adjacent to the vertices of at least one vertical path of $\tau$ in
$G$, say $p_{3}$. In this case, however, we obtain a contradiction to the fact
that $v_{3}$, which is a tripod-vertex of $c_{s}^{1}$, is connect to $u_{3}$
that belongs to $p_{3}$, i.e., edge $(u_{3},v_{3})$ cannot exist in $G$.

Hence, not all vertices $y_{1}$, $y_{2}$ and $y_{3}$ belong to only one of
$c_{s}^{1}$ or $c_{s}^{2}$, as we initially claimed. In particular, since
$y_{3}\preceq_{H}y_{2}\preceq_{H}y_{1}$ and since all vertices of $c_{s}^{1}$
precede those of $c_{s}^{2}$, it follows that $y_{3}$ belongs to $c_{s}^{1}$,
while $y_{1}$ belongs to $c_{s}^{2}$. Since $u_{1}$, $u_{2}$ and $u_{3}$
belong to $p_{1}$, $p_{2}$ and $p_{3}$, respectively, the vertices of
$c_{s}^{1}$ and $c_{s}^{2}$ are connected to all vertical paths of $\tau$.
Thus, Property (P.11) applies, which implies that the tripod-vertices of
$c_{s}^{2}$ (including $v_{1}$) are not connected to the first vertical path
$p_{1}$ of $\tau$, which is a contradiction to the fact that $(u_{1},v_{1})$
is an edge of $G$, since $u_{1}\in p_{1}$. Hence, the edges of $E_{3}^{2}$
cannot form a $3$-rainbow. Symmetrically, we can prove that the edges of
$E_{3}^{3}$ cannot form a $3$-rainbow, which completes the proof of the lemma.
∎

We are now ready to state the main theorem of this section.

######  Theorem 5.1.

Every planar graph has queue number at most $42$.

##  6 Conclusions

In this work, we improved the upper bound on the queue number of planar graphs
by refining the three techniques involved in the original algorithm [12]. We
believe that our approach has the potential to further reduce the upper bound
by at least $3$ (i.e., from $42$ to $39$). However, more elaborate arguments
that exploit deeper the planarity of the graph are required, and several
details need to be worked out. Still the gap with the lower bound of $4$
remains large and needs to be further reduced. In this regard, determining the
exact queue number of planar 3-trees becomes critical, since an improvement of
the current upper bound of $5$ (to meet the lower bound of $4$) directly
implies a corresponding improvement on the upper bound on the queue number of
general planar graphs. On the other hand, to obtain a better understanding of
the general open problem, it is also reasonable to further examine subclasses
of planar graphs, such as bipartite planar graphs or planar graphs with
bounded degree (e.g., max-degree 3).

## References

  * [1] Alam, J.M., Bekos, M.A., Gronemann, M., Kaufmann, M., Pupyrev, S.: Queue layouts of planar 3-trees. Algorithmica 82(9), 2564–2585 (2020), https://doi.org/10.1007/s00453-020-00697-4
  * [2] Bannister, M.J., Devanny, W.E., Dujmovic, V., Eppstein, D., Wood, D.R.: Track layouts, layered path decompositions, and leveled planarity. Algorithmica 81(4), 1561–1583 (2019), https://doi.org/10.1007/s00453-018-0487-5
  * [3] Barth, D., Pellegrini, F., Raspaud, A., Roman, J.: On bandwidth, cutwidth, and quotient graphs. RAIRO Theor. Informatics Appl. 29(6), 487–508 (1995), https://doi.org/10.1051/ita/1995290604871
  * [4] Bekos, M.A., Förster, H., Gronemann, M., Mchedlidze, T., Montecchiani, F., Raftopoulou, C.N., Ueckerdt, T.: Planar graphs of bounded degree have bounded queue number. SIAM J. Comput. 48(5), 1487–1502 (2019), https://doi.org/10.1137/19M125340X
  * [5] Bekos, M.A., Kaufmann, M., Klute, F., Pupyrev, S., Raftopoulou, C.N., Ueckerdt, T.: Four pages are indeed necessary for planar graphs. J. Comput. Geom. 11(1), 332–353 (2020), https://journals.carleton.ca/jocg/index.php/jocg/article/view/504
  * [6] Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory, Ser. B 27(3), 320–331 (1979), https://doi.org/10.1016/0095-8956(79)90021-2
  * [7] Chinn, P.Z., Chvatalova, J., Dewdney, A.K., Gibbs, N.E.: The bandwidth problem for graphs and matrices - a survey. J. Graph Theory 6(3), 223–254 (1982), https://doi.org/10.1002/jgt.3190060302
  * [8] Di Battista, G., Frati, F., Pach, J.: On the queue number of planar graphs. SIAM J. Comput. 42(6), 2243–2285 (2013), https://doi.org/10.1137/130908051
  * [9] Díaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002), https://doi.org/10.1145/568522.568523
  * [10] Dujmović, V., Frati, F.: Stack and queue layouts via layered separators. J. Graph Algorithms Appl. 22(1), 89–99 (2018), https://doi.org/10.7155/jgaa.00454
  * [11] Dujmović, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. In: Zuckerman, D. (ed.) FOCS. pp. 862–875. IEEE Computer Society (2019), https://doi.org/10.1109/FOCS.2019.00056
  * [12] Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. J. ACM 67(4), 22:1–22:38 (2020), https://dl.acm.org/doi/10.1145/3385731
  * [13] Dujmović, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. Comput. 34(3), 553–579 (2005), https://doi.org/10.1137/S0097539702416141
  * [14] Dujmović, V., Pór, A., Wood, D.R.: Track layouts of graphs. Discrete Mathematics & Theoretical Computer Science 6(2), 497–522 (2004), http://dmtcs.episciences.org/315
  * [15] Dujmović, V., Wood, D.R.: On linear layouts of graphs. Discrete Mathematics & Theoretical Computer Science 6(2), 339–358 (2004), http://dmtcs.episciences.org/317
  * [16] Heath, L.S.: Embedding planar graphs in seven pages. In: FOCS. pp. 74–83. IEEE Computer Society (1984), https://doi.org/10.1109/SFCS.1984.715903
  * [17] Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398–412 (1992), https://doi.org/10.1137/0405031
  * [18] Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927–958 (1992), https://doi.org/10.1137/0221055
  * [19] Horton, S.B., Parker, R.G., Borie, R.B.: On minimum cuts and the linear arrangement problem. Discret. Appl. Math. 103(1-3), 127–139 (2000), https://doi.org/10.1016/S0166-218X(00)00173-6
  * [20] Kratochvíl, J., Vaner, M.: A note on planar partial 3-trees. CoRR abs/1210.8113 (2012), http://arxiv.org/abs/1210.8113
  * [21] Wiechert, V.: On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), P1.65 (2017), http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p65
  * [22] Wood, D.R.: Queue layouts, tree-width, and three-dimensional graph drawing. In: Agrawal, M., Seth, A. (eds.) FST TCS. LNCS, vol. 2556, pp. 348–359. Springer (2002), https://doi.org/10.1007/3-540-36206-1_31
  * [23] Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36–67 (1989), https://doi.org/10.1016/0022-0000(89)90032-9