Drawing Planar Graphs Badly.

Abstract: We study how far one can deviate from optimal behavior when drawing a planar graph on a plane. For a planar graph $G$, we say that a plane subgraph $H\subseteq G$ is a \textit{plane-saturated subgraph} if adding any edge (possibly with a new vertex) 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 \textit{plane-saturation ratio}, $\psr(G)$, as the minimum value of $\frac{e(H)}{e(G)}$ for a plane-saturated subgraph $H\subseteq G$ and investigate how small $\psr(G)$ can be. While there exist planar graphs where $\psr(G)$ is arbitrarily close to $0$, we show that for all twin-free planar graphs, $\psr(G)>1/16$, and that there exist twin-free planar graphs where $\psr(G)$ is arbitrarily close to $1/16$.

Posted on Oct 2, 2024 in Seminario de Grafos, Seminars