Graph Connectivity

Connectivity augmentation is a classical problem in graph theory with application in network design, e.g., for telecommunications network.

A planar straight line graph (PSLG) is a graph G=(V,E), where V is a set of distinct points in the plane, and E is a set of straight line segments between the points in V such that two segments may intersect at their endpoints only.

Given a PSLG G=(V,E) and an integer k, the embedding preserving connectivity (resp., edge-connectivity) augmentation problem asks for a set of new edges F of minimal cardinality such that G=(V,E union F) is a k-connected (resp., k-edge connected) PSLG.

Preserving the embedding of the input graph is an important restriction. For example, a path (as an abstract graph) can be augmented to a 2-connected graph by adding one new edge, but it takes n-2 (resp., floor of n/2) new edges to augment a "zig-zag" path with n vertices in convex position in the plane to a 2-connected (resp., 2-edge connected) PSLG; see the illustration for augmentation of the graph that preserves its (vertex) connectivity.

It is easy to check that every PSLG with n ≥ 2 vertices and p connected components can be augmented to a connected PSLG by adding at most p-1 new edges. It is also known that every connected PSLG G with n ≥ 3 vertices and b ≥ 2 distinct 2-connected blocks can be augmented to a 2-connected PSLG by adding at most b-1 new edges. Every connected PSLG with n ≥ 3 vertices can be augmented to a 2-edge connected PSLG by adding at most floor((2n - 2)/3) new edges; see next figure depicting a PSLG on n=18 vertices that requires at least 12 new edges to become 2-connected or 2-edge connected. Can you find the appropriate graph augmentation (if not, the solution key may be found here)?

These bounds are tight in the worst case.

If you would like to learn more about this project, please contact Dr. Csaba D. Toth.

Selected references:

1. M. Abellanas, A. Garcia, F. Hurtado, J. Tejel, J. Urrutia, Augmenting the connectivity of geometric graphs, Comput. Geom. Theory Appl. 40 (3) (2008), 220-230.
2. Cs. D. Toth, Connectivity augmentaion in planar straight line graphs, 2008, manuscript. http://math.ucalgary.ca/~cdtoth/2edgecon18.pdf Also in: Proc. Intl. Conf. on Topological and Geometric Graph Theory (Paris, 2008), pp. 51-54.
3. Cs. D. Toth and P. Valtr, Augmenting the edge connectivity of planar straight line graphs to three, in Proc. XIII Spanish Meeting on Comput. Geom. (Zaragoza 2009), to appear. http://math.ucalgary.ca/~cdtoth/3edgeconTV.pdf