Daniel Simon


Title: Saturated Partial Embeddings of Maximal Planar Graphs
(Joint work with Alexander Clifton)




We investigate two notions of saturation for partial planar embeddings
of maximal planar graphs. Let $G = (V, E) $ be a vertex-labeled maximal
planar graph  on $ n $ vertices, which by definition has $3n - 6$ edges.
We say that a labeled plane graph $H = (V, E')$ with $E' \subseteq E$ is
a \emph{labeled plane-saturated subgraph} of $G$ if no edge in $E
\setminus E'$ can be added to $H$ in a manner that preserves vertex
labels, without introducing a crossing. The \emph{labeled
plane-saturation ratio} $lpsr(G)$ is defined as the minimum value of
$\frac{e(H)}{e(G)}$ over all such $H$. We establish almost tight bounds
for $lpsr(G)$, showing $lpsr(G) \leq \frac{n+5}{3n-6}$ for $n \geq 47$,
and constructing a maximal planar graph $G$ with $lpsr(G) \geq
\frac{n+2}{3n-6}$ for each $n\ge 5$.

Dropping vertex labels, a \emph{plane-saturated subgraph} is defined as
a plane subgraph $H\subseteq G$ where adding any additional edge to the
drawing either introduces a crossing or causes the resulting graph to no
longer be a subgraph of $G$. The \emph{plane-saturation ratio} $psr(G)$
is defined as the minimum value of $\frac{E(H)}{E(G)}$ over all such
$H$. For all sufficiently large $n$, we demonstrate the existence of a
maximal planar graph $G$ with $psr(G) \geq \frac{\frac{3}{2}n - 3}{3n -
6} = \frac{1}{2}$.