Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs

Abstract

We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG $G=(V,E)$ in general position can be augmented to a 2-connected PSLG $(V,E\cup E^{+})$ by adding new edges of total Euclidean length $\Vert E^{+}\Vert \le 2\Vert E\Vert$, and this bound is the best possible. An optimal edge set $E^{+}$ can be computed in $O(|V{|}^4)$ time; however the problem becomes NP-hard when $G$ is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG $G=(V,E)$ into a planar straight-line cycle $G^{\prime }=(V,E^{\prime })$ such that $\Vert E^{\prime }\Vert \le 2\Vert \mathrm{MST}(V)\Vert$, and the graph remains connected with edge length below $\Vert E\Vert +\Vert \mathrm{MST}(V)\Vert$ at all stages. These bounds are the best possible.

15 pages, 7 figures, to appear in the Proceedings of WALCOM 2017