The Plane-Saturation Ratio of Planar Graphs
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality