#  Approximate Realizations for
Outerplanaric Degree Sequences††thanks: This work was supported by US-Israel
BSF grant no. 2022205.

Amotz Bar-Noy
<EMAIL_ADDRESS>The Graduate Center of the City University of New
York, NY 10016, USA.  Toni Böhnlein
<EMAIL_ADDRESS>Huawei, Zurich, Switzerland. David Peleg
<EMAIL_ADDRESS>Department of Computer Science and Applied
Mathematics, The Weizmann Institute of Science, Rehovot 76100, Israel. Yingli
Ran44footnotemark: 4
<EMAIL_ADDRESS>Dror Rawitz
<EMAIL_ADDRESS>Faculty of Engineering, Bar Ilan University, Ramt-Gan
52900, Israel

###### Abstract

We study the question of whether a sequence $d=(d_{1},d_{2},\ldots,d_{n})$ of
positive integers is the degree sequence of some outerplanar (a.k.a. 1-page
book embeddable) graph $G$. If so, $G$ is an outerplanar realization of $d$
and $d$ is an outerplanaric sequence. The case where $\sum d\leq 2n-2$ is
easy, as $d$ has a realization by a forest (which is trivially an outerplanar
graph). In this paper, we consider the family $\mathcal{D}$ of all sequences
$d$ of even sum $2n\leq\sum d\leq 4n-6-2\omega_{1}$, where $\omega_{x}$ is the
number of $x$’s in $d$. (The second inequality is a necessary condition for a
sequence $d$ with $\sum d\geq 2n$ to be outerplanaric.) We partition
$\mathcal{D}$ into two disjoint subfamilies,
$\mathcal{D}=\mathcal{D}_{NOP}\cup\mathcal{D}_{2PBE}$, such that every
sequence in $\mathcal{D}_{NOP}$ is provably non-outerplanaric, and every
sequence in $\mathcal{D}_{2PBE}$ is given a realizing graph $G$ enjoying a
2-page book embedding (and moreover, one of the pages is also bipartite).

##  1 Introduction

#### Background.

Our study is concerned with degree sequences of graphs. The degree of a vertex
in a graph $G$ is the number of its incident edges, and the sequence of vertex
degrees of $G$ is denoted by $\deg(G)$. Studied for more than 60 years, the
Degree Realization problem requires to decide, given a sequence $d$ of
positive integers, whether $d$ has a _realizing graph_ , namely, a graph $G$
such that $\deg(G)=d$, and to find such a graph if exists. A sequence $d$ that
has a realizing graph is called _graphic_. One of the first characterizations
of all graphic degree sequences was given by Erdös and Gallai [6]. About the
same time, Havel and Hakimi [10, 11] described an algorithm that, given a
sequence $d$, generates a realization if $d$ is graphic or verifies that $d$
is not graphic. Other studies focused on the uniqueness of the realization. It
is known that a sequence can have several non-isomorphic realizations. As an
example, consider the sequence111We use the shorthand $a^{k}$ to denote a
subsequence of $k$ consecutive $a$’s. $(2^{6})$, which can be realized by a
6-vertex cycle or by two 3-vertex cycles. This issue is not of our concern in
the current paper.

The realization problem has also been investigated for various well known
classes of graphs. In particular, realization by planar graphs was considered
in several papers, but currently a complete solution seems out of reach. The
survey by Rao [18] listed a number of partial results and studies on related
questions. In this paper, we address the question whether a given sequence has
an _outerplanar_ realization. Outerplanar graphs are planar graphs that can be
embedded in the plane so that edges do not intersect each other and
additionally, each vertex lies on the outer face (i.e., no vertex is
surrounded by edges) [21].

A sequence $d\in\mathcal{D}$ is _outerplanaric_ if it has a realizing
outerplanar graph. Similarly, a sequence $d\in\mathcal{D}$ is _maximal
outerplanaric (MOP)_ if it has a realizing _maximal_ outerplanar graph
(namely, an outerplanar graph with the property that adding any edge to it
violates outerplanarity).

Throughout, we denote by $d=(d_{1},d_{2},\ldots,d_{n})$ a nonincreasing
sequence of $n$ positive integers and denote its _volume_ by $\sum
d=\sum_{i=1}^{n}d_{i}$. We use the shorthand $a^{k}$ to denote a subsequence
of $k$ consecutive integers $a$, and denote the multiplicity of degree $x$ in
a sequence $d$ by $\omega_{x}$. By the well-known Handshaking Lemma, $\sum d$
is even for every graphic sequence $d$. If $\sum d\leq 2n-2$ and $\sum d$ is
even, then $d$ has a forest realization with $(2n-\sum_{i}d_{i})/2$ components
[9]. Therefore, we focus on $d$ with $\sum d\geq 2n$. We show later (Lemma 4)
that if $d$ is outerplanaric but not forestic (i.e., $\sum d>2n-2$), then also
$\sum d\leq 4n-6-2\omega_{1}$, and moreover, $\sum d=4n-6$ if and only if $d$
is maximal outerplanaric. Consequently, we focus on the family of
nonincreasing sequences of $n$ positive integers

$\mathcal{D}~{}=~{}\left\\{d=(d_{1},\ldots,d_{n})~{}\mid~{}\sum d~{}\mbox{is
even and}~{}2n\leq\sum d\leq 4n-6-2\omega_{1}\right\\}.$

Let $\mathcal{D}_{\leq 4}\subseteq\mathcal{D}$ be the subclass of sequences
whose largest degree satisfies $d_{1}\leq 4$.

While we are unable to fully characterize the sequences of the family
$\mathcal{D}$ with respect to outerplanarity, we obtain a classification
result that can be thought of as an “approximate” solution to the
outerplanarity problem. To do that, we employ the concept of _book embeddings_
which is used in graph theory to measure how far a graph is _away_ from being
outerplanar. Given a graph $G=(V,E)$, let $E=E_{1}\cup\ldots\cup E_{p}$ be a
partition of its edges such that each subgraph $G_{i}=(V,E_{i})$ is
outerplanar. For a book embedding of $G$, think of a book in which the pages
(half-planes) are filled by outerplanar embeddings of the $G_{i}$’s such that
the vertices are embedded on the spine of the book and in the same location on
each page. This constraint is equivalent to requiring that the vertices appear
in the same order along the cyclic order (defined later as the vertex ordering
on the outer face) of each of the outerplanar embeddings of the $G_{i}$’s. The
_book thickness_ or _pagenumber_ [2] is the minimal number of pages for which
a graph has a valid book embedding. Note that a graph is outerplanar if and
only if it has pagenumber $1$, and it is known that the pagenumber of planar
graphs is at most $4$ [23].

#### Our contribution.

Our main result is a classification of $\mathcal{D}$ into two sub-families,
$\mathcal{D}=\mathcal{D}_{NOP}\cup\mathcal{D}_{2PBE}$, such that

  * •

every sequence in $\mathcal{D}_{NOP}$ is provably non-outerplanaric, and

  * •

every sequence in $\mathcal{D}_{2PBE}$ is given (in polynomial time) a
realizing graph $G=(V,E)$, $E=E_{1}\cup E_{2}$, enjoying a 2-page book
embedding with pages $G_{1}$ and $G_{2}$ (hereafter referred to as a _2PBE
realization_). Moreover, $G_{2}$ is bipartite (hereafter, an _OP+bi
realization_), and in some cases, $G_{2}$ consists of at most one or two edges
(hereafter, an _OP+1_ or _OP+2_ realization).

Note that every _outerplanaric_ sequence in $D$ falls in $\mathcal{D}_{2PBE}$.
Thus, the above result can be interpreted as yielding a polynomial time
algorithm providing an “approximation” for outerplanaric sequences, in the
sense that if the given sequence $d$ is outerplanaric (i.e., has a 1-page
realization), then the algorithm will produce a 2-page realization for it. We
remark that for many of the outerplanaric sequences in $\mathcal{D}$, we are
in fact able to find an outerplanar realization, but as this refined
classification is incomplete, it is omitted here.

Figure 1 gives an overview of the algorithm.

$d\in\mathcal{D}$, $d$ is graphic$d_{n-1}\leq 2$ and $d_{n-2}\leq 3$ Not
outerplanaric (Lemma 3) $d\in\mathcal{D}_{\leq 4}$? Build 2PBE (Theorem 15)
$d_{2}\leq 3$? Build 2PBE (Lemma 18) $2\Delta_{E}\geq\Delta_{\omega}$ Build
2PBE (Lemma 20) Not outerplanaric (Lemma 8) noyesyesnoyesnoyesno Figure 1: A
flowchart of the resulting algorithm. $\Delta_{E}=(4n-6-\sum d)/2$ and
$\Delta_{\omega}=3\omega_{1}+2\omega_{2}+\omega_{3}-n$.

#### Additional related work.

For the Outerplanar Degree Realization problem, a full characterization of
_forcibly_ outerplanar graphic sequences (namely, sequences each of whose
realizations is outerplanar) was given in [5]. A characterization of the
degree sequence of maximal outerplanar graphs having exactly two 2-degree
nodes was provided in [17]. This was also mentioned in [3]. A characterization
of the degree sequences of maximal outerplanar graphs with at most four
vertices of degree 2 was given in [14].

Sufficient conditions for the realization of $2$-trees were given in [15]. A
full characterization of the degree sequences of 2-trees was presented in [3].
A graph $G$ is a 2-tree if $G=K_{3}$ or $G$ has a vertex $v$ with degree 2,
whose neighbors are adjacent and $G[V\setminus\left\\{v\right\\}]$ is a
2-tree. This definition implies, in particular, that 2-trees have $\sum
d=4n-6$. By Theorem 1 of [3], if a sequence $d$ is maximal outerplanaric,
i.e., it is outerplanaric and satisfies $\sum d=4n-6$, then $d$ can be
realized by a 2-tree. In [19] it was shown that every 2-tree has a 2-page book
embedding. Note that the class of 2-trees is not hereditary, i.e., subgraphs
of 2-trees are not necessarily 2-trees. Therefore, the result of [3] does not
apply to non-maximal degree sequences.

For the Planar Degree Realization problem, regular planar graphic sequences
were classified in [12], and planar bipartite biregular degree sequences were
studied in [1]. In [20], Schmeichel and Hakimi determined which graphic
sequences with $d_{1}-d_{n}=1$ are planaric, and presented similar results for
$d_{1}-d_{n}=2$, with a small number of unsolved cases. Some of the sequences
left unsolved in [20] were later resolved in [7, 8]. Some additional studies
on special cases of the planaric degree realization problem were listed in
[18].

##  2 Preliminaries

#### Definitions and notation.

Given two $n$-integer sequences $d$ and $d^{\prime}$, denote their
componentwise addition and difference, respectively, by $d\oplus
d^{\prime}=(d_{1}+d^{\prime}_{1},\ldots,d_{n}+d^{\prime}_{n})$ and $d\ominus
d^{\prime}=(d_{1}-d^{\prime}_{1},\ldots,d_{n}-d^{\prime}_{n})$. For a
nonincreasing sequence $d$ of $n$ nonnegative integers, let $\mbox{\sf
pos}(d)$ denote the prefix consisting of the positive integers of $d$
(discarding the zeros). Given two sequences $d^{\prime}$ and
$d^{\prime\prime}$ of length $n^{\prime}$ and $n^{\prime\prime}$ respectively,
let $d^{\prime}\circ
d^{\prime\prime}=(d^{\prime}_{1},\ldots,d^{\prime}_{n^{\prime}},d^{\prime\prime}_{1},\ldots,d^{\prime\prime}_{n^{\prime\prime}})$.

Consider a simple (undirected) graph $G=(V,E)$. A (directed) _circuit_ in $G$
is an _ordered set_ of vertices
$C=\left\\{v_{0},v_{1},\ldots,v_{k-1}\right\\}$ (with possible repetitions)
such that $(v_{i},v_{(i+1)\bmod k})\in E$ for every $i=0,\ldots,k-1$. The
directed edge set of the circuit $C$ is $E(C)=\\{\langle v_{i},v_{(i+1)\bmod
k}\rangle\mid i=0,\ldots,k-1\\}$ and it is required that no directed edge may
appear on it more than once. If the vertices of $C$ are distinct then it is
called a _cycle_. A _triangle_ is a cycle consisting of three edges.

For a graph $G=(V,E)$, one may define an accompanying embedding in the plane,
namely, a mapping of every vertex to a point in two-dimensional space, with a
curve connecting the two endpoints $u,w$ of every edge $(u,w)\in E$. An
_outerplanar_ graph $G$ is a graph that has a planar embedding in which all
the vertices occur on the outer face. (This embedding can be transformed into
a 1-page book embedding of $G$, with all vertices placed on the _spine_ of the
book.) We refer to the order in which the vertices occur on the outer face as
the _cyclic-order_ of $G$, and denote it by $C_{order}(G)$. A _maximal
outerplanar_ (MOP) graph $G$ is an outerplanar graph such that adding any new
edge to it results in a non-outerplanar graph. It is folklore that for a
2-connected outerplanar graph, the cyclic order corresponds to a Hamiltonian
cycle in $G$.

Hereafter, whenever we discuss a given outerplanar (resp., 2PBE) graph, we
implicitly assume that some outerplanar (resp., 2PBE) embedding for it is
given as well, and when constructing an outerplanar (resp., 2PBE) graph, we
also give an outerplanar (resp., 2PBE) embedding for it.

Given an outer-planar embedding, an _external_ edge is an edge residing on the
outer face. That is, $e=(u,w)$ is external if $u$ and $w$ are neighbors on a
circuit which is part of the outer face. All other edges of $G$ are
_internal_. An _outer_ (respectively, _inner_) _cycle_ in $G$ is a cycle all
of whose edges are external (resp., internal). Note that the outer face may be
comprised of several outer-cycles (as can be seen in Figure 2).

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$ Figure 2: An outerplanar graph
without degree-1 vertices. The triangle $(5,7,9)$ is the only internal cycle,
while $(1,2,3)$, $(3,4,5,6,7,8,9,10)$, and $(11,12,13)$ are outer-cycles. A
possible cyclic-order is $(1,2,3,4,5,6,7,8,9,10,11,12,13)$.

#### Degree sequences of trees and forests.

Consider a nonincreasing sequence $d=(d_{1},\ldots,d_{n})$ of positive
integers such that $\sum d$ is an even number. It is known that if $\sum d\leq
2n-2$ then $d$ is graphic, and moreover, $d$ can be realized by an acyclic
graph (forest). In this case, $d$ is called a _forestic_ sequence. If $\sum
d=2n-2$, then $d$ can be realized only by trees, and $d$ is called a _treeic_
sequence. A vertex of degree one is called a _leaf_.

We make use of a special type of realizations of treeic sequences by
_caterpillar graphs_. In a caterpillar graph $G=(V,E)$, all the non-leaves
vertices are arranged on a path, called the _spine_ of the caterpillar.
Formally, the spine of a caterpillar graph is an ordered sequence
$S=(x_{1},\ldots,x_{s})\subseteq V$, $s\geq 1$, in which $(x_{i},x_{i+1})\in
E$ for $i=1,\ldots,s-1$ (see Figure 3 for an example).

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$ Figure 3: A caterpillar graph with degree
sequence $(5,4^{3},2,1^{11})$. Spine vertices are gray, leaves are yellow.

