PreprintCC BY-NC-ND 4.0arXiv
The Plane-Saturation Ratio of Planar Graphs
Abstract
For a planar graph G, a plane subgraph H is plane-saturated with respect to G if adding any edge to the fixed drawing of H, possibly together with new vertices, either creates a crossing or results in a graph that is not a subgraph of G. The plane-saturation ratio psr(G) is the minimum of e(H)/e(G) over all plane-saturated subgraphs H of G. For nonnegative integers k1 and k2, let cGk1,k2 denote the class of planar graphs in which, for each i∈{1,2}, at most ki vertices of degree i have any prescribed neighborhood, where ki=0 means that vertices of degree i are forbidden. We prove that every G∈cGk1,k2 with at least one edge satisfies psr(G)>1/(9+k1+6k2). This settles two conjectures of Clifton and Salia.
Related
- Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
- On the minimizer of the barycentric isoperimetric ratio among connected planar sets
- Saturation and semisaturation of oriented graphs
- Bounds for B-coloring planar and outerplanar graphs
- Saturation numbers for joins with graphs containing isolated vertices
BibTeX
@misc{cui2026planesaturation,
title = {{The Plane-Saturation Ratio of Planar Graphs}},
author = {Qing Cui and Shengjin Ji},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34407},
eprint = {2610.34407},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34407},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - The Plane-Saturation Ratio of Planar Graphs
AU - Qing Cui
AU - Shengjin Ji
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34407
UR - https://arxiv.org/abs/2610.34407
AB - For a planar graph G, a plane subgraph H is plane-saturated with respect to G if adding any edge to the fixed drawing of H, possibly together with new vertices, either creates a crossing or results in a graph that is not a subgraph of G. The plane-saturation ratio psr(G) is the minimum of e(H)/e(G) over all plane-saturated subgraphs H of G. For nonnegative integers k_1 and k_2, let cG_k_1,k_2 denote the class of planar graphs in which, for each i∈{1,2}, at most k_i vertices of degree i have any prescribed neighborhood, where k_i=0 means that vertices of degree i are forbidden. We prove that every G∈cG_k_1,k_2 with at least one edge satisfies psr(G)>1/(9+k_1+6k_2). This settles two conjectures of Clifton and Salia.
ER -