The Price of Connectivity Augmentation on Planar Graphs

Abstract

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^{\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^{\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: $\ell$-planar, $\ell$-plane topological, or $\ell$-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity $k$ and the local crossing number $\ell$ of the augmented graph $G^{\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.

29 pages, 21 figures, accepted at the 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)