The Price of Connectivity Augmentation on Planar Graphs

Given two classes of graphs, ${\mathcal{G}}_1\subseteq {\mathcal{G}}_2$, and a $c$-connected graph $G\in {\mathcal{G}}_1$, we wish to augment $G$ with a smallest cardinality set of new edges $F$ to obtain a $k$-connected graph $G^{\mathrm{\prime }}=(V,E\cup F)\in {\mathcal{G}}_2$. In general, this is the $c\to k$ connectivity augmentation problem. Previous research considered variants where ${\mathcal{G}}_1={\mathcal{G}}_2$ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the $c\to k$ augmentation problem is NP-complete when $2\le c<k\le 5$. However, the connectivity of the augmented graph $G^{\mathrm{\prime }}$ is at most $5$ if ${\mathcal{G}}_2$ is limited to planar graphs. We initiate the study of the $c\to k$ connectivity augmentation problem for arbitrary $k\in \mathbb{N}$, where ${\mathcal{G}}_1$ is the class of planar graphs, plane graphs, or planar straight-line graphs, and ${\mathcal{G}}_2$ is a beyond-planar class of graphs: $\mathrm{\ell }$-planar, $\mathrm{\ell }$-plane topological, or $\mathrm{\ell }$-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity $k$ and the local crossing number $\mathrm{\ell }$ of the augmented graph $G^{\mathrm{\prime }}$. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.