2026-07-21T12:35:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20574 2024-08-23T05:50:28Z ddc:004 open_access

Sparse Graphic Degree Sequences Have Planar Realizations Bar-Noy, Amotz Böhnlein, Toni Peleg, David Ran, Yingli Rawitz, Dror Degree Sequences Graph Algorithms Graph Realization Planar Graphs A sequence d = (d_1,d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amotz Bar-Noy and Toni Böhnlein and David Peleg and Yingli Ran and Dror Rawitz 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.18 urn:nbn:de:0030-drops-205745 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.18 eng https://creativecommons.org/licenses/by/4.0/legalcode