The other ingredient in the construction of a realization to a forestic
sequence is a collection of disjoint edges, hereafter referred to somewhat
informally as a _matching_.

######  Observation 1.

A forestic sequence $d=(d_{1},d_{2},\ldots,d_{n})$ of positive integers can be
realized by a union of a caterpillar graph and a matching.

###### Proof.

First consider a treeic sequence $d$ (such that $\sum d=2n-2$). Assume there
are $n-s$ vertices of degree 1 in $d$. Denote by $d^{*}$ the prefix of $d$
that contains all the degrees $d_{i}>1$. It follows that $\sum
d^{*}+(n-s)=\sum d=2n-2$, or equivalently $\sum d^{*}-2s+2=n-s$. To get the
caterpillar realization of $d$, first arrange $s$ vertices corresponding to
the degrees of $d^{*}$ in a path. The path edges contribute $2s-2$ to the
volume $\sum d^{*}$. The missing $\sum d^{*}-2s+2=n-s$ degrees are satisfied
by attaching the $n-s$ leaves to the path, which now forms the spine of the
caterpillar realization. Note that the order of the vertices on the spine can
be arbitrary.

Now assume that $d$ is forestic but not treeic, i.e., $\sum d<2n-2$. In this
case, remove pairs of 1 degrees from $d$ until the volume of the reaming
sequence $d^{\prime}$ with $n^{\prime}$ vertices is $2(n^{\prime}-2)$. This
must happen because each pair removal reduces the volume by $2$ while $2n-2$
decreases by $4$. Let $G^{\prime}$ be the caterpilar realization of
$d^{\prime}$ as implied by the first part of the proof. To get the realization
of $d$, add $(n-n^{\prime})/2$ edges to $G^{\prime}$ to satisfy the
$n-n^{\prime}$ removed 1 degrees by a matching. ∎

#### Some known results.

We next summarize known conditions for sequence outerplanarity.

######  Lemma 2 ([22]).

If $d=(d_{1},\ldots,d_{n})$ is an outerplanaric degree sequence where $n\geq
2$, then $\sum d\leq 4n-6$, with equality if and only if $d$ is maximal
outerplanaric.

######  Lemma 3 ([21]).

If $d=(d_{1},\ldots,d_{n})$ is outerplanaric, then  (i) $d_{n-1}\leq 2$, and
(ii) $d_{n-2}\leq 3$.  Moreover, $d_{n-1}=d_{n}=2$ in a maximal outerplanaric
sequence $d$.

Our next observation is that Lemma 2 can be improved if $\omega_{1}$, the
multiplicity of degree $1$ in $d$ is taken into consideration. Specifically,
for the case $\sum d>2n-2$, we have the following.

######  Lemma 4.

If $d=(d_{1},\ldots,d_{n})$ is outerplanaric and $\sum d>2n-2$, then $\sum
d\leq 4n-6-2\omega_{1}$.

###### Proof.

Let $d$ be as in the lemma and let $G=(V,E)$ be an outerplanar graph that
realizes $d$. Construct a graph $G^{\prime}$ by deleting from $G$ all the
$\omega_{1}$ vertices of degree $1$ together with their incident edges, and
subsequently deleting the vertices whose degree was reduced to zero. The graph
$G^{\prime}$ may contain vertices whose degree became 1. Observe that
$G^{\prime}$ is outerplanar, and let $d^{\prime}=\deg(G^{\prime})$. Note that
$n^{\prime}\leq n-\omega_{1}$, where $n^{\prime}$ the number of vertices in
$G^{\prime}$. Lemma 2 yields the claim, since

$\sum d=\sum d^{\prime}+2\omega_{1}\leq
4(n-\omega_{1})-6+2\omega_{1}=4n-6-2\omega_{1}~{},$

where the first equality comes from the fact that $\omega_{1}$ vertices of
degree $1$ together with their incident edges are deleted, and the inequality
is due to Lemma 2. ∎

We remark that Lemma 4 is false without the assumption that $\sum d>2n-2$. To
see this, consider the treeic sequence $d=(a,1^{a})$ which is (uniquely)
realized by a star graph and therefore is outerplanaric. The process in the
proof of Lemma 4 yields $G^{\prime}$ consisting of one isolated vertex. Note
that Lemma 2 cannot be applied in this case. Indeed, we have

$\sum d=2a>2a-2=4(a+1)-6-2a=4n-6-2\omega_{1}~{}.$

We now recall some facts concerning maximal outerplanaric sequences (or
MOP’s).

######  Fact 1 ([16]).

A graph is a MOP if and only if it can be constructed from a triangle by a
finite number of applications of repeatedly applying the following operation:
to the graph already constructed, add a new vertex in the exterior face and
join it to two adjacent vertices on that face.

