Relay placement for two-connectivity

Motivated by applications to wireless sensor networks, we study the following problem. We are given a set SS of wireless sensor nodes, given as a multiset of points in a normed space. We seek to place a minimum-size (multi)set QQ of wireless relay nodes in the normed space such that the unit-disk graph induced by Q∪SQ∪S is two-connected. The unit-disk graph of a set of points has an edge between two points if their distance is at most 1.In Infocom 2006, Kashyap, Khuller, and Shayman present two algorithms, for the two variants of the problem: two-edge-connectivity and biconnectivity. For both they prove an approximation ratio of 2dMST2dMST, where dMSTdMST is the maximum degree of a minimum-degree Minimum Spanning Tree in the normed space. It is known that in the Euclidean two-dimensional space, dMST=5dMST=5, and in the three dimensional space, dMST=12dMST=12.We give a tight analysis of variants of the same algorithms, obtaining approximation ratios of dMSTdMST for biconnectivity and 2dMST−12dMST−1 for two-edge-connectivity respectively. To do so we prove additional structural properties regarding bypassing Steiner nodes in biconnected graphs.