DROPS

Document

Invited Paper

DOI: 10.4230/LIPIcs.MFCS.2024.1

On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

Call a sequence d = (d_1,d_2, …, d_n) of positive integers graphic, planaric, outer-planaric, or forestic if it is the degree sequence of some arbitrary, planar, outer-planar, or cycle-free graph G, respectively. The two extreme classes of graphic and forestic sequences were given full characterizations. (The latter has a particularly simple criterion: d is forestic if and only if its volume, ∑ d ≡ ∑_i d_i, satisfies ∑ d ≤ 2n - 2.) In contrast, the problems of fully characterizing planaric and outer-planaric degree sequences are still open. In this paper, we discuss the parameters affecting the realizability of degree sequences by restricted classes of sparse graph, including planar graphs, outerplanar graphs, and some of their subclasses (e.g., 2-trees and cactus graphs). A key parameter is the volume of the sequence d, namely, ∑ d which is twice the number of edges in the realizing graph. For planar graphs, for example, an obvious consequence of Euler’s theorem is that an n-element sequence d satisfying ∑ d > 4n-6 cannot be planaric. Hence, ∑ d ≤ 4n-6 is a necessary condition for d to be planaric. What about the opposite direction? Is there an upper bound on ∑ d that guarantees that if d is graphic then it is also planaric. Does the answer depend on additional parameters? The same questions apply also to sub-classes of the planar graphs. A concrete example that is illustrated in the technical part of the paper is the class of outer-planaric degree sequences. Denoting the number of 1’s in d by ω₁, we show that for a graphic sequence d, if ω₁ = 0 then d is outer-planaric when ∑ d ≤ 3n-3, and if ω₁ > 0 then d is outer-planaric when ∑ d ≤ 3n-ω₁-2. Conversely, we show that there are graphic sequences that are not outer-planaric with ω₁ = 0 and ∑ d = 3n-2, as well as ones with ω₁ > 0 and ∑ d = 3n-ω₁-1.

Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz. On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper). In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2024.1,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
  title =	{{On Key Parameters Affecting the Realizability of Degree Sequences}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.1},
  URN =		{urn:nbn:de:0030-drops-205573},
  doi =		{10.4230/LIPIcs.MFCS.2024.1},
  annote =	{Keywords: Degree Sequences, Graph Algorithms, Graph Realization, Outer-planar Graphs}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.18

Sparse Graphic Degree Sequences Have Planar Realizations

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

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.

Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz. Sparse Graphic Degree Sequences Have Planar Realizations. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2024.18,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
  title =	{{Sparse Graphic Degree Sequences Have Planar Realizations}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.18},
  URN =		{urn:nbn:de:0030-drops-205745},
  doi =		{10.4230/LIPIcs.MFCS.2024.18},
  annote =	{Keywords: Degree Sequences, Graph Algorithms, Graph Realization, Planar Graphs}
}

Search Results

Documents authored by Ran, Yingli

On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

Abstract

Cite as

Sparse Graphic Degree Sequences Have Planar Realizations

Abstract

Cite as

Thanks for your feedback!

Could not send message