We rely on the construction method of Lemma 1 to prove the following simple
but useful facts. Parts (1) and (2) are known (cf. [22, 4]. We could not find
a reference for Part (3), so we give a proof for completeness.

######  Lemma 5.

Consider a maximal outerplanar graph $G$ with $n\geq 4$ vertices.

  1. (1)

Every two vertices of degree 2 in $G$ are nonadjacent.

  2. (2)

there is a outerplanar embedding of $G$ such that the boundary of the outer
face is a Hamiltonian cycle $C$ and each inner face is a triangle.

  3. (3)

Removing the edges of $C$ from $G$ and discarding the resulting degree-0
vertices yields a connected outerplanar graph.

###### Proof.

The lemma is proved by induction on the number of vertices $n$. The claim
clearly holds for the base case of $n=4$, where the 4-cycle augmented by a
single chord is the only MOP. Now suppose the claim holds for all MOP graphs
with at most $n$ vertices, and consider a graph $G$ with $n+1$ vertices.

By 1 $G$ was obtained by adding a vertex $v$ and edges $(v,u)$ and $(v,w)$ to
some MOP graph $G^{\prime}$ in which $e=(u,w)$ is an external edge. By the
inductive hypothesis, the claim holds for $G^{\prime}$, so there exists an
outer-cycle $C^{\prime}$ of $G^{\prime}$ which is Hamiltonian, and removing
$C^{\prime}$ yields a connected graph $c(G^{\prime})$. Note that $u$ and $w$
both appear in $G^{\prime}$, so by Lemma 3 their degrees in $G^{\prime}$ are 2
or higher, and moreover, at least one of $\deg_{G^{\prime}}(u)$ and
$\deg_{G^{\prime}}(w)$ is 3 or higher, since $G^{\prime}$ satisfies Property
(1). This implies that at least one of $u$ and $w$ belongs to $c(G^{\prime})$.
Adding $v$ to $G$ and connecting it to $u$ and $w$ increases their degrees in
$G$ to 3 or higher, so $v$ has no neighbor of degree 2 in $G$. Hence, property
(1) holds in $G$ by the inductive hypothesis. Also, inserting the vertex $v$
between $u$ and $w$ in $C^{\prime}$ yields a Hamiltonian cycle $C$ for $G$,
implying Property (2). Finally, removing $C$ from $G$ yields the graph
$c(G)=c(G^{\prime})\cup\\{e\\}$, which is connected since $c(G^{\prime})$ is
connected and it contains $u$ or $w$. ∎

Jao and West [13] show that the number of internal triangles of a MOP is
related to $\omega_{2}$.

######  Lemma 6.

[13] Let $G$ be a maximal outerplanar graph on $n$ vertices, let $d=\deg(G)$,
and let $t$ be the number of internal triangles. If $n\geq 4$, then
$t=\omega_{2}-2$.

#### Bipartite bracket balancing (BBB) algorithm.

we make use of a simple variant of the Bracket Balancing problem, in which the
matched brackets must fit in given positions. Formally, the problem, referred
to as Bipartite Bracket Balancing (BBB), is defined as follows. We are given
two ordered sets $P=\left\langle p_{1},\ldots,p_{k}\right\rangle$ and
$Q=\left\langle q_{1},\ldots,q_{k}\right\rangle$, merged into a $2k$-element
sequence $R=\left\langle r_{1},\ldots,r_{2k}\right\rangle$ that contains all
the elements from $P$ and $Q$ while maintaining their original order. The goal
is to associate with every $r_{i}$, $1\leq i\leq 2k$, a bracket
$f(r_{i})\in\left\\{[,]\right\\}$ with the following two properties:

  * •

The sequence $f(R)=\langle f(r_{1}),\ldots,f(r_{2k})\rangle$ is balanced such
that the number of opening brackets ($``[^{\prime\prime}$) in every prefix of
$R$ is no less than the number of closing brackets ($``]^{\prime\prime}$) in
this prefix. Observe that in balanced sequences it is possible to match the
opening brackets with the closing brackets so that the intervals associated
with the matched brackets are either nested or disjoint.

  * •

if $f(r_{i})=[$ and $f(r_{j})=]$ were matched, for $i<j$, then $r_{i}\in P$
and $r_{j}\in Q$ or vice versa.

This problem can be solved by a straightforward variant of the standard stack-
based linear-time bracket balancing algorithm, named Algorithm BBB, described
here for completeness. The algorithm uses a stack $D$ and scans the sequence
$R$ from start to end. At any given time, the stack contains either only
elements from $P$ or only elements from $Q$ (i.e., $D\subseteq P$ or
$D\subseteq Q$). Upon reaching the element $r_{i}$, the algorithm acts based
on the stack contents, as follows:

  * •

$D=\emptyset$, or $D\subseteq P$ and $r_{i}\in P$, or $D\subseteq Q$ and
$r_{i}\in Q$ :
$PUSH(r_{i},D)$

  * •

$D\subseteq P$ and $r_{i}\in Q$, or $D\subseteq Q$ and $r_{i}\in P$ :
$x\leftarrow POP(D)~{}~{}$; $f(x)\leftarrow~{}[$ ; $f(r_{i})\leftarrow~{}]$

It is easy to verify that the algorithm solves the Bipartite Bracket Balancing
problem.

Figure 4: A merged sequence $R$ and its corresponding bracket assignment.

Figure 4 illustrates an example sequence $R$ and the corresponding balanced
bracket assignment generated by the algorithm. Notice that the stack switches
its contents from time to time. In particular, it initially gets only elements
of $P$, then becomes empty after inspecting $r_{12}=q_{6}$, then contains only
elements of $Q$ for a while, then becomes empty after inspecting
$r_{16}=q_{8}$, and so on.

##  3 Necessary and Sufficient Conditions for Outerplanarity

This section presents some necessary and sufficient conditions for
outerplanarity, which are used to prove the results of the main section
concerning 2-page book embedding. The next lemma provides a necessary
condition for maximal outerplanarity.

######  Lemma 7.

If $d=(d_{1},\ldots,d_{n})$ is a maximal outerplanaric sequence where
$d_{1}>3$ then if $d_{2}>3$ or $\omega_{2}>2$ then $2\omega_{2}+\omega_{3}\leq
n$ otherwise $2\omega_{2}+\omega_{3}\leq n+1$.

###### Proof.

Let $d$ be as in the lemma and let $G$ be a maximal outerplanar realization of
$d$. Observe that by Lemma 5(2), removing the outer-cycle from $G$ and
discarding the resulting 0-degree vertices results in an outerplanar graph
$G^{\prime}$ with degree sequence $d^{\prime}=\mbox{\sf pos}(d\ominus(2^{n}))$
such that $n^{\prime}=n-\omega_{2}$. It follows that $d^{\prime}$ is
outerplanaric. We consider the following three cases.

Case 1:

$\omega_{2}>2$. $G$ has an internal triangle due to Lemma 6. This triangle
still exists in $G^{\prime}$. Moreover, $G^{\prime}$ is connected by Lemma
5(3). It follows that $\sum d^{\prime}>2n^{\prime}-2$. By Lemma 4,

$2n-6~{}=~{}\sum d-2n~{}=~{}\sum
d^{\prime}~{}\leq~{}4n^{\prime}-6-2\omega_{1}^{{}^{\prime}}~{}=~{}4(n-\omega_{2})-6-2\omega_{3}.$

Simplifying yields that $2\omega_{2}+\omega_{3}\leq n$.

Case 2:

$\omega_{2}=2$ and $d_{2}>3$. We have that $\omega_{3}\leq n-4$ and
$2\omega_{2}+\omega_{3}=4+\omega_{3}\leq n$.

Case 3:

$\omega_{2}=2$ and $d_{2}\leq 3$. Since $d_{1}>3$, we have that
$\omega_{3}\leq n-3$. It follows that $2\omega_{2}+\omega_{3}=4+\omega_{3}\leq
n+1$.

The lemma follows. ∎

Note that this lemma does not hold for non-maximal outerplanaric sequences.
For example, the outerplanaric sequence $(4,2^{4})$ is a counterexample for
which $2\omega_{2}+\omega_{3}=8=n+3$.

We next define two functions that play a key role in our analysis. For a
sequence $d$, define the _edge deficit_ and _low degree surplus_ of $d$ to be,
respectively,

$\displaystyle\Delta_{E}(d)$ $\displaystyle=(4n-6-\sum d)/2,$
$\displaystyle\Delta_{\omega}(d)$
$\displaystyle=3\omega_{1}+2\omega_{2}+\omega_{3}-n.$

Note that $\Delta_{E}(d)\geq 0$ for any outerplanaric sequence. If
$\Delta_{E}(d)>0$ and $G$ is a nonmaximal outerplanar realization of $d$, then
$\Delta_{E}(d)$ is the number of edges that need to be added to $G$ to
generate a maximal outerplanar graph. If $d$ is clear from the context we
write simply $\Delta_{E},\Delta_{\omega}$ instead of
$\Delta_{E}(d),\Delta_{\omega}(d)$. The next lemma shows a connection between
$\Delta_{E}$ and $\Delta_{\omega}$.

######  Lemma 8.

Let $d=(d_{1},\ldots,d_{n})$ be an outerplanaric sequence with $d_{2}>3$. Then
$2\Delta_{E}\geq\Delta_{\omega}$.

###### Proof.

Let $d$ be as in the lemma, and let $G$ be an outerplanar realization of $d$.
We can add $\Delta_{E}$ edges to $G$ so as to transform it into a maximal
outerplanar graph $G^{\prime}$ (without adding vertices). For $0\leq
i\leq\Delta_{E}$, let $G_{i}$ be the graph $G$ after adding $i$ edges, and let
$d^{i}$ be the degree sequence of $G_{i}$. By definition, $G_{0}=G$ and
$G_{\Delta_{E}}=G^{\prime}$. Define
$f(G_{i})=2\Delta_{E}(d^{i})-\Delta_{\omega}(d^{i})$ for $0\leq
i\leq\Delta_{E}$. We show:

$\displaystyle f(G_{i})\geq f(G_{i+1})\textrm{~{}for ~{}any}~{}0\leq
i\leq\Delta_{E}-1.$ (1)

Let $d^{\prime}=\deg(G^{\prime})$. Then $\sum d^{\prime}=4n-6$ and
$\omega^{\prime}_{1}=0$. Lemma 7 implies that
$2\omega^{\prime}_{2}+\omega^{\prime}_{3}\leq n$. Thus,
$\Delta_{E}(d^{\prime})=0$ and
$\Delta_{\omega}(d^{\prime})=3\omega^{\prime}_{1}+2\omega^{\prime}_{2}+\omega^{\prime}_{3}-n\leq
0$. Hence,

$\displaystyle
f(G_{\Delta_{E}})=2\Delta_{E}(d^{\prime})-\Delta_{\omega}(d^{\prime})\geq 0.$
(2)

$\deg_{G_{i}}(u),\deg_{G_{i}}(v)$ | $\delta$
---|---
$(1,1)\to(2,2)$ | $-2$
$(1,2)\to(2,3)$ | $-2$
$(1,3)\to(2,4+)$ | $-2$
$(1,4+)\to(2,5+)$ | $-1$
$(2,2)\to(3,3)$ | $-2$

$\deg_{G_{i}}(u),\deg_{G_{i}}(v)$ | $\delta$
---|---
$(2,3)\to(3,4+)$ | $-2$
$(2,4+)\to(3,4+)$ | $-1$
$(3,3)\to(4+,4+)$ | $-2$
$(3,4+)\to(4+,4+)$ | $-1$
$(4+,4+)\to(4+,4+)$ | $0$

We now compute how adding a single edge $(u,v)$ to $G_{i}$ decreases the value
of $3\omega_{1}(G_{i})+2\omega_{2}(G_{i})+\omega_{3}(G_{i})$. There are ten
possibilities for the changes in the degrees of $u$ and $v$ ($\deg_{G_{i}}(u)$
and $\deg_{G_{i}}(v)$) that cause
$3\omega_{1}(G_{i})+2\omega_{2}(G_{i})+\omega_{3}(G_{i})$ to change by
$\delta$. We list the ten possibilities in the above table where we denote
degrees of $4$ or more by $4+$. It follows that adding a single edge decreases
$3\omega_{1}(G_{i})+2\omega_{2}(G_{i})+\omega_{3}(G_{i})$ by at most $2$ which
implies that $\Delta_{\omega}(d^{i})$ is also decreased by at most $2$. Also,
$2\Delta_{E}(d^{i})$ is decreased by exactly $2$ when adding a single edge to
$G_{i-1}$. Therefore, Inequality (1) holds. Combining this with inequality (2)
implies that $f(G_{0})\geq 0$. The lemma follows because
$f(G_{0})=2\Delta_{E}-\Delta_{\omega}$. ∎

We start with a sequence $d$ satisfying $d_{n}=2$ and $\omega_{2}=2$. To prove
our next result, we generate a reduced sequence $d^{\prime}$ of $d$ where each
degree is decreased by $2$. We verify that $d^{\prime}$ is forestic and
realize it by a graph $G^{\prime}$ constructed as the union of a caterpillar
graph and a matching, following 1. Then, a realization $G$ of $d$ is found by
adding a Hamiltonian cycle to $G^{\prime}$. The Hamiltonian cycle is the
outer-cycle of $G$. It follows that in this case, there is a realization of
$d$ where each vertex appears exactly once on the outer-cycle.

######  Lemma 9.

Let $d\in\mathcal{D}$. If

  1. (i)

$d_{n}=2$ and

  2. (ii)

$\omega_{2}=2$,

then $d$ is outerplanaric, and has a realization with an outerplanar embedding
that has a Hamiltonian outer-cycle.

###### Proof.

Let $d$ be as in the lemma. First, we construct the sequence
$d^{\prime}=(d^{\prime}_{1},\ldots,d^{\prime}_{n^{\prime}})$ by subtracting
$2$ from each degree of $d$, i.e., let $d^{\prime}_{i}=d_{i}-2$ for
$i\in\left\\{1,\ldots,n-2\right\\}$. Note that $n^{\prime}=n-2$ and that $\sum
d^{\prime}$ is even. Moreover, note that $d^{\prime}$ is forestic, since $\sum
d\leq 4n-6$. Hence,

$\sum d^{\prime}=\sum d-2n\leq 2n-6=2(n^{\prime}+2)-6=2n^{\prime}-2.$

By 1, $d^{\prime}$ can be realized by a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ composed of the union of a caterpillar
graph $T^{\prime}$ and a matching $M^{\prime}$. Let $S=(x_{1},\ldots,x_{s})$
be the vertices on the spine of $T^{\prime}$, and let
$X_{i}=\left\\{\ell_{i,1},\ldots,\ell_{i,k_{i}}\right\\}\subseteq V^{\prime}$
be the leaves adjacent to the spine vertex $x_{i}$, for
$i\in\left\\{1,\ldots,s\right\\}$. Note that vertex $x_{i}$ has degree
$k_{i}+1$ if $i\in\left\\{1,s\right\\}$, otherwise it has degree $k_{i}+2$.
Assume
$M^{\prime}=\left\\{(x^{\prime}_{1},x^{\prime\prime}_{1}),\ldots,(x^{\prime}_{t},x^{\prime\prime}_{t})\right\\}$.
To find an outerplanar realization of $d$, we add a set of edges to
$G^{\prime}$ that form a Hamiltonian cycle (including two additional vertices
of degree $2$). We explain our construction in four steps for which we assume
that $s$ is odd. If $s$ is even, an analogogous construction applies.

  1. (1)

Add the edges along the following two paths
$P_{1}=(x_{1},x_{3},\ldots,x_{s-2},x_{s})$ and
$P_{2}=(x_{s-1},x_{s-3},\ldots,x_{4},x_{2})$ connecting spine vertices in odd
and even positions, respectively.

  2. (2)

Add two additional vertices $x_{0},x_{s+1}$ and use them to form a cycle $C$
together with $P_{1}$ and $P_{2}$. Let
$C=(x_{0},x_{1},x_{3},\ldots,x_{s},x_{s+1},x_{s-1},x_{s-3},\ldots,x_{4},x_{2},x_{0})$.

  3. (3)

The leaves of a vertex in $P_{1}$ are inserted into $C$ between two vertices
of $P_{2}$. Specifically, the leaves of $x_{i}$, for $i=1,\ldots,s$, are
inserted between $x_{i-1}$ and $x_{i+1}$.

  4. (4)

Insert vertices $x^{\prime}_{1},\ldots,x^{\prime}_{t}$ on the segment between
$\ell_{s,k_{s}}$ and $x_{s+1}$ in clockwise order. Similarly, insert vertices
$x^{\prime\prime}_{1},\ldots,x^{\prime\prime}_{t}$ on the segment between
$x_{s+1}$ and $x_{s}$ in a counter-clockwise order. Connect $x^{\prime}_{i}$
and $x^{\prime\prime}_{i}$ for $1\leq i\leq t$.

$x_{0}$$x_{7}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$...$$...$$...$$...$$...$$...$$x^{\prime}_{1}$$x^{\prime\prime}_{1}$
Figure 5: Illustration of $G$ as constructed in Lemma 9. The vertices
$x_{1},\ldots,x_{6}$ and the leaves in yellow (labels omitted) together with
the black edges form the caterpillar graph $G^{\prime}$. Note that $x_{5}$ has
no leaves. Paths $P_{1}$ and $P_{2}$ are depicted in green and blue,
respectively. Together, they form the cycle $C$.

Figure 5 illustrates the construction of $G$. Following the four steps, we
have

$\displaystyle C$
$\displaystyle=(x_{0},x_{1},\ell_{2,1},\ell_{2,2},\ldots,\ell_{2,k_{2}},x_{3},\ell_{4,1},\ell_{4,2},\ldots,\ell_{4,k_{2}},x_{5},\ldots,x_{s-1},\ell_{s,1},\ell_{s,2},\ldots,\ell_{s,k_{s}},$
$\displaystyle
x^{\prime}_{1},\ldots,x^{\prime}_{t},x_{s+1},x^{\prime\prime}_{t},\ldots,x^{\prime\prime}_{1},x_{s},\ell_{s-1,k_{s-1}},\ell_{s-1,k_{s-1}-1},\ldots,x_{2},\ell_{1,k_{1}},\ell_{1,k_{1}-1},\ldots,\ell_{1,1},x_{0})~{}.$

Formally, let $V=V^{\prime}\cup\\{x_{0},x_{s+1}\\}$. The set $E^{\prime}$
contains the path connecting the spine vertices, $\\{(x_{i},x_{i+1})\mid
i=1,2,\ldots,s-1\\}$, and the edges connecting each spine vertex to its
leaves. The set $L$ contains edges among the leaves while the sets $A_{1}$ and
$A_{2}$ contain edges connecting spine and leaf vertices

$\displaystyle L$ $\displaystyle=~{}\\{(\ell_{i,j},\ell_{i,j+1})\mid
i=1,\ldots,s,~{}~{}~{}j=1,\ldots,k_{i}-1\\},$ $\displaystyle A_{2}$
$\displaystyle=~{}\\{(x_{i},\ell_{i+1,1})\cup(\ell_{i+1,k_{i+1}},x_{i+2})\;|\;i=1,\ldots,s\text{
and }k_{i+1}>0\\},$ $\displaystyle A_{1}$
$\displaystyle=~{}\\{(x_{i},x_{i+2})\;|\;i=1,\ldots,s\text{ and }k_{i+1}=0\\}$

Recall that
$M^{\prime}=\left\\{(x^{\prime}_{1},x^{\prime\prime}_{1}),\ldots,(x^{\prime}_{t},x^{\prime\prime}_{t})\right\\}$.
Note that $A_{2},A_{1},L,E^{\prime},M^{\prime}$ are pairwise disjoint. Let
$E=E^{\prime}\cup L\cup A_{2}\cup A_{1}\cup M^{\prime}$, and let $G=(V,E)$.
Notice that Figure 5 depicts an outerplanar embedding of $G$. By the
construction of $G$, every vertex in $V$ appears on the Hamiltonian outer-
cycle. No two edges in $E(G)$ cross each other. Therefore, $G$ is an
outerplanar graph. By the definition of $d^{\prime}$, two vertices of degree 2
are deleted, which correspond to $x_{0},x_{s+1}$. Every vertex in
$V\setminus\\{x_{0},x_{s+1}\\}$ has its degree decreased by 2. Recall that
$T^{\prime}\cup M^{\prime}$ realizes $d^{\prime}$. After adding $C$ to
$T^{\prime}$ and inserting $M^{\prime}$ in step (4), every vertex $i\in
V\setminus\\{x_{0},x_{s+1}\\}$ has its degree increased by 2, making it equal
to $d_{i}$. Combining this with the fact that $x_{0}$ and $x_{s+1}$ have
degree 2 in $G$, we have $\deg(G)=d$. The lemma follows. ∎

######  Corollary 10.

$d\in\mathcal{D}$ is outerplanaric If $\sum d\leq 4n-2\omega_{2}-2$ and
$d_{n-1}=d_{n}=2$.

###### Proof.

Let $d^{\prime\prime}$ be the prefix of $d$ satisfying
$d=d^{\prime\prime}\circ(2^{\omega_{2}})$. Consider the sequence
$d^{\prime}=d^{\prime\prime}\circ(2^{2})$ of length
$n^{\prime}=n-\omega_{2}+2$. Observe that $\sum d^{\prime}$ is even. As $\sum
d\leq 4n-2\omega_{2}-2$, it follows that

$\sum d^{\prime}~{}=~{}\sum
d-2(\omega_{2}-2)~{}\leq~{}4n-4\omega_{2}+2~{}=~{}4(n-\omega_{2}+2)-6~{}=~{}4n^{\prime}-6.$

Sequence $d^{\prime}$ satisfies the preconditions of Lemma 9. Hence, let
$G^{\prime}$ be an outerplanar realization and embedding of $d^{\prime}$ with
a Hamiltonian outer-cycle. An outerplanar realization of $d$ is obtained by
replacing an edge on this outer-cycle by a path of length $\omega_{2}-2$. ∎

##  4 Approximate Realizations by Book Embeddings

This section concerns finding approximate realizations. Our main result is a
classification of $\mathcal{D}$ into two sub-families,
$\mathcal{D}=\mathcal{D}_{NOP}\cup\mathcal{D}_{2PBE}$, such that

  * •

every sequence in $\mathcal{D}_{NOP}$ is provably non-outerplanaric, and

  * •

every sequence in $\mathcal{D}_{2PBE}$ is given a realizing gaph enjoying a
2-page book embedding (hereafter referred to as a _2PBE realization_).

Note that if a graph has pagenumber $2$, then it is planar (the converse it
false).

###  4.1 A 2PBE realization for sequences with $d_{1}\leq 4$

In this section, we analyze the subclass $\mathcal{D}_{\leq
4}\subseteq\mathcal{D}$ of sequences whose largest degree satisfies $d_{1}\leq
4$. We show that every $d\in\mathcal{D}_{\leq 4}$ enjoys a 2PBE realization.
Lemmas 12, 13 and 14 imply Theorem 15.

First, consider the case where $\omega_{3}>0$ and $d_{n-1}=d_{n}=2$.

######  Lemma 11.

Every $d\in\mathcal{D}_{\leq 4}$ s.t. $d_{n}=d_{n-1}=2$ and $\omega_{3}>0$ is
outerplanaric.

###### Proof.

The degree sum $\sum d$ is even, so necessarily $\omega_{3}\geq 2$. Since
$n=\omega_{4}+\omega_{3}+\omega_{2}$, it follows that $\sum
d=4\omega_{4}+3\omega_{3}+2\omega_{2}\leq 4n-2\omega_{2}-2$, which satisfies
the conditions of Corollary 10. Therefore, $d$ is outerpananric. ∎

######  Lemma 12.

Every $d\in\mathcal{D}_{\leq 4}$ s.t. $d_{n}=d_{n-1}=2$ and $d_{1}\leq n-1$
has an OP+2 realization.

###### Proof.

When $\omega_{3}>0$, the claim follows by Lemma 11. So hereafter suppose
$\omega_{3}=0$. We split the analysis into three cases.

Case 1:

$\omega_{4}=0$. Then $d=(2^{n})$, which for $n\geq 3$ can be realized by a
cycle, hence it is outerplanaric.

Case 2:

$\omega_{4}=1$. Then $\omega_{2}\geq 4$ since $\omega_{3}=0$ and $d_{1}=4\leq
n-1$. In this case, construct an outerplanar graph $G$ as follows. First,
connect vertex $v_{1}$ of degree 4 to vertices $v_{2},v_{3},v_{4},v_{5}$ of
degree 2. Next, add edges $(v_{2},v_{3}),(v_{4},v_{5})$ and insert
$\omega_{2}-4$ vertices into the edge $(v_{2},v_{3})$, i.e., transform this
edge into a path $(v_{2},u_{1},\ldots,u_{\omega_{2}-4},v_{3})$. Notice that
$G$ is outerplanar.

Case 3:

$\omega_{4}\geq 2$. Here, $d$ consists of only 2’s and 4’s. Since $\sum d\leq
4n-6$, necessarily

$\displaystyle\omega_{2}\geq 3.$ (3)

Generate a sequence $d^{\prime}$ by removing one degree $2$ from $d$ and
reducing $d_{1},d_{2}$ by $1$. Then
$d^{\prime}=(4^{\omega_{4}-2},3^{2},2^{\omega_{2}-1})$. It is easy to verify,
using Eq. (3), that $d^{\prime}$ satisfies the preconditions of Lemma 11.
Hence, let $G^{\prime}$ be an outerplanar realization of $d^{\prime}$ by Lemma
11. We create a 2-page book embedding graph $G$ realizing $d$ based on
$G^{\prime}=(V^{\prime},E^{\prime})$. Let $v_{1},v_{2}\in V^{\prime}$ be the
vertices with $\deg_{G^{\prime}}(v_{1})=\deg_{G^{\prime}}(v_{2})=3$. Add an
isolated vertex $u$ to $G^{\prime}$ and obtain an outerplanar graph
$G_{1}=(V,E^{\prime})$ with $V=V^{\prime}\cup\\{u\\}$. Let $G_{2}=(V,E_{2})$
with $E_{2}=\\{(v_{1},u),(v_{2},u)\\}$. The position of $u$ in the embeddings
of $G^{\prime}$ and $G_{2}$ can be fixed arbitrarily since $u$ is isolated in
$G_{1}$, and $G_{2}$ has only two edges that do not exist in
$\bar{G}^{\prime}$. Hence, $G_{1}$ and $G_{2}$ form a 2PBE realization for
$d$. Notice that $G_{1}$ is outerplanar and $G_{2}$ consists of two edges.

The lemma follows. ∎

######  Lemma 13.

Every $d\in\mathcal{D}$ s.t. $d_{n}\geq 2$ and $d_{n-1}\geq 3$ has an OP+1
realization.

###### Proof.

Since $\sum d\leq 4n-6$ and $d_{n}\geq 2$, we have $d_{n-1}\leq 3$. Consider
the two possible cases, $(d_{n-1},d_{n})\in\\{(2,3),(3,3)\\}$.

Case 1:

$d_{n}=d_{n-1}=3$. Then construct a sequence $d^{\prime}$ by replacing
$(d_{n-1},d_{n})$ with $(2,2)$. Note that $d^{\prime}$ satisfies the
conditions in Lemma 9 and it can be realized by a outerplanar graph
$G^{\prime}$ with two nonadjacent vertices $v^{\prime},v^{\prime\prime}$ of
degree 2. Then $d$ can be realized by a graph $G$ obtained by adding the edge
$(v^{\prime},v^{\prime\prime})$ to $G^{\prime}$. One can verify that $G$ has a
2-page book embedding (with $G^{\prime}$ on one page and the added edge on the
other).

Case 2:

$d_{n}=2$ and $d_{n-1}=3$. In this case, $d_{n-2}=3$ since $\sum d\leq 4n-6$.
Construct $d^{\prime}$ by replacing $(d_{n-2},d_{n-1})$ with $(2,2)$. Note
that $\sum d^{\prime}\leq 4n-8$ and $\omega^{\prime}_{2}=3$, so $d^{\prime}$
satisfies the conditions in Corollary 10 and there is an outerplanar graph
$G^{\prime}$ realizing $d^{\prime}$. By the construction of $G^{\prime}$, it
has two nonadjacent vertices $v^{\prime},v^{\prime\prime}$ of degree 2.
Therefore, we can construct a graph $G$ by adding the edge
$(v^{\prime},v^{\prime\prime})$ to $G^{\prime}$. Again, $G$ has a 2-page book
embedding.

Notice that in both cases $G^{\prime}$ is outerplanar and the other page
consists of one edge. The lemma follows. ∎

It remains to deal with sequences $d\in\mathcal{D}_{\leq 4}$ that contain also
1’s. We show the following.

######  Lemma 14.

Every $d\in\mathcal{D}_{\leq 4}$ s.t. $d_{n}=1$ and $d_{1}\leq n-1$ has an
OP+2 realization.

###### Proof.

First, in $\omega_{1}$ steps, delete one degree 1 from the sequence and
decrease the current largest degree by 1, yielding the residual sequence
$d^{\prime}$, whose length is $n^{\prime}=n-\omega_{1}$. Since $\sum d\leq
4n-2\omega_{1}-6$ and $\sum d\geq 2n$,

$\displaystyle\sum d^{\prime}$ $\displaystyle\leq 4(n-\omega_{1})-6,$
$\displaystyle d^{\prime}_{n-\omega_{1}}$ $\displaystyle\geq 2$ (4)

Consider the following two cases.

Case 1:

$\omega_{1}\leq\omega_{4}$. Then
$d^{\prime}=(4^{\omega_{4}-\omega_{1}},3^{\omega_{3}+\omega_{1}},2^{\omega_{2}})$.
and that when $n^{\prime}=4$, $d^{\prime}$ is $OP+1$. In this case, if
$\omega_{2}\geq 2$ (respectively, $\omega_{2}\leq 1$), then $d^{\prime}$ has a
2PBE realization $G^{\prime}$ by Eq. (4) and Lemma 12, (resp., 13). Notice
that for $\omega_{2}\geq 2$, $d^{\prime}_{1}\leq n^{\prime}-1$ since
$\omega_{3}+\omega_{1}\geq 2$.

Case 2:

$\omega_{1}>\omega_{4}$. Then

$d^{\prime}=(3^{\omega_{3}+\omega_{4}-(\omega_{1}-\omega_{4})},2^{\omega_{2}+(\omega_{1}-\omega_{4})})=(3^{\omega_{3}+2\omega_{4}-\omega_{1}},2^{\omega_{2}+\omega_{1}-\omega_{4}}),$

which satisfies the condition in Lemma 13 or 12, by Eq. (4), so again
$d^{\prime}$ has a 2PBE realization $G^{\prime}$. Notice that for
$\omega^{\prime}_{2}=\omega_{2}+\omega_{1}-\omega_{4}\geq 2$,
$d^{\prime}_{1}\leq n^{\prime}-1$.

Finally, we obtain a 2PBE realization $G$ for $d$ by taking $G^{\prime}$ and
connecting $\omega_{1}$ new degree 1 vertices with degree 3 or 2 in
$G^{\prime}$. By above construction of $G$, one page is outerplanar and the
other page consists of at most two edges. The lemma follows. ∎

Combining Lemmas 12, 13 and 14, we have the following theorem.

######  Theorem 15.

Let $d\in\mathcal{D}_{\leq 4}$ and $d_{1}\leq n-1$. Then $d$ has an OP+2
realization.

###  4.2 A 2PBE realization for sequences with $d_{1}\geq 5$

In this section, we analyze the subclass $\mathcal{D}_{\geq
5}=\mathcal{D}\setminus\mathcal{D}_{\leq 4}$ of sequences whose largest degree
satisfies $d_{1}\geq 5$. We first consider the special case of _maximal-
volume_ sequences in $\mathcal{D}_{\geq 5}$, namely, ones whose volume equals
exactly $4n-6$. By Lemma 4, $\omega_{1}=0$. Combining this with Lemma 3,
$\omega_{2}\geq 2$. Since Lemma 9 has already considered the case for
$\omega_{2}=2$, it remains to consider sequences $d$ where $\omega_{2}>2$.
This class of sequences turns out to be the most challenging. Their
characterization is covered by the next key lemma, whose proof is by far the
most complex part of our analysis.

######  Lemma 16.

Let $d\in\mathcal{D}_{\geq 5}$. If  (1) $\sum d=4n-6$,  (2)
$2\omega_{2}+\omega_{3}\leq n+1$,  (3) $\omega_{2}>2$, and  (4) $d_{n}=2$,
Then $d$ has an OP+bi realization.

$v_{\pi(1)}$$v_{\pi(2)}$$v_{\pi(3)}$$v_{\pi(4)}$$v_{\pi(5)}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$
Figure 6: Illustration for the way in which the graph $G^{\prime}$ constructed
in the proof of Case A of Lemma 16 can be embedded into the page of a book.
The blue rectangles are B’s vertices. In the example, $j=4$. Figure 7:
Illustration of the construction of $Bar(A,B)$. The black edges represent the
matching between $A_{1}$ and $B_{1}$. The green edges represent the union of
disjoint stars between $B_{2}$ and $A_{1}$. The red edges represent the zigzag
path between $A_{2}$ and $B_{2}$
$v_{\pi(1)}$$v_{\pi(2)}$$a_{2}$$v_{\pi(3)}$$a_{3}$$v_{\pi(4)}$$v_{\pi(5)}$$a_{5}$$v_{\pi(6)}$$v_{\pi(7)}$$v_{\pi(8)}$$a_{8}$$v_{\pi(9)}$$a_{9}$
Figure 8: The graph $G^{\prime}$ after the first step of the construction.
Throughout our illustration figures, vertices of $A_{1}$ (respectively, $B$)
are colored red (resp., blue). Vertices of $A_{1}$, $B_{1}$ (resp., $A_{2}$,
$B_{2}$) are circular (resp., rectangular). Figure 9: The situation before
Step 2. Vertices of $A$ (respectively, $B$) are colored red (resp., blue).
Vertices of $A_{1}$ and $B_{1}$ (respectively, $B_{2}$) are depicted as
circles (resp., rectangles). The free ports of a vertex are depicted as tags
attached to it. In this example, the $d^{\prime}$ degrees of the vertices of
$B_{2}$ are $d^{\prime}(v_{1})=3$, $d^{\prime}(v_{2})=4$,
$d^{\prime}(v_{2})=6$ and $d^{\prime}(v_{4})=3$. The ports of $B_{2}$ and
$A_{1}$ vertices that have to be connected in a non-intersecting way
correspond to the input sequences of the example in Figure 4. This is done
using Algorithm BBB of Section 2.  Figure 10: The connections obtained by
Algorithm BBB for the ports of $B_{2}$ and $A_{1}$. Figure 11: Illustration of
Algorithm 2, which transforms the crossing edges to be noncrossing. (a) The
graph obtained after placing the vertices of $A_{2}$ in the first part of step
3. In this graph, the edge $(v_{\pi(k_{i})},a_{q-\ell+i+1})$ crosses the edges
$(N^{\prime}(a_{i^{\prime}+1}),a_{i^{\prime}+1})$ and
$(N^{\prime}(a_{i^{\prime}}),a_{i^{\prime}})$. (b) The resulting graph after
the transformation. The three edges involvesd in the crossings are replaced by
the edges
$(v_{\pi(k_{i})},a_{i^{\prime}}),(N^{\prime}(a_{i^{\prime}+1}),a_{q-\ell+i+1}),(N^{\prime}(a_{i^{\prime}}),a_{i^{\prime}+1})$.
Figure 12: The graph after Algorithm 2 based on Figure 10. The purple squares
represent the vertices in $A_{2}$. The orange edges represent the modified
edges based on Figure 10. $v$$u$$w$ Figure 13: The black squares represent the
added vertices $u,w$ and they are connected to $v$.

###### Proof.

Let $d$ be as in the lemma. To prove the claim, we define sequences
$d^{\prime},d^{\prime\prime}$, of lengths $n^{\prime},n^{\prime\prime}$
respectively, such that $d=d^{\prime}\oplus d^{\prime\prime}$.

Intuitively, it would appear that if property (1) of the lemma holds, then
$d^{\prime}$ and $d^{\prime\prime}$ can be defined such that $\sum
d^{\prime}=2n^{\prime}-4$ and $\sum d^{\prime\prime}=2n^{\prime\prime}-2$, so
both $d^{\prime}$ and $d^{\prime\prime}$ can be realized by a forest and
embedded on its own page, implying a 2-page book embedding. Proving this
intuition is complicated by the need to ensure two properties:  (a) that no
edge $(u,w)$ occurs in _both_ pages, and  (b) that the vertices occur in the
same order on the outer face of both pages.

Instead, we select the sequence $d^{\prime\prime}$ (ignoring the $0$-degrees)
so that it meets the preconditions of Lemma 9, i.e., $d^{\prime\prime}$
satisfies  (i) $\omega^{\prime\prime}_{2}=2$,  (ii)
$d^{\prime\prime}_{n^{\prime\prime}}=2$, and  (iii) $d"\in\mathcal{D}$,
namely, $\sum d^{\prime\prime}\leq 4n^{\prime\prime}-6$ and $\sum
d^{\prime\prime}$ is even.  Then, Lemma 9 provides an outerplanar realization
$G^{\prime\prime}$ of $d^{\prime\prime}$ and its embedding fills the first
page of the book. The embedding of $G^{\prime\prime}$ imposes an ordering on
the vertices, as they appear along the spine of the book (which is the same
ordering as on the outer-cycle of the embedding). For the second page, we
construct an outerplanar realization $G^{\prime}$ of $d^{\prime}$ such that
the vertices follow the same ordering along the book spine. To obtain
$d^{\prime\prime}$, we apply the following two transformations to $d$.

(TR1)

remove $q:=\omega_{2}-2$ degree-2 entries from $d$ to meet requirement (i).

(TR2)

decrease the total volume of the remaining sequence by $2q$ to satisfy
requirement (iii), while carefully avoiding the creation of new degrees $1$ or
$2$.

Denote the number of degrees that are $5$ or more by $\ell:=$$\sum_{i\geq
5}\omega_{i}=n-\omega_{2}-\omega_{3}-\omega_{4}$. The remaining proof,
describing the construction of $G^{\prime}$ for $d^{\prime}$, is split into
two cases, depending on the relation between $q$ and $\ell$.

#### Case A:

$q<\ell$. In this easier case, a path sequence
$d^{\prime}=(2^{n^{\prime}-2},1^{2})$ is a suitable choice, and the
construction of $G^{\prime}$ is simplified considerably.

We define the sequence $d^{\prime}$ to have length $n^{\prime}=n$. It contains
vertices of degree $0$ and we do _not_ consider it in non-increasing order, to
satisfy the constraint $d=d^{\prime}\oplus d^{\prime\prime}$. Once
$d^{\prime}$ is defined, $d^{\prime\prime}$ is implicitly defined as well, as
$d^{\prime\prime}=d\ominus d^{\prime}$. It can be regarded as having length
$n^{\prime\prime}=n$ where $d^{\prime\prime}_{i}=0$ if $i>n-q$.

$\displaystyle d_{i}^{\prime}$ $\displaystyle=\begin{cases}1,&\text{ if
}i=1,\\\ 2,&\text{ if }i=2,\ldots,q,\\\ 1,&\text{ if }i=q+1,\\\ 0,&\text{ if
}i=q+2,\ldots,n-q,\\\ 2,&\text{ if }i=n-q+1,\ldots,n.\end{cases}$
$\displaystyle d_{i}^{\prime\prime}$
$\displaystyle=\begin{cases}d_{i}-1,&\text{ if }i=1,\\\ d_{i}-2,&\text{ if
}i=2,\ldots,q,\\\ d_{i}-1,&\text{ if }i=q+1,\\\ d_{i},&\text{ if
}i=q+2,\ldots,n-q,\\\ 0,&\text{ if }i=n-q+1,\ldots,n.\end{cases}$

We use the sequence $d=(6^{2},5^{4},4,3^{2},2^{6})$ as a running example for
Case A. In this case, $n=15$, $q=4$, and $\ell=6$. It is not hard to verify
that $d$ satisfies the conditions of this lemma and the condition of Case A.
We have that $d^{\prime}=(1,2^{3},1,0^{2},2^{4})$,
$d^{\prime\prime}=(5,4,3^{2},4,5,4,3^{2},2^{2},0^{4})$.

For the next step, consider
$\hat{d}=(d^{\prime\prime}_{1},d^{\prime\prime}_{2},\ldots,d^{\prime\prime}_{n-q})$,
which is $d^{\prime\prime}$ without the trailing $0$ degrees. In the above
example, we have that $\hat{d}=(5^{2},4^{3},3^{4},2^{2})$. For this $\hat{d}$,
whose length is $\hat{n}=n-q$, we show the following.

######  Claim 1.

Sequence $\hat{d}$ satisfies the preconditions of Lemma 9.

###### Proof.

By construction of $d^{\prime\prime}$, we have that $\sum\hat{d}=\sum d"$ is
even, and that $\hat{d}_{\hat{n}}=d^{\prime\prime}_{n-q}=2$. Observe that
$\hat{\omega}_{2}=\omega^{\prime\prime}_{2}=2$ as $q<\ell$ implies that
$d_{q+1}\geq 5$. To complete the proof, observe that

$\sum\hat{d}=\sum d-4q\leq 4n-6-4q=4(n-q)-6=4\hat{n}-6.\mbox{\hskip
56.9055pt}\Box$

∎

By Lemma 9, $\hat{d}$ can be realized as the outerplanar graph $\hat{G}$. (For
our example, this graph is given in Figure 14.) We add $q$ isolated vertices
to $V(\hat{G})$ to generate an outerplanar realization
$G^{\prime\prime}=(V,E^{\prime\prime})$ of $d^{\prime\prime}$. Let
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ such that
$\deg_{G^{\prime\prime}}(v_{i})=d^{\prime\prime}_{i}$, for $i=1,2,\ldots,n$.
Hence, the set $R:=\\{v_{n-q+1},\ldots,v_{n}\\}$ contains the isolated
vertices of degree $0$. Consider an outerplanar embedding of $\hat{G}$, and
note that the isolated vertices in $R$ can be placed in arbitrary positions on
the cyclic order to yield a planar embedding of $G^{\prime\prime}$.

$v_{\pi(1)}$$v_{\pi(2)}$$v_{\pi(3)}$$v_{\pi(4)}$$v_{\pi(5)}$ Figure 14: The
graph realizing $\hat{d}$. Blue circles: vertices in $B$. Green circles:
vertices in $V(\hat{G})\setminus B$.

Let $B:=\\{v_{1},v_{2},\ldots,v_{q+1}\\}$ be the set of vertices whose degrees
were reduced in $d^{\prime\prime}$ compared to the original $d$ and whose
original degree is at least 5. Let $\pi$ be the permutation by which the
vertices of $B$ appear in the cyclic-order defined by the planar embedding of
$G^{\prime\prime}$. Without loss of generality, let $\pi(1)=1$. Hence, there
is an embedding of $G^{\prime\prime}$ into the page of a book where the
vertices in $B$ are arranged along the spine in the order
$(v_{\pi(1)},v_{\pi(2)},\ldots,v_{\pi(q+1)})$. The vertices in $R$ can be
placed arbitrarily along the spine.

In our example $\hat{G}$, $B=\\{v_{1},\ldots,v_{5}\\}$, and its vertices are
arranged in the outer-cycle in the order $v_{\pi_{1}},\ldots,v_{\pi_{5}}$, as
depicted in Figure 14.

To finish the proof of case A, construct a realization
$G^{\prime}=(V,E^{\prime})$ of $d^{\prime}$ such that
$\deg_{G^{\prime}}(v_{i})=d^{\prime}_{i}$, for $i=1,2,\ldots,n$. The vertices
$v_{q+2},\ldots,v_{n-q}$ have vertices of degree $0$ in $G^{\prime}$ and are
ignored when constructing $G^{\prime}$. The vertices in $R$ must have degree
$2$ in $G^{\prime}$. In the embeddings of $G^{\prime\prime}$ and $G^{\prime}$,
we place vertex $v_{n-q+i}$ between $v_{\pi(i)}$ and $v_{\pi(i+1)}$ along the
spine, for $i=1,\ldots,q$. Let index $j$ be such that
$d^{\prime\prime}_{\pi(j)}=d_{q+1}-1$. For every $i=1,\ldots$, $\pi(j)-2$,
$\pi(j)$, $\pi(j)+1,\ldots$, $q$, add to $G^{\prime}$ the two edges
$(v_{\pi(i)},v_{n-q+i})$ and $(v_{n-q+i},v_{\pi(i+1)})$. Finally, add the
edges $(v_{\pi(j)-1},v_{n-q+j})$ and $(v_{n-q+j},v_{q+1})$.

By construction, $V(G^{\prime\prime})=V(G^{\prime})$. By definition of
$d^{\prime}$ and $d^{\prime\prime}$, it follows that
$\deg_{G^{\prime}}(v_{i})+\deg_{G^{\prime\prime}}(v_{i})=d_{i}$ for
$i=1,2,\ldots,n$. The vertices in $B\cup R$ form a path in $G^{\prime}$ where
$v_{1}$ and $v_{\pi(j)}$ are the two ends (vertices of degree $1$). Finally,
observe that $E^{\prime\prime}\cap E^{\prime}=\emptyset$ since each edge of
$G^{\prime}$ is incident to a vertex in $R$, which has vertices of degree 0 in
$G^{\prime\prime}$. It follows that $G^{\prime\prime}$ and $G^{\prime}$ form a
valid book embedding of a graph that realizes $d$. Notice that $G^{\prime}$ is
bipartite outerplanar and $G^{\prime\prime}$ is an outerplanar graph.

Notice that in our example $v_{\pi(1)}=v_{1}$, $v_{\pi(2)}=v_{3}$,
$v_{\pi(3)}=v_{4}$, $v_{\pi(4)}=v_{2}$, $v_{\pi(5)}=v_{5}$. Then in
$G^{\prime}$, $d^{\prime}(v_{\pi(1)})=1$,
$d^{\prime}(v_{\pi(2)})=d^{\prime}(v_{\pi(3)})=d^{\prime}(v_{\pi(4)})=2$,
$d^{\prime}(v_{\pi(5)})=1$, $R=\\{u_{1},\ldots,u_{q}\\}$. Figure 6 shows a
valid embedding of $G^{\prime}$ into the page of a book. This completes the
proof of Case A.

#### Case B:

$q\geq\ell$. This case is significantly more complicated than case A. Note
that as $2\omega_{2}+\omega_{3}\leq n+1$, it follows that

$\omega_{4}=n-\omega_{2}-\omega_{3}-\ell\geq\omega_{2}-1-\ell=q+1-\ell>0~{}.$

Also note that $w_{4}+\ell\geq q+1$.

The construction generalizes that of case A. Similar to case A, we obtain
sequence $d^{\prime\prime}$ from $d$ by removing $q=\omega_{2}-2$ vertices of
degree $2$. The next steps, though, are more complicated than in case A. The
reason is that, if we set (like above) $d^{\prime\prime}_{i}=d_{i}-2$, for
$i=2,3,\ldots,q$, then some vertices of degree $4$ in $d$ are decreased to $2$
in $d^{\prime\prime}$ and requirement (i), $\omega^{\prime\prime}_{2}=2$,
might not be met.

Instead, the sequences $d^{\prime}$ and $d^{\prime\prime}$ have to be defined
differently. In particular, to define $d^{\prime\prime}$, we reduce only the
degrees that are _larger_ than $4$ by $2$ (or more), and we reduce $q-\ell+1$
vertices of degree $4$ to $3$. At first, let sequence $\bar{d}$ be such that

$\bar{d}_{i}=\begin{cases}d_{i}-2,&\text{ if
}i=1,\ldots,\ell,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\text{where
}d_{i}\geq 5)\\\ d_{i}-1,&\text{ if
}i=\ell+1,\ldots,q+1~{}~{}~{}~{}~{}(\text{where }d_{i}=4)\\\ d_{i},&\text{ if
}i=q+2,\ldots,n-q,~{}~{}~{}(\text{where }4\geq d_{i}\geq 2)\\\ 0,&\text{ if
}i=n-q+1,\ldots,n.~{}~{}~{}(\text{where }d_{i}=2)\end{cases}$

