Approximate Realizations for Outerplanaric Degree Sequences

We study the question of whether a sequence d = (d_1,d_2, …, 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 ∑ d ≤ 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 of all sequences d of even sum 2n≤ ∑ d ≤ 4n-6-2_1, where _x is the number of x's in d. (The second inequality is a necessary condition for a sequence d with ∑ d≥ 2n to be outerplanaric.) We partition into two disjoint subfamilies, =NOP∪2PBE, such that every sequence in NOP is provably non-outerplanaric, and every sequence in 2PBE is given a realizing graph G enjoying a 2-page book embedding (and moreover, one of the pages is also bipartite).