Abstract
We investigate the extremal properties of saturated partial plane embeddings of maximal planar graphs. For a planar graph $G$, the plane-saturation number $\mathrm{sat}_{\mathcal{P}}(G)$ denotes the minimum number of edges in a plane subgraph of $G$ such that the addition of any edge either violates planarity or results in a graph that is not a subgraph of $G$. We focus on maximal planar graphs and establish an upper bound on $\mathrm{sat}_{\mathcal{P}}(G)$ by showing there exists a universal constant $\epsilon > 0$ such that $\mathrm{sat}_{\mathcal{P}}(G) < (3-\epsilon)v(G)$ for any maximal planar graph $G$ with $v(G) \geq 16$. This answers a question posed by Clifton and Simon. Additionally, we derive lower bound results and demonstrate that for maximal planar graphs with sufficiently large number of vertices, the minimum ratio $\mathrm{sat}_{\mathcal{P}}(G)/e(G)$ lies within the interval $(1/16, 1/9 + o(1)]$.
The Plane-Saturation Problem
In extremal graph theory, a graph is considered "saturated" with respect to a property if it lacks that property, but the addition of any missing edge creates it. This paper explores a geometric variant: plane saturation. Given a "host" graph $G$ that is a maximal planar graph (a triangulation), a plane subgraph $H \subseteq G$ is plane-saturated if no edge from $E(G) \setminus E(H)$ can be added to $H$ without crossing existing edges or violating the planarity of the embedding.
The central goal is to determine the plane-saturation number $\mathrm{sat}_{\mathcal{P}}(G)$, which is the minimum number of edges in such a "stuck" subgraph. While a triangulation $G$ has $3v - 6$ edges, the researchers aim to show that $\mathrm{sat}_{\mathcal{P}}(G)$ is significantly smaller, missing a linear number of edges relative to the vertex count.
Structural Constraints and the "Hiding" Strategy
The core of the proof involves analyzing the distribution of low-degree vertices, specifically degree-3 vertices, within the host triangulation. A key insight is that degree-3 vertices cannot be too dense; the authors prove they form an independent set and their count is bounded by $(2n-4)/3$.
To minimize the number of edges in a saturated subgraph, the authors employ a "hiding" strategy. By placing vertices inside the triangular faces of a smaller maximal planar subgraph, those vertices are restricted to connecting only to the three corners of their containing triangle. If these potential edges are omitted or blocked, the vertex becomes saturated with minimal connectivity.
Establishing Universal Bounds
The authors successfully answer a conjecture by Clifton and Simon by proving that for any maximal planar graph with $v(G) \geq 16$, there exists a universal constant $\epsilon > 0$ such that $\mathrm{sat}_{\mathcal{P}}(G) < (3 - \epsilon)v(G)$. Through rigorous case partitioning—separating graphs with many degree-3 vertices from those with few—they derive a specific value of $\epsilon = 1/300$.
On the lower bound side, the paper provides a simplified proof showing that $\mathrm{sat}_{\mathcal{P}}(G) \ge \frac{v(G)+4}{6}$. This ensures that while the saturation number is smaller than the total edge count, it still grows linearly with the number of vertices.
Asymptotic Ratios and Extremal Constructions
For large graphs, the researchers focus on the ratio $\mathrm{sat}_{\mathcal{P}}(G)/e(G)$. They demonstrate that this ratio is bounded between $1/16$ and approximately $1/9$. To prove the upper bound of this interval, they construct a specific infinite family of graphs, $G_k$, and identify a corresponding saturated subgraph $H_k$.
In this construction, the saturated subgraph $H_k$ utilizes isolated vertices ($I_{2k-23}$) and star-like structures ($K_{1,11}$) to "trap" vertices within the faces of a larger framework, effectively reducing the edge count to roughly $v(G)/3$.
Conclusion
This work provides the first universal linear upper bound for the plane-saturation number of maximal planar graphs. While the existence of $\epsilon$ is confirmed, the current value of $1/300$ is likely conservative. Future research remains to close the gap between the $1/16$ lower bound and the $1/9$ upper bound construction, and to extend these findings to general, non-maximal planar graphs.
Summary updated