Recall that $d$ satisfies $w_{4}+\ell\geq q+1$, which implies that
$d_{q+1}\geq 4$ and therefore $\bar{d}_{q+1}\geq 3$. As $q=\omega_{2}-2$ out
of the $\omega_{2}$ vertices of degree $2$ of $d$ are transformed to $0$, it
follows that $\bar{\omega}_{2}=2$.

Note that $\sum\bar{d}\leq 4(n-q)-6$ is not guaranteed, so requirement (iii)
does not necessarily hold. However, observe that $\sum\bar{d}=\sum
d-2(\ell+q)-(q-\ell+1)$, so

$\sum\bar{d}=\sum d-2(\ell+q)-(q-\ell+1)=4n-6-3q-\ell-1=4(n-q)-6+(q-\ell-1)$
(5)

does hold. To meet requirement (iii) of Lemma 9, we set
$d^{\prime\prime}=\bar{d}$ and gradually reduce
$\sum_{i=1}^{\ell}d^{\prime\prime}_{i}$ further by decreasing the large
degrees using Algorithm 1.

1 Set $d^{\prime\prime}\leftarrow\bar{d}$

2 while  _$\sum d^{\prime\prime} >4(n-q)-6$_ do

3 $d^{\prime\prime}_{j}\leftarrow d^{\prime\prime}_{j}-1$, where
$j=\text{argmax}_{i\in[\ell]}~{}d^{\prime\prime}_{i}$

