Paperlane

no. 3 · Tuesday 27 October 2026

The Plane-Saturation Ratio of Planar Graphs

Qing Cui and Shengjin Ji

math.CO · 10 pp

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 \(k_1\) and \(k_2\), let \(\cG_{k_1,k_2}\) denote the class of planar graphs in which, for each \(i\in\{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\in\cG_{k_1,k_2}\) with at least one edge satisfies $\psr(G)>\frac{1}{9+k_1+6k_2}.$ This settles two conjectures of Clifton and Salia.

comments
10 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.34407 ↗