Minimum weight connectivity augmentation for planar straight-line graphs (Q2272377)

The vertex (edge) connectivity of a graph is defined as the minimum number of vertices (edges) whose removal will disconnect such a graph. This pair of fundamental characteristics of a graph have been of great interest from both a theoretical and practical perspective. The focus of this paper is to study if we could increase the connectivity, in terms of both vertex and edge, of a given \textit{planar, straight-line graph (PSLG)} by adding and deleting edges while minimizing the total edge length of the resulting graph. Notice that for a PSLG, $G(V, E)$, vertices in $V$ are points in the Euclidean plane, the edges in $E$ are non-crossing line segments between the corresponding vertices, the weight of an edge $e$ is its Euclidean length, and the weight of $E$, denoted by $\|E\|$, is the sum of the weights of all the edges. Since, by the well-known Euler's polyhedron formula, the vertex, and the edge, connectivity of a planar graph are both at most 5, the scope of such a potential augmentation is rather limited. To this regard, this paper obtains three results, including the following two: 1) A general connected PSLG graph, $G(V, E)$, can be augmented to a 2-connected PSLG, $G'(V, E \cup E^+)$, by adding a set of edges $E^+$ where $\|E^+\| < 2\|E\|;$ and a minimum $E^+$ can be computed in $O({|V|}^4)$ time. 2) This problem becomes NP-hard for all the other cases, i.e., whether a disconnected $G(V, E)$ is to be augmented to a 2-connected graph or a $(\tau-1)$-connected PSLG graph is to be augmented to a $\tau$-connected graph for $\tau \in [3, 5]$, with any finite edge set $E^+$. This problem has been studied for a variety of graphs, including the class of PSLG, as evidenced by the works cited within this paper. But, apparently, usage of the Euclidean length as the weight function is a new, and recent, attempt. The results are certainly revealing, as well as final, for PSLG, thanks to its rather limited connectivity. When seeking clarification to some of the issues as contained in this paper, this reviewer did have some communication with the corresponding author of this paper, who pointed out, among other things, that ``The optimal solution for augmenting from disconnected to 2-connected does not necessarily contain the optimal solutions for augmenting from disconnected to connected and from connected to 2-connected. The latter two parts can be computed in poly-time, but we showed that the optimal solution for the first one (disconnected to 2-connected) is NP-complete. The solution for this problem may not be the union of the solutions of the two other `smaller' problems.''