4

$\hat{d}\leftarrow\mbox{\sf pos}(d^{\prime\prime})$.

Algorithm 1 Generating sequence $d^{\prime\prime}$ from $\bar{d}$.

Note that the output
$\hat{d}=(d^{\prime\prime}_{1},d^{\prime\prime}_{2},\ldots,d^{\prime\prime}_{n-q})$
of Algorithm 1 is the prefix of length ${\hat{n}}=n-q$ of the sequence
$d^{\prime\prime}$ at the end of Algorithm 1, omitting the trailing zeros.

######  Claim 2.

The sequence $\hat{d}$ satisfies the preconditions of Lemma 9.

###### Proof.

Requirement (iii) holds by construction. Note that when constructing $\bar{d}$
we reduced $2\ell$ from the volume of the “high” (first $\ell$) elements,
$\sum_{i=1}^{\ell}d_{i}$. Algorithm 1 reduces this volume further by
$(q-\ell-1)$. To show that $\hat{d}$ satisfies requirements (i) and (ii), it
suffices to show that the “high” degrees $d_{1},d_{2},\ldots,d_{\ell}$ have
sufficient volume so that $d^{\prime\prime}_{i}\geq 3$ for $i\leq\ell$, i.e.,
it remains to prove that $\sum_{i=1}^{\ell}(\bar{d}_{i}-3)\geq q-\ell-1$.

Recall that $\sum d=4n-6$, which can be rewritten as

$\sum_{i=1}^{\ell}(\bar{d}_{i}-3)=\sum_{i=1}^{\ell}(d_{i}-5)=4n-6-(4\omega_{4}+3\omega_{3}+2\omega_{2})-5\ell=n-6-\omega_{4}+\omega_{2}-2\ell$
(6)

By assumption (3) of the lemma, $\omega_{2}>2$, hence also
$\omega_{3}+\omega_{2}\geq 3$, which can be written equivalently as
$n-\omega_{4}-3\geq\ell$. Equation (6), hence
$\sum_{i=1}^{\ell}(\bar{d}_{i}-3)\geq\omega_{2}-\ell-3=q-\ell-1$, and the
claim follows. ∎

Concluding that Lemma 9 applies, and noting that by construction
$\sum{\hat{d}}=4{\hat{n}}-6$, it follows that $\hat{d}$ is maximal
outerplanaric. Let $\hat{G}$ be a a maximal outerplanar realization of
$\hat{d}$. We add $q$ isolated vertices to $V(\hat{G})$ to generate an
outerplanar realization $G^{\prime\prime}=(V,E^{\prime\prime})$ of
$d^{\prime\prime}$. Let $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ such that
$\deg_{G^{\prime\prime}}(v_{i})=d^{\prime\prime}_{i}$, for $i=1,2,\ldots,n$.
Hence, the set $A:=\\{v_{n-q+1},\ldots,v_{n}\\}$ contains the isolated
vertices of degree $0$ in $G^{\prime\prime}$. For ease of notation, we relabel
the vertices $a_{i}:=v_{n-q+i}$, for $i=1,\ldots q$. Consequently,

$A~{}=~{}\\{a_{1},\ldots,a_{q}\\}=\\{v_{n-q+1},\ldots,v_{n}\\}~{}.$

Consider an outerplanar embedding of $\hat{G}$. Let $\pi$ be the permutation
by which the vertices of $B:=\\{v_{1},v_{2},\ldots,v_{q+1}\\}$ appear on the
cyclic-order defined by the planar embedding of $G^{\prime\prime}$. Without
loss of generality, let $\pi(1)=1$. It follows that $G^{\prime\prime}$ has an
embedding into a book page where the vertices of $B$ are arranged along the
spine according to $\pi$. The vertices in $A$ can be placed freely along the
spine without interfering with the embedding of $G^{\prime\prime}$.

Note that unlike in case A, here we did not define the sequence
$d^{\prime\prime}$ explicitly, so the sequence $d^{\prime}$ too is not defined
explicitly, but rather is determined as $d^{\prime}:=d\ominus
d^{\prime\prime}$.

To complete the proof, we construct an outerplanar realization
$G^{\prime}=(V^{\prime},E^{\prime})$ of $d^{\prime}$ such that $V^{\prime}=V$
and $\deg_{G^{\prime}}(v_{i})=d^{\prime}_{i}$, for $i=1,2,\ldots,n$. Only the
vertices in $A$ and $B$ need to be connected in $G^{\prime}$. Partition the
vertices in $B$ into the sets

$\displaystyle B_{1}$ $\displaystyle=\\{v_{\ell+1},\ldots,v_{q+1}\\}$ and
$\displaystyle B_{2}$ $\displaystyle=\\{v_{1},\ldots,v_{\ell}\\}.$

Note that $d^{\prime}_{i}=1$ for $v_{i}\in B_{1}$, and $d^{\prime}_{i}\geq 2$
for $v_{i}\in B_{2}$, and that $d^{\prime}_{i}=2$ for every $v_{i}\in A$.
$G^{\prime}$ and its book embedding are constructed simultaneously. The
vertices in $B$ are arranged according to $\pi$ along the book spine. Hence,
vertices of $B_{1}$ and $B_{2}$ may appear in any order and vertices in $A$
can be placed freely between them. Since vertices in $A$ have degree $0$ in
$G^{\prime\prime}$, it follows that $E^{\prime\prime}\cap
E^{\prime}=\emptyset$, which is necessary for $G^{\prime}$ and
$G^{\prime\prime}$ to form a valid book embedding of a simple graph (rather
than a multigraph).

It is essential that each edge in $E^{\prime}$ is incident to one vertex in
$A$ and one vertex in $B$, i.e., $G^{\prime}$ is a bipartite graph with parts
$A$ and $B$. Partition $A$ into $A_{1}\cup A_{2}$, where
$|A_{1}|=|B_{1}|=q-\ell+1$ and $|A_{2}|=|B_{2}|-1=\ell-1$. Specifically, let

$\displaystyle A_{1}$ $\displaystyle=\\{a_{1},\ldots,a_{q-\ell+1}\\}$ and
$\displaystyle A_{2}$ $\displaystyle=\\{a_{q-\ell+2},\ldots,a_{q}\\}.$

The relationship between the volume of $B_{2}$ and the cardinalities of
$A_{2}$ and $A_{1}$ is established in the following claim, which helps to show
that $G^{\prime}$ is bipartite.

######  Claim 3.

$\sum_{i=1}^{\ell}d^{\prime}_{i}=2|A_{2}|+|A_{1}|$.

###### Proof.

Notice that $\sum_{i=1}^{\ell}d^{\prime}_{i}$ consists of two parts. One comes
from the decrease from $d$ to $\bar{d}$ on the elements of $B_{2}$, and is
equal to $2\ell$; the other part comes from the decreases of
$d^{\prime\prime}$ on the elements of $B_{2}$ in Algorithm 1, and is equal to
$q-\ell-1$ by (5). Also recall that $|A_{1}|=q-\ell+1$ and $|A_{2}|=\ell-1$.
It follows that
$\sum_{i=1}^{\ell}d^{\prime}_{i}=2\ell+(q-\ell-1)=2(\ell-1)+q-\ell+1=2|A_{2}|+|A_{1}|$.
∎

By 3, there is a bipartite graph $Bar(A,B)$ between $A$ and $B$, defined as
follows.

  1. 1.

Connect a matching between $B_{1}$ and $A_{1}$;

  2. 2.

Connect the vertices of $B_{2}$ to the vertices of $A_{1}$ by constructing a
union of disjoint stars, with $v_{1}$ connected to $d^{\prime}(v_{1})-1$
vertices in $A_{1}$, $v_{i}$ connected to $d^{\prime}(v_{i})-2$ vertices in
$A_{1}$ for $2\leq i\leq\ell-1$, and $v_{\ell}$ connected to
$d^{\prime}(v_{\ell})-1$ vertices in $A_{1}$;

  3. 3.

Construct a path $v_{1}-a_{q-\ell+2}-v_{2}-\ldots-a_{q}-v_{\ell}$ zigzagging
between $A_{2}$ and $B_{2}$.

The Figure 7 illustrates the structure of $Bar(A,B)$.

One can easily verify that assuming no restrictions on the ordering of the
vertices, it is possible to find an outerplanar embedding of $Bar(A,B)$ in the
plane. The only remaining obstacle is that the embedding must obey the
ordering $\pi$ dictated for the vertices of $B$ by the graph
$G^{\prime\prime}$. The remainder of the proof concerns finding an outerplanar
embedding obeying this ordering.

The construction of $G^{\prime}$ consists of three steps corresponding to
those of the construction of $Bar(A,B)$. First, construct a matching between
$A_{1}$ and $B_{1}$. Next, construct disjoint stars between $B_{2}$ and
$A_{1}$. Finally, construct the path between $A_{2}$ and $B_{2}$.

Our starting point is the spine defined for $G^{\prime\prime}$, consisting of
the vertices of $B$. This spine dictates the order of the $B$ vertices, which
in turn dictate the bipartite $A$-$B$ connections in the constructed graph
$G^{\prime}$. It is convenient to separate the indices of $B_{1}$ and $B_{2}$.
Let $(h_{1},\ldots,h_{q-\ell+1})$ denote the increasing sequence of indices
$\\{i~{}\mid~{}v_{\pi(i)}\in B_{1}\\}$, let $(k_{1},\ldots,k_{\ell})$ denote
the increasing sequence of indices $\\{i~{}\mid~{}v_{\pi(i)}\in B_{2}\\}$. The
placement of the $A_{1}$ (respectively, $A_{2}$) vertices on the spine is
fixed in Step 1 (resp., Step 3) based on these positions of the $B_{1}$
(resp., $B_{2}$) vertices.

In the first step, place one vertex of $A_{1}$ next to each vertex of $B_{1}$
in the embedding of $G^{\prime}$ (and $G$) and connect them. We place $a_{i}$
to the right of $v_{\pi(h_{i})}$, for $i=1,\ldots,q-\ell+1$, and add the edge
$(a_{i},v_{\pi(h_{i})})$ to $E^{\prime}$. See Figure 8 for an illustration.

Note that after step 1, each of the vertices in $A_{1}$ is still one edge
short, while each of the vertices in $A_{2}:=A\setminus A_{1}$ is still
missing two edges. The goal of step 2 is to handle the remaining shortages of
the vertices of $A_{1}$ by connecting them to the vertices of $B_{2}$. Towards
that, we partition the vertices in $A_{1}$ into subsets of vertices that fall
in the gaps between consecutive vertices of $B_{2}$. Formally, define
$A_{1}^{i}=\\{a_{j}\in A_{1}~{}:~{}k_{i}<j<k_{i+1}\\}$, for $i=1,\ldots,\ell$,
as the vertices of $A_{1}$ that appear between $v_{\pi(k_{i})}$ and
$v_{\pi(k_{i+1})}$ along the spine. Consider Figure 8 where $k_{1}=1$,
$k_{2}=4$, and $A_{1}^{1}=\\{2,3\\}$.

For the second step, we make use of the following tool.

In the second step towards building the graph $G^{\prime}$, we connect
vertices of $B_{2}$ to the vertices of $A_{1}$ by using the bipartite bracket
balancing algorithm BBB. This is done as follows. Let $P=A_{1}$. For the other
side, identify with every vertex $v_{\pi(k_{i})}\in B_{2}$ a sequence of
$s_{i}$ _“ports”_ , or connection points, $\langle
v_{\pi(k_{i})}^{1},\ldots,v_{\pi(k_{i})}^{s_{i}}\rangle$, where

$s_{i}~{}=~{}d^{\prime}(v_{\pi(k_{i})})-\begin{cases}1,&i=1,\\\ 2,&2\leq
i\leq\ell-1,\\\ 1,&i=\ell,\end{cases}$

and let $Q$ be the union of those sets, i.e., the set of all resulting ports,

$Q=\langle v_{\pi(k_{1})}^{1},\ldots
v_{\pi(k_{1})}^{s_{1}},v_{\pi(k_{i})}^{1},\ldots,v_{\pi(k_{i})}^{s_{i}},\ldots,v_{\pi(k_{\ell})}^{1},\ldots,v_{\pi(k_{\ell})}^{s_{\ell}}\rangle.$

The ordering of the merged set $R$ is dictated by the order of the vertices of
$A_{1}$ and $B_{2}$ on the spine. Figure 9 illustrates the transformation to
the instance of Bipartite Bracket Balancing problem.

After applying Algorithm BBB to this input, transform its output into a
collection of edges on our original graph as follows. For each $1\leq
i\leq\ell$, merge the $s_{i}$ “ports” corresponding to $v_{\pi(k_{i})}$ into
the point $v_{\pi(k_{i})}$ and change all the edges that are incident to those
$s_{i}$ “ports” to be incident to $v_{\pi(k_{i})}$. This yields an outerplanar
graph $\bar{G}^{\prime}$. Figure 10 illustrates the resulting graph after
applying the algorithm.

After the construction of $\bar{G}^{\prime}$, the end vertices
$v_{\pi(k_{1})}$ and $v_{\pi(k_{\ell})}$ of $B_{2}$ are still missing one edge
each, and the vertices $v_{\pi(k_{i^{\prime}})}$ for $2\leq i^{\prime}\leq
k_{\ell-1}$ are still missing two edges each. Our third step involves
spreading the $A_{2}$ vertices between the $B_{2}$ vertices. Each $A_{2}$
vertex is placed between two consecutive $B_{2}$ vertices (according to
$\pi$). Specifically, we place $a_{q-\ell+1+i}$ between $v_{\pi(k_{i})}$ and
$v_{\pi(k_{i+1})}$ for $i\in[\ell-1]$, and construct the path

$v_{\pi(k_{1})}-a_{q-\ell+2}-v_{\pi(k_{2})}-a_{q-\ell+3}-\ldots
a_{q}-v_{\pi(k_{\ell})}.$

There are two difficulties involved in performing this step. The first
concerns determining the exact position in which the vertex $a_{q-\ell+1+i}$
should be placed between $v_{\pi(k_{i})}$ and $v_{\pi(k_{i+1})}$. The second
is the need to eliminate possible crossings of edges after adding the path
above.

Let $N_{\bar{G}^{\prime}}(v)=\\{v^{\prime}~{}\mid~{}(v,v^{\prime})\in
E(\bar{G}^{\prime})\\}$ for any $v\in V$. To handle the first difficulty,
$a_{q-\ell+1+i}$ should be placed between two vertices $v$ and $v^{\prime}$ in
$A_{1}^{i}\cup\\{v_{\pi(k_{i})},v_{\pi(k_{i+1})}\\}$ such that the point $v$
to the left of $a_{q-\ell+1+i}$ satisfies that any vertex in
$N_{\bar{G}^{\prime}}(v)$ is to the left of $v$, and the point $v^{\prime}$ to
the right of $a_{q-\ell+1+i}$ satisfies that any vertex in
$N_{\bar{G}^{\prime}}(v^{\prime})$ is to the left of $v^{\prime}$. As shown in
Figure 11, $a_{q-\ell+1+i}$ is placed between $a_{i^{\prime}+1}$ and
$v_{\pi(k_{i+1})}$ since $a_{i^{\prime}+1}$ has all its neighbors on its left
and $v_{\pi(k_{i+1})}$ has all its neighbors on its right.

To handle the second difficulty, we first present some notations. The set
$E_{le}^{i}$ (respectively, $E_{ri}^{i}$) contains edges connecting a vertex
$v_{\pi(j)}$, for $j<i$ (resp., $j>i+1$) to a vertex in $A_{1}^{i}$. Formally,

$\displaystyle E_{le}^{i}$ $\displaystyle=$
$\displaystyle\\{(v_{\pi(k_{j^{\prime}})},a_{j})\in
E(\bar{G}^{\prime})~{}\mid~{}j^{\prime}<i,~{}a_{j}\in A_{1}^{i}\\},$
$\displaystyle E_{ri}^{i}$ $\displaystyle=$
$\displaystyle\\{(v_{\pi(k_{j^{\prime}})},a_{j})\in
E(\bar{G}^{\prime})~{}\mid~{}j^{\prime}>i+1,~{}a_{j}\in A_{1}^{i}\\}.$

As shown in Figure 11,
$E_{le}^{i}=\\{(N^{\prime}(a_{i^{\prime}}),a_{i^{\prime}}),(N^{\prime}(a_{i^{\prime}+1}),a_{i^{\prime}+1})\\}$
and $E_{ri}^{i}=\emptyset$. Note that $N^{\prime}(a_{i^{\prime}})$ is equal to
$v_{\pi(k_{j^{\prime}})}$ with some $j^{\prime}<i$. Similar result can apply
for $N^{\prime}(a_{i^{\prime}+1})$. When adding edges
$(v_{\pi(k_{i})},a_{q-\ell+i+1})$ and $(a_{q-\ell+i+1},v_{\pi(k_{i+1})})$,
they may cross the existing edges in $\bar{G}^{\prime}$. The following steps
of Algorithm 2 eliminate the problem by replacing the set of crossing edges
with noncrossing set of edges while preserving the vertex degrees.

Edge crossing happens when $E_{le}^{i}\neq\emptyset$ in line 2 or
$E_{ri}^{i}\neq\emptyset$ in line 2. Notice that the right (respectively left)
endpoints of edges in $E_{le}^{i}$ (respectively $E_{ri}^{i}$) are in
consecutive order by Algorithm BBB. Let the set of the right endpoints of
edges in $E_{le}^{i}$ be
$\\{a_{i^{\prime}},\ldots,a_{i^{\prime}+\ell^{\prime}}\\}$ with
$\ell^{\prime}=|E_{le}^{i}|-1$. Similarly, let the set of the left endpoints
of edges in $E_{ri}^{i}$ be
$\\{a_{i^{\prime\prime}},\ldots,a_{i^{\prime\prime}+\ell^{\prime\prime}}\\}$
with $\ell^{\prime\prime}=|E_{ri}^{i}|-1$. Since $N_{\bar{G}^{\prime}}(v)$
consists only one element for any
$v\in\\{a_{i^{\prime}},\ldots,a_{i^{\prime}+\ell^{\prime}},a_{i^{\prime\prime}},\ldots,a_{i^{\prime\prime}+\ell^{\prime\prime}}\\}$,
let $N^{\prime}(v)$ refer to the only element in $N_{\bar{G}^{\prime}}(v)$. In
the case where $E_{le}^{i}\neq\emptyset$, the edge
$(v_{\pi(k_{i})},a_{q-\ell+i+1})$ crosses all the edges in $E_{le}^{i}$. The
correction process exchanges the right endpoints of edges in
$E_{le}^{i}\cup\\{(v_{\pi(k_{i})},a_{q-\ell+i+1})\\}$ such that there are no
cross edges. In the other case, where $E_{ri}^{i}\neq\emptyset$,
$(a_{q-\ell+i+1},v_{\pi(k_{i+1})})$ crosses all the edges in $E_{ri}^{i}$. The
correction process is similar to that of $E_{le}^{i}\neq\emptyset$.

Figure 11 illustrates the correction process between $v_{\pi(k_{i})}$ and
$v_{\pi(k_{i+1})}$ for the case where $E_{le}^{i}\neq\emptyset$. Figure 12
illustrates the corrected graph following the entire correction process
performed by applying Algorithm 2, based on Figure 10.

input : outerplanar graph $\bar{G^{\prime}}$ obtained from the second step

output : an outerplanar graph $G^{\prime}$

1 forall  _$i\in[\ell-1]$_ do

2 Put $a_{q-\ell+i+1}$ between two vertices $v$ and $v^{\prime}$ in
$A_{1}^{i}\cup\\{v_{\pi(k_{i})},v_{\pi(k_{i+1})}\\}$ such that the point $v$
to the left of $a_{q-\ell+1+i}$ satisfies that any vertex in
$N_{\bar{G}^{\prime}}(v)$ is to the left of $v$, and the point $v^{\prime}$ to
the right of $a_{q-\ell+1+i}$ satisfies that any vertex in
$N_{\bar{G}^{\prime}}(v^{\prime})$ is to the left of $v^{\prime}$.

3 Connect $(v_{\pi(k_{i})},a_{q-\ell+i+1}),(a_{q-\ell+i+1},v_{\pi(k_{i+1})})$

4 if  _$E_{le}^{i}\neq\emptyset$_ then

5 Delete all the edges in $E_{le}^{i}$ and $(v_{\pi(k_{i})},a_{q-\ell+i+1})$

6 Connect
$(N^{\prime}(a_{i^{\prime}+\ell^{\prime}}),a_{q-\ell+i+1}),(N^{\prime}(a_{i^{\prime}+\ell^{\prime}-1}),a_{i^{\prime}+\ell^{\prime}}),\ldots,(N^{\prime}(a_{i^{\prime}}),a_{i^{\prime}+1}),(v_{\pi(k_{i})},a_{i^{\prime}})$

7

8 if  _$E_{ri}^{i}\neq\emptyset$_ then

9 Delete all the edges in $E_{ri}^{i}$ and $(a_{q-\ell+i+1},v_{\pi(k_{i+1})})$

10 Connect
$(N^{\prime}(a_{i^{\prime\prime}}),a_{q-\ell+i+1}),(N^{\prime}(a_{i^{\prime\prime}+1}),a_{i^{\prime\prime}}),\ldots,(N^{\prime}(a_{i^{\prime\prime}+\ell^{\prime\prime}}),a_{i^{\prime\prime}+\ell^{\prime\prime}-1}),(v_{\pi(k_{i+1})},a_{i^{\prime\prime}+\ell^{\prime\prime}})$

