Approximate realizations for outerplanaric degree sequences

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran*, Dror Rawitz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We study the question of whether a sequence d=(d1,…,dn) of positive integers is the degree sequence of some outerplanar 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. In this paper, we consider the family D of all sequences d of even sum 2n≤∑d≤4n−6−2ω1, where ωx is the number of x's in d. We partition D into two disjoint subfamilies, D=DNOP∪D2PBE, such that every sequence in DNOP is provably non-outerplanaric, and every sequence in D2PBE is given a realizing graph G enjoying a 2-page book embedding (and moreover, one of the pages is also bipartite).

Original languageEnglish
Article number103588
Number of pages20
JournalJournal of Computer and System Sciences
Volume148
Early online date10 Oct 2024
DOIs
Publication statusPublished Online - 10 Oct 2024

Funding

This research is supported by US-Israel BSF grant (2022205) and National Natural Science Foundation of China (11901533) .

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Approximate realizations for outerplanaric degree sequences'. Together they form a unique fingerprint.

Cite this