The Plane-Saturation Ratio of Planar Graphs

Source 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.