11

12

Algorithm 2 Construction algorithm for $G^{\prime}$ third step

######  Claim 4.

The output $G^{\prime}$ of Algorithm 2 is outerplanar and satisfies
$\deg(G^{\prime})=d^{\prime}$.

###### Proof.

Let us first prove the outerplanarity of $G^{\prime}$. Consider a pair of
vertices $v_{\pi(k_{i})},v_{\pi(k_{i+1})}$. If $E_{le}^{i}=\emptyset$ and
$E_{ri}^{i}=\emptyset$, then for any edge $e\in E(\bar{G}^{\prime})$ with one
endpoint in $A_{1}^{i}$, the other endpoint of $e$ is either $v_{\pi(k_{i})}$
or $v_{\pi(k_{i+1})}$ by the definition of $E_{le}^{i}$ and $E_{ri}^{i}$.
Combining this with the choice of the position of $a_{q-\ell+i+1}$ in line 2
of the algorithm, $(v_{\pi(k_{i})},a_{q-\ell+i+1})$ and
$(v_{\pi(k_{i+1})},a_{q-\ell+i+1})$ do not cross any edges with one endpoint
in $A_{1}^{i}$. Therefore, there are no crossing edges in this case.

If $E_{le}^{i}\neq\emptyset$, then $(v_{\pi(k_{i})},a_{q-\ell+i+1})$ crosses
all the edges in $E_{le}^{i}$, which is the edge set with one endpoint before
$v_{\pi(k_{i})}$ and one in $A_{1}^{i}$. In this case, the correction process
deletes the edges in $E_{le}^{i}$ and $(v_{\pi(k_{i})},a_{q-\ell+i+1})$ and
connects $(N^{\prime}(a_{i^{\prime}+\ell^{\prime}}),a_{q-\ell+i+1})$,
$(N^{\prime}(a_{i^{\prime}+\ell^{\prime}-1}),a_{i^{\prime}+\ell^{\prime}})$,
$\ldots,(N^{\prime}(a_{i^{\prime}}),a_{i^{\prime}+1}),(v_{\pi(k_{i})},a_{i^{\prime}})$,
which means that all the edges in $E_{le}^{i}$ change their right endpoint to
the closest vertex on the right of it in $A$, and $v_{\pi(k_{i})}$ connects to
the leftmost endpoint of edges in $E_{le}^{i}$. After this step, the newly
added edges do not cross each other or the edges in
$E(\bar{G}^{\prime})\setminus E_{le}^{i}$ since $\bar{G}^{\prime}$ is outer
planar. The argument for $E_{ri}^{i}\neq\emptyset$ is similar to that of
$E_{le}^{i}\neq\emptyset$.

Next, we show that above correction processes are independent. Notice that the
correction process in Algorithm 2 is based on exchanging the endpoint of $e$
in $A_{1}^{i}$ to another vertex in $A_{1}^{i}$ for some
$e\in\bar{G}^{\prime}$. Therefore, the correction processes applied to
different pairs of $v_{\pi(k_{i})},v_{\pi(k_{i+1})}$ are independent. Also, in
the case that $E_{le}^{i}\neq\emptyset$, Algorithm 2 exchanges the right
endpoints of edges in $E_{le}^{i}$ and $a_{q-\ell+i+1}$. Similarly, in the
case that $E_{ri}^{i}\neq\emptyset$, Algorithm 2 exchanges the left endpoints
of edges in $E_{ri}^{i}$ and $a_{q-\ell+i+1}$. Since $E_{le}^{i}$ and
$E_{ri}^{i}$ are disjoint, the correction processes for
$E_{le}^{i}\neq\emptyset$ and $E_{ri}^{i}\neq\emptyset$ are independent. In
conclusion, after performing all of the above corrections for each pair
$v_{\pi(k_{i})},v_{\pi(k_{i+1})}$, there are no crossing edges left in
$G^{\prime}$.

Finally, we show that there are no parallel edges in the resulting
$G^{\prime}$. In the process of exchanging the endpoints, in the case that
$E_{le}^{i}\neq\emptyset$, the added edges are
$(N^{\prime}(a_{i^{\prime}+\ell^{\prime}}),a_{q-\ell+i+1})$,
$(N^{\prime}(a_{i^{\prime}+\ell^{\prime}-1}),a_{i^{\prime}+\ell^{\prime}})$,
$\ldots$, $(N^{\prime}(a_{i^{\prime}}),a_{i^{\prime}+1})$,
$(v_{\pi(k_{i})},a_{i^{\prime}})$, which did not exist in $\bar{G}^{\prime}$.
A similar argument applies for $E_{ri}^{i}\neq\emptyset$. Therefore, there are
no parallel edges. It follows that $G^{\prime}$ is a simple outerplanar graph.

To prove that $\deg(G^{\prime})=d^{\prime}$, it suffices to show that
$G^{\prime}$ has the same degree sequence as the bipartite graph $Bar(A,B)$,
since $\deg(Bar(A,B))=d^{\prime}$. In the first and second step, the
construction of $G^{\prime}$ is same as that of $\bar{G}^{\prime}$. Comparing
$\bar{G}^{\prime}$ with $Bar(A,B)$, the vertices $v_{\pi(k_{1})}$ and
$v_{\pi(k_{\ell})}$ are each one edge short, while the vertices
$v_{\pi(k_{i^{\prime}})}$ for $2\leq i^{\prime}\leq\ell-1$ are each two edges
short. Every vertex in $A_{2}$ has degree 0. In the third step, the correction
process in Algorithm 2 exchanges the endpoints of the cross edges, which keeps
the degree $2$ of the vertices in $A_{1}$. Also, the degrees of
$v_{\pi(k_{1})}$ and $v_{\pi(k_{\ell})}$ each increase by 1, and the degrees
of $v_{\pi(k_{i})}$ for $2\leq i\leq\ell-1$ each increase by 2. For $1\leq
i\leq\ell$, the vertex $a_{q-\ell+i+1}$ inserted between $v_{\pi(k_{i})}$ and
$v_{\pi(k_{i+1})}$ has degree 2 in $G^{\prime}$. Therefore,
$\deg(G^{\prime})=\deg(Bar(A,B))$. ∎

In summary, $G^{\prime}$ has an embedding into the page of a book where the
vertices are ordered along book spine according to $\pi$. It follows that $G$
and $G^{\prime}$ form a 2PBE realization of $d$. Note that $G$ is outerplanar
and $G^{\prime}$ is bipartite outerplanar. This completes the proof of Case B,
and of Lemma 16. ∎

Lemma 16 considers maximal-volume sequences. The following lemma mainly
focuses on non-maximal-volume sequences. Recall that $\Delta_{E}(d)=(4n-6-\sum
d)/2$ and $\Delta_{\omega}(d)=3\omega_{1}+2\omega_{2}+\omega_{3}-n$.

######  Lemma 17.

Let $d\in\mathcal{D}_{\geq 5}$ and $d_{1}\leq n-1$. If  (1)
$2\Delta_{E}\geq\Delta_{\omega}$,  (2) $\omega_{2}>2$ (3) $d_{2}>3$, and  (4)
$d_{n}=2$,  Then $d$ has an OP+bi realization.

###### Proof.

Given $d$ as in the lemma, apply to it the following Algorithm 3; let
$\bar{d}$ be its output.

1 Set $\bar{d}\leftarrow d$

2 while  _$\sum\bar{d} <4\bar{n}-6$ AND $\bar{\omega}_{2}>3$ AND
$\bar{d}_{1}>4$_ do

3 $\bar{d}_{j}\leftarrow\bar{d}_{j}-2$, where
$j=\text{argmax}_{i\in[\bar{n}]}~{}\bar{d}_{i}$

4 Remove two degrees $2$ from $\bar{d}$

5

Algorithm 3 generating $\bar{d}$ from $d$

To prove the lemma, we first show that $\bar{d}$ has a realization $\bar{G}$
that is outerplanar or a book embedding with two pages. Then, we modify
$\bar{G}$ to generate a realization $G$ of $d$ with the analogous properties.

Assume Algorithm 3 executes $k$ iterations of its while-loop. Let
$\bar{d}^{i}$ be the intermediate sequence after iteration $i\in[0,k]$, i.e.,
$\bar{d}^{0}=d$ and $\bar{d}^{k}=\bar{d}$. Observe that

  1. (i)

$\bar{n}^{i}=\bar{n}^{i+1}+2$,

  2. (ii)

$\bar{\omega}^{i}_{2}=\bar{\omega}^{i+1}_{2}+2$, and

  3. (iii)

$\sum\bar{d}^{i}=\sum\bar{d}^{i+1}+6$.

Next, we argue that $\bar{\Delta}_{E}^{i}=\bar{\Delta}_{E}^{i+1}+1$. Verify
that,

$2\bar{\Delta}_{E}^{i}=4\bar{n}^{i}-6-\sum\bar{d}^{i}=4\bar{n}^{i+1}-6-\sum\bar{d}^{i+1}+2=2(\bar{\Delta}_{E}^{i+1}+1).$

We proceed showing that
$\bar{\Delta}_{\omega}^{i}=\bar{\Delta}_{\omega}^{i+1}+2$. Verify that,

$\bar{\Delta}_{\omega}^{i}=2\bar{\omega}^{i}_{2}+\bar{\omega}^{i}_{3}-\bar{n}^{i}=2\bar{\omega}^{i+1}_{2}+4+\bar{\omega}^{i}_{3}-\bar{n}^{i+1}-2=\bar{\Delta}_{\omega}^{i+1}+2.$

It follows that $2\bar{\Delta}_{E}\geq\bar{\Delta}_{\omega}$. Moreover, note
that $\bar{d}_{\bar{n}-1}=\bar{d}_{\bar{n}}=2$ holds.

There are three conditions under which Algorithm 3 stops. Each of them allows
us to use a previous result and generate a realization of $\bar{d}$. We
consider the three cases separably.

Case (a):

$\bar{d}_{1}\leq 4$. $\bar{d}_{1}\leq\bar{n}-1$ by Algorithm 3. Then Lemma 12,
provides a 2PBE realization $(\bar{G},\bar{G}^{\prime})$ of $\bar{d}$.

Case (b):

$\bar{d}_{1}>4$ and $\sum\bar{d}=4\bar{n}-6$. Since $\bar{\Delta}_{E}=0$ and
$2\bar{\Delta}_{E}\geq\bar{\Delta}_{\omega}$ hold, we have that
$2\bar{\omega}_{2}+\bar{\omega}_{3}\leq\bar{n}$. It follows that $\bar{d}$
satisfies the preconditions of Lemma 16 yielding a 2PBE realization
$(\bar{G},\bar{G}^{\prime})$.

Case (c):

$\bar{d}_{1}>4$, $\sum\bar{d}<4\bar{n}-6$, and $\bar{\omega}_{2}\leq 3$. If
$\bar{\omega_{2}}=2$, then $\bar{d}$ has an outerplanar realization $\bar{G}$
due to Lemma 9. Otherwise, $\bar{\omega}_{2}=3$ holds, and Corollary 10
provides an outerplanar realization $\bar{G}$ of $\bar{d}$.

In either of the cases, $\bar{G}$ is a 2PBE graph that (partially) realizes
$\bar{d}$. During the execution of Algorithm 3, the order of $\bar{d}$ is kept
the same and it is not necessarily in nonincreasing order. For $i\in[k]$, let
$\ell_{i}$ be the index of the degree that was reduced by $2$ in iteration $i$
by Algorithm 3 (line(3)). To finish the proof, we modify $\bar{G}$ by running
Algorithm 4. Intuitively, it reverses the reduction, which was applied to
sequence $d$ by Algorithm 3, on the graph $\bar{G}$.

1 Set $G\leftarrow\bar{G}$

2 for  _$i\in[k]$_ do

3 Let $v\in V(G)$ such that $\deg_{G}(v)=\bar{d}_{\ell_{k-i+1}}$

4 $V(G)\leftarrow V(G)\cup\\{u,w\\}$

5 Add edges $(v,u),(v,w)$, and $(u,w)$ to $E(G)$

6 $\bar{d}_{\ell_{k-i+1}}=\bar{d}_{\ell_{k-i+1}}+2$

7

Algorithm 4 reversing $\bar{d}$ to $d$

Algorithm 4 starts constructing graph $G$ by copying $\bar{G}$. Note that
$\bar{G}$ is guaranteed to have a vertex $v$ with degree $\bar{d}_{\ell_{k}}$.
In the last iteration of Algorithm 3, $\bar{d}_{\ell_{k}}$ was reduced by $2$.
The degree of $v$, which is $\bar{d}_{\ell_{k}}$, is increased by $2$ in the
first iteration of Algorithm 4. Additionally, two more vertices are added to
$G$ which are connected to each other and to $v$. Figure 13 shows how the new
vertices can be added to an existing outerplanar embedding of $G$.

It follows that the graph $G$ returned by Algorithm 4 is a (partial)
realization of $d$. If $\bar{G}$ is an outerplanar realization of $\bar{G}$,
then $G$ is an outerplanar realization of $d$. Otherwise,
$(\bar{G},\bar{G}^{\prime})$ is a 2PBE realization of $\bar{d}$. Observe that
the vertices added by Algorithm 4 can be added to $\bar{G}^{\prime}$ as
isolated vertices without invalidating the book embedding. Hence,
$(G,\bar{G}^{\prime})$ is a 2PBE realization of $d$, where $G$ is outerplanar
and $\bar{G}^{\prime}$ is bipartite outerplanar. The lemma follows. ∎

######  Lemma 18.

Every graphic $d\in\mathcal{D}_{\geq 5}$ with $d_{2}\leq 3$ has an OP+bi
realization.

###### Proof.

First, in $\omega_{1}$ steps, connect a new vertex of degree 1 with the vertex
of currently largest degree obtaining the residual degree sequence
$d^{\prime}$. Since $\sum d\geq 2n$ and $\sum d\leq 4n-2\omega_{1}-6$,

$\displaystyle\sum d^{\prime}$ $\displaystyle\leq 4(n-\omega_{1})-6,$
$\displaystyle d^{\prime}_{n-\omega_{1}}$ $\displaystyle\geq 2.$ (7)

If $d^{\prime}_{1}\leq 4$, then $d^{\prime}$ has a 2PBE realization graph
$G^{\prime}$ by Theorem 15 and Inequality (7). Add $d_{i}-d^{\prime}_{i}$
leaves to the vertex in $G^{\prime}$ with degree $d^{\prime}_{i}$ for $1\leq
i\leq n-\omega_{1}$ and we get a graph $G$. Notice that $G$ realizes $d$ and
has page number 2.

Assume $u_{1},\ldots,u_{n-\omega_{1}}$ are the vertices with decreasing degree
in $d^{\prime}$ and $n^{\prime}=n-\omega_{1}$. If $d^{\prime}_{1}\geq 5$, then
$d^{\prime}_{1}>d_{2}$. All the $\omega_{1}$ leaves are connected to the
vertex with $d^{\prime}_{1}$ since the leaf is connected with the vertex of
currently largest degree. Therefore, $d_{1}-d^{\prime}_{1}=\omega_{1}$. Then
$d^{\prime}_{1}\leq n-1-\omega_{1}$ since $d_{1}\leq n-1$. Next connect
$u_{1}$ with $u_{2},\ldots u_{d^{\prime}_{1}+1}$ and obtain the residual
sequence $d^{\prime\prime}$. Notice that $d^{\prime\prime}$ has the form of
$(2^{n^{\prime}-1})$ or $(3^{\omega^{\prime}_{3}},2^{\omega^{\prime}_{2}})$ or
$(2^{\omega^{\prime}_{2}},1^{\omega^{\prime}_{1}})$ with
$\omega^{\prime}_{3},\omega^{\prime}_{2},\omega^{\prime}_{1}>0$.

