The Plane-Saturation Ratio of Planar Graphs

arXiv:2610.34407 · math.CO · Submitted 2026-10-25 · Read on arXiv

math.CO

Submitted: 2026-10-25

Updated: 2026-10-25

Comments: 10 pages

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: 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…

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 (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 k 1,k 2 denote the class of planar graphs in which, for each i in1,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 k 1,k 2 with at least one edge satisfies (G)> 1 over 9+k 1+6k 2. This settles two conjectures of Clifton and Salia.

Related papers