Approximate Realizations for Outerplanaric Degree Sequences

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 \le 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\le \sum d \le 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\ge 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).