Saturated Partial Embeddings of Planar Graphs

In this work, we study how far one can deviate from optimal behavior when embedding a planar graph. For a planar graph $G$, we say that a plane subgraph $H\subseteq G$ is a $\mathit{\text{plane-saturated}}\mathit{\text{subgraph}}$ if adding any edge (possibly with new vertices) to $H$ would either violate planarity or make the resulting graph no longer a subgraph of $G$. For a planar graph $G$, we define the $\mathit{\text{plane-saturation}}\mathit{\text{ratio}}$, $\text{psr}(G)$, as the minimum value of $\frac{e(H)}{e(G)}$ for a plane-saturated subgraph $H$ of $G$ and investigate how small $\text{psr}(G)$ can be. While there exist planar graphs where $\text{psr}(G)$ is arbitrarily close to $0$, we show that for all twin-free planar graphs, $\text{psr}(G)>1\mathrm{/}16$, and that there exist twin-free planar graphs where $\text{psr}(G)$ is arbitrarily close to $1\mathrm{/}16$. In fact, we study a broader category of planar graphs, focusing on classes characterized by a bounded number of degree $1$ and degree $2$ twin vertices. We offer solutions for some instances of bounds while positing conjectures for the remaining ones.