Case 1:

$d^{\prime\prime}=(2^{n^{\prime}-1})$. Since $d^{\prime}_{1}\geq 5$ and
$d_{2}\leq 3$, there are $d^{\prime}_{1}$ vertices changing their degree from
3 in $d^{\prime}$ to 2 in $d^{\prime\prime}$. Then $n^{\prime}-1\geq 5$ and
$d^{\prime\prime}$ can be realized by a cycle.

Case 2:

$d^{\prime\prime}=(3^{\omega^{\prime}_{3}},2^{\omega^{\prime}_{2}})$. Since
$\omega^{\prime}_{3}>0$ and $d_{2}\leq 3$, there are $d^{\prime}_{1}$ vertices
changing their degree from 3 in $d^{\prime}$ to 2 in $d^{\prime\prime}$. Then
$\omega^{\prime}_{2}\geq 5$. Combining it with that $\omega^{\prime}_{3}$ is
even, $d^{\prime\prime}$ can be realized by an outerplanar graph .

Case 3:

For $d^{\prime\prime}=(2^{\omega^{\prime}_{2}},1^{\omega^{\prime}_{1}})$, it
can be realized by the union of a cycle and a matching or a forest. Therefore,
$d^{\prime\prime}$ can be realized by an outerplanar graph $G^{\prime\prime}$.

From above three cases, $G"$ is an outer planar graph. Add an isolated vertex
$u_{1}$ to $G^{\prime\prime}$ and obtain an outerplanar graph
$G_{1}^{\prime}=G^{\prime\prime}\cup\\{u_{1}\\}=(V,E^{\prime})$ with
$V=V^{\prime\prime}\cup\\{u_{1}\\}$. Let $G^{\prime}_{2}=(V,E^{\prime\prime})$
with
$E^{\prime\prime}=\\{(u_{1},u_{2}),\ldots,(u_{1},u_{d^{\prime}_{1}+1})\\}$.
The position of $u_{1}$ in the embedding of $G^{\prime}_{1}$ and
$G^{\prime}_{2}$ can be fixed arbitrarily since $u_{1}$ is isolated in
$G^{\prime}_{1}$, and $G^{\prime}_{2}$ has edges that do not exist in
$G^{\prime}$. $G^{\prime}_{1}\cup G^{\prime}_{2}$ realizes $d^{\prime}$ with
$2$ page embedding. Add $d_{i}-d^{\prime}_{i}$ leaves to the vertex in
$G^{\prime}_{2}$ with degree $d^{\prime}_{i}$ for $1\leq i\leq n-\omega_{1}$
and an outer planar graph $G_{2}$ is obtained. Notice that $G^{\prime}_{1}\cup
G_{2}$ realizes $d$ and has 2 page book embedding, where $G^{\prime}_{1}$ is
outerplanar and $G_{2}$ is bipartite outerplanar. ∎

######  Corollary 19.

Let $d\in\mathcal{D}_{\geq 5}$ and $d_{1}\leq n-1$. If
$2\Delta_{E}\geq\Delta_{\omega}$ and $d_{n}=d_{n-1}=2$, then $d$ has an OP+bi
realization.

###### Proof.

If $\omega_{2}=2$, then by Lemma 9, $d$ is outerplanaric. If $d_{2}\leq 3$,
then $d$ has a 2PBE realization by Lemma 18. Combining above observations with
Lemma 17, this corollary is proved. ∎

######  Lemma 20.

Let $d\in\mathcal{D}_{\geq 5}$ and $d_{1}\leq n-1$. If
$2\Delta_{E}\geq\Delta_{\omega}$ and $d$ satisfies $d_{n-1}\leq 2$ and
$d_{n-2}\leq 3$, then $d$ has an OP+bi realization.

###### Proof.

By the assumption on $d_{n-1}$, $d_{n}$ is either 1 or 2. If $d_{n}=2$, then
$d_{n-1}=2$ by the assumption on $d_{n-1}$, implying that $d$ has a 2PBE
realization by Corollary 19. So hereafter we focus on the case where
$d_{n}=1$.

We apply to $d$ a sequence of transformations described in Algorithm 5, which
gradually get rid of the 1 degrees.

1 Set $\bar{d}\leftarrow d$

2 while  _$\bar{\omega}_{1} >0$ AND $\bar{d}_{1}>4$_ do

3 $\bar{d}_{1}\leftarrow\bar{d}_{1}-1$

4 Remove one degree $1$ from $\bar{d}$

5 Re-sort $\bar{d}$

6

Algorithm 5 Removing 1 degrees

Assume Algorithm 5 executes $k$ iterations of its while-loop before halting.
Let $\bar{d}^{i}$ be the intermediate sequence after iteration $i\in[0,k]$,
i.e., $\bar{d}^{0}=d$ and $\bar{d}^{k}$ is the sequence $\bar{d}$ reached upon
termination of the algorithm. Observe that

  1. (i)

$\bar{n}^{i}=\bar{n}^{i+1}+1$,

  2. (ii)

$\bar{\omega}^{i}_{1}=\bar{\omega}^{i+1}_{1}+1$,
$\bar{\omega}^{i}_{2}=\bar{\omega}^{i+1}_{2}$,
$\bar{\omega}^{i}_{3}=\bar{\omega}^{i+1}_{3}$, and

  3. (iii)

$\sum\bar{d}^{i}=\sum\bar{d}^{i+1}+2$.

These observations imply also that,

$\displaystyle 2\bar{\Delta}_{E}^{i}$ $\displaystyle=$ $\displaystyle
4\bar{n}^{i}-6-\sum\bar{d}^{i}~{}=~{}4(\bar{n}^{i+1}+1)-6-(\sum\bar{d}^{i+1}+2)$
(8) $\displaystyle=$ $\displaystyle
4\bar{n}^{i+1}-6-\sum\bar{d}^{i+1}+2~{}=~{}2\bar{\Delta}_{E}^{i+1}+2.$

By the above observations (i) and (ii),

$\displaystyle\bar{\Delta}_{\omega}^{i}$
$\displaystyle=3\bar{\omega}^{i}_{1}+2\bar{\omega}^{i}_{2}+\bar{\omega}^{i}_{3}-\bar{n}^{i}=3(\bar{\omega}^{i+1}_{1}+1)+2\bar{\omega}^{i+1}_{2}+\bar{\omega}^{i+1}_{3}-\bar{n}^{i+1}-1=\bar{\Delta}_{\omega}^{i+1}+2$
(9)

We next claim that throughout the execution of Algorithm 5,

$\displaystyle
2\bar{\Delta}_{E}^{i}\geq\bar{\Delta}_{\omega}^{i},~{}~{}~{}~{}~{}~{}\mbox{for}~{}i=0,\ldots,k,$
(10) $\displaystyle\sum\bar{d}^{i}\leq
4\bar{n}^{i}-6-2\bar{\omega}^{i}_{1},~{}~{}~{}~{}~{}~{}\mbox{for}~{}i=0,\ldots,k.$
(11)

Both claims can be shown by induction on $i$, where the basis follows from the
assumptions of the lemma. For the first inequality, the inductive progress
step follows by Eq. (8) and (9). For the second inequality, the progress step
follows from the inductive hypothesis since

$\sum d^{i+1}=\sum d^{i}+2\leq
4n^{i}-6-2\bar{\omega}^{i}_{1}+2=4n^{i+1}-6-2\bar{\omega}^{i+1}_{1}.$

Algorithm 5 stops when either $\bar{\omega}_{1}=0$ or $\bar{d}_{1}\leq 3$. Let
the final sequence be $d^{\prime}$ and $n$ is updated to $n^{\prime}$. By Eq.
(10) and (11), we have

$\displaystyle 2\Delta_{E}^{\prime}$ $\displaystyle\geq$
$\displaystyle\Delta_{\omega}^{\prime}~{},$ (12) $\displaystyle\sum
d^{\prime}$ $\displaystyle\leq$ $\displaystyle
4n^{\prime}-6-2\omega^{\prime}_{1}~{}.$ (13)

Next, we claim that the resulting sequence $d^{\prime}$ has a 2PBE
realization. To prove this, consider the above two cases separately.

Case a:

$\omega^{\prime}_{1}=0$. By Eq. (13), we have $d^{\prime}_{n^{\prime}-1}\leq
3$. Consider two possible subcases,
$(d^{\prime}_{n^{\prime}-1},d^{\prime}_{n^{\prime}})=(2,2)$ and
$(d^{\prime}_{n^{\prime}-1},d^{\prime}_{n^{\prime}})\in\\{(2,3),(3,3)\\}$.

SubCase (a1):

$d^{\prime}_{n^{\prime}}=d^{\prime}_{n^{\prime}-1}=2$. Then combining Eq. (12)
and (13), the conditions in Corollary 19 are satisfied and $d^{\prime}$ has a
2PBE realization $G^{\prime}$.

SubCase (a2):

$d^{\prime}_{n^{\prime}}\in\\{2,3\\}$ and $d^{\prime}_{n^{\prime}-1}=3$. Then,
$d^{\prime}$ has a 2PBE realization $G^{\prime}$ by Lemma 13.

Case (b):

$d^{\prime}_{1}\leq 4$ and $\bar{\omega}_{1}>0$. Notice that
$d^{\prime}_{1}\leq n^{\prime}-1$ by Algorithm 5. In this case, $d^{\prime}$
2PBE realization $G^{\prime}$ by Lemma 14 and Eq. (13).

It follows that in all cases, $d^{\prime}$ has a 2PBE realization. We now
transform this realization into a 2PBE realization $G$ for the original
sequence $d$ by creating $d_{i}-d^{\prime}_{i}$ new vertices of degree 1 and
connecting them to vertex $i$ in $G^{\prime}$, for every $i$. (Clearly, these
vertices can be embedded on the existing pages of $G^{\prime}$ while
preserving their outerplanarity.) By the above construction, $G$ consists of
two graphs, where one is outerplanar and the other is bipartite outerplanar. ∎

Combining Lemmas 3, 8 and 20, we conclude the following.

######  Corollary 21.

There is a polynomial time algorithm that, given an outerplanaric sequence
$d\in\mathcal{D}_{\geq 5}$ with $d_{2}>3$, returns an OP+bi realization for
$d$.

###  4.3 Putting the pieces together

Combining Thm. 15, Lemma 18 and Cor. 21, we conclude with the following.

######  Theorem 22.

There is a polynomial time algorithm that given a sequence $d\in\mathcal{D}$
either returns “$d$ is not outerplanaric” or returns a 2PBE realization for
$d$.

######  Corollary 23.

There is a poly-time algorithm that constructs a 1PBE or 2PBE realization for
any sequence in a superclass222The class $\mathcal{S}$ strictly contains the
class $\mathcal{OP}$. For example, the sequence $(4^{2},2^{4})$ is not
outerplanaric yet it satisfies the conditions of Lemma 12, hence our algorithm
succeeds in constructing a 2PBE realization for it. $\mathcal{S}$ of the class
$\mathcal{OP}$ of all outerplanaric sequences.

## References

  * [1] P. Adams and Y. Nikolayevsky.  Planar bipartite biregular degree sequences.  Discr. Math., 342:433–440, 2019.
  * [2] F. Bernhart and P. C. Kainen.  The book thickness of a graph.  J. Combin. Th. B, 27:320–331, 1979.
  * [3] P. Bose, V. Dujmović, D. Krizanc, S. Langerman, P. Morin, D. R. Wood, and S. Wuhrer.  A characterization of the degree sequences of 2-trees.  JGT, 58:191–209, 2008.
  * [4] C. N. Campos and Y. Wakabayashi.  On dominating sets of maximal outerplanar graphs.  Discr. Appl. Math., 161(3):330–335, 2013.
  * [5] S. A. Choudum.  Characterization of forcibly outerplanar graphic sequences.  In Combinatorics and Graph Theory, pages 203–211. 1981.
  * [6] P. Erdös and T. Gallai.  Graphs with prescribed degrees of vertices [hungarian].  Matematikai Lapok, 11:264–274, 1960.
  * [7] S. Fanelli.  On a conjecture on maximal planar sequences.  JGT, 4:371–375, 1980.
  * [8] S. Fanelli.  An unresolved conjecture on nonmaximal planar graphical sequences.  Discr. Math., 36(1):109–112, 1981.
  * [9] G. Gupta, P. Joshi, and A. Tripathi.  Graphic sequences of trees and a problem of Frobenius.  Czechoslovak Math. J., 57:49–52, 2007.
  * [10] S. L. Hakimi.  On realizability of a set of integers as degrees of the vertices of a linear graph –I.  SIAM J. Appl. Math., 10(3):496–506, 1962.
  * [11] V. Havel.  A remark on the existence of finite graphs [in Czech].  Casopis Pest. Mat., 80:477–480, 1955.
  * [12] A. Hawkins, A. Hill, J. Reeve, and J. Tyrrell.  On certain polyhedra.  The Mathematical Gazette, 50(372):140–144, 1966.
  * [13] K. F. Jao and D. B. West.  Vertex degrees in outerplanar graphs.  Journal of Combinatorial Mathematics and Combinatorial Computing, 82:229–239, 2012.
  * [14] Z. Li and Y. Zuo.  On the degree sequences of maximal outerplanar graphs.  Ars Comb., 140:237–250, 2018.
  * [15] Z. Lotker, D. Majumdar, N. S. Narayanaswamy, and I. Weber.  Sequences characterizing _k_ -trees.  In 12th COCOON, volume 4112 of LNCS, pages 216–225, 2006\.
  * [16] A. Proskurowski.  Minimum dominating cycles in 2-trees.  Int. J. Comput. & Info. Sci., 8:405–417, 1979.
  * [17] M. T. Rafid, R. Ibrat, and M. S. Rahman.  Generating scale-free outerplanar networks.  In Int. Computer Symp., pages 156–166. Springer, 2022.
  * [18] S. B. Rao.  A survey of the theory of potentially p-graphic and forcibly p-graphic degree sequences.  In Combinatorics and graph theory, pages 417–440, 1981.
  * [19] S. Rengarajan and C. E. V. Madhavan.  Stack and queue number of 2-trees.  In 1st COCOON, volume 959 of LNCS, pages 203–212, 1995\.
  * [20] E. F. Schmeichel and S. L. Hakimi.  On planar graphical degree sequences.  SIAM J. Applied Math., 32:598–609, 1977.
  * [21] M. M. Syslo.  Characterizations of outerplanar graphs.  Disc. Math., 26:47–53, 1979.
  * [22] D. West.  Introduction to graph theory.  Prentice Hall, 2001.
  * [23] M. Yannakakis.  Four pages are necessary and sufficient for planar graphs.  In 18th ACM Symp. on Theory of Computing (STOC), pages 104–108, 1986.