Approximate Realizations for Outerplanaric Degree Sequences
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929336311873536 |
|---|---|
| author | Bar-Noy, Amotz Bohnlein, Toni Peleg, David Ran, Yingli Rawitz, Dror |
| author_facet | Bar-Noy, Amotz Bohnlein, Toni Peleg, David Ran, Yingli Rawitz, Dror |
| contents | 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 \cD of all sequences d of even sum 2n\leq \sum d \le 4n-6-2\multipl_1, where \multipl_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 \cD into two disjoint subfamilies, \cD=\cD_{NOP}\cup\cD_{2PBE}, such that every sequence in \cD_{NOP} is provably non-outerplanaric, and every sequence in \cD_{2PBE} is given a realizing graph $G$ enjoying a 2-page book embedding (and moreover, one of the pages is also bipartite). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03278 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximate Realizations for Outerplanaric Degree Sequences Bar-Noy, Amotz Bohnlein, Toni Peleg, David Ran, Yingli Rawitz, Dror Data Structures and Algorithms Discrete Mathematics 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 \cD of all sequences d of even sum 2n\leq \sum d \le 4n-6-2\multipl_1, where \multipl_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 \cD into two disjoint subfamilies, \cD=\cD_{NOP}\cup\cD_{2PBE}, such that every sequence in \cD_{NOP} is provably non-outerplanaric, and every sequence in \cD_{2PBE} is given a realizing graph $G$ enjoying a 2-page book embedding (and moreover, one of the pages is also bipartite). |
| title | Approximate Realizations for Outerplanaric Degree Sequences |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2405.03278 |