Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Edge-connectivity augmentation is a classic problem in combinatorial optimization motivated by applications in fault-tolerant network design. Given an undirected graph \(G=(V,E)\) and a number , we want to find a set F of new edges of minimum cardinality such that \(G'=(V,E\cup F)\) is \(\tau \)-edge-connected. In this note, we consider edge-connectivity augmentation for planar straight line graphs (PSLG) with n vertices in general position (no three collinear vertices).

Every graph with components can be augmented into a connected graph with the addition of \(t-1\) new edges. Every PSLG with n vertices can be augmented to a connected PSLG (encompassing graph) with at most \(n-1\) new edges. Every connected PSLG on n vertices can be augmented to a 2-edge-connected PSLG with at most \(\lfloor (2n-2)/3\rfloor \) new edges [3]. Both bounds are the best possible. The combination of the two bounds implies that every PSLG on n vertices can be augmented to 2-edge-connectivity with the addition of at most \(\lfloor 5(n-1)/3\rfloor \) new edges. However, this bound is not tight. We derive a better bound and show the following.

FormalPara Theorem 1

Every PSLG with \(n\ge 3\) vertices can be augmented to a 2-edge-connected PSLG with the addition of at most \(\lfloor (4n-4)/3\rfloor \) new edges. This bound is the best possible.

The upper bound in Theorem 1 is attained for a triangulation on \(k\ge 3\) vertices, with an isolated vertex placed in each of the \(2k-5\) bounded faces and 3 vertices in the outer face that pairwise do not see each other (that is, \(n=k+(2k-5)+3=3k-2\)). The proof of the upper bound is constructive and distinguishes between two cases depending on the number of components in the graph. Due to space limitation, we give an outline of the proof here.

Let G be a PSLG on \(n\ge 3\) vertices in general position. Let c be the number of components in G. In the first case \(c\le \lfloor (2n+1)/3 \rfloor \), and we augment G to a 2-edge-connected PSLG as follows: first use \(c - 1\) new edges to obtain a connected PSLG, and then use \(\lfloor (2n-2)/3\rfloor \) edges to make it 2-edge-connected [3]. The total number of new edges is at most

$$\begin{aligned} (c - 1) + \bigg \lfloor {\frac{2n-2}{3}}\bigg \rfloor \le \bigg \lfloor {\frac{2n+1}{3}}\bigg \rfloor -1+ \bigg \lfloor {\frac{2n-2}{3}}\bigg \rfloor \le \bigg \lfloor {\frac{4n-4}{3}} \bigg \rfloor . \end{aligned}$$
(1)

In the second case, when \(c \ge \lfloor (2n+1)/3\rfloor +1 = \lfloor (2n+4)/3\rfloor \), we develop an augmentation algorithm that uses a convex subdivision of G. A convex subdivision H is obtained from G by successively shooting rays from the reflex vertices of all nonsingleton components of G, similar to [2]. The isolated vertices of G lie in the interiors of the convex cells of H. For every convex subdivision H constructed in this way, we derive an upper bound for the number of cells h.

FormalPara Lemma 1

Let G be a PSLG with n vertices, b bridges, and c components. Then every convex subdivision of G has at most \(h \le 2n-2c-b+1\) cells.

We augment G successively with new edges, and we always denote by \(G'\) the current graph. Graph \(G'\) is a planar straight line multigraph (PSLMG). Let \(T\subseteq G'\) denote the set of nonsingleton connected components in \(G'\).

Our augmentation algorithm works as follows:

  1. 1.

    Construct a convex subdivision H of G. Let \(C=\{C_i: i=1\ldots h\}\) be the set of convex cells. Compute T.

  2. 2.

    For each cell \(C_i\in C\): (a) for each nonsingleton component adjacent to \(C_i\) select an arbitrary vertex incident to \(C_i\); (b) connect the selected vertices and singleton vertices in the cell \(C_i\) into a simple polygon; (c) recompute T.

  3. 3.

    Replace each bridge of \(G'\) by a double edge.

  4. 4.

    Transform the multigraph \(G'\) into a simple graph.

In step 2 we add \(c+h-1\) edges. Since we do not create any new bridges in step 2, we add b edges in step 3. The total number of new edges \(e'\) added is \(e'\le c + h -1 + b\). By Lemma 1, since \(c\ge \lfloor (2n+4)/3\rfloor \), we obtain:

$$\begin{aligned} e'\le c + h -1 +b\le 2n - c\le 2n - \bigg \lfloor {\frac{2n+4}{3}}\bigg \rfloor \le \bigg \lfloor {\frac{4n-4}{3}}\bigg \rfloor . \end{aligned}$$
(2)

In step 4 we can transform the 2-edge-connected multigraph \(G'\) into a 2-edge-connected simple graph without increasing the number of edges by Lemma 2.

FormalPara Lemma 2

[1] Let \(G'\) be a 2-edge-connected PSLMG and let e be a double edge in \(G'\). Then we can obtain a 2-edge-connected PSLMG from \(G'\) by decrementing the multiplicity of e by one and adding at most one new edge of multiplicity 1.