Treffer: Globally Linked Pairs and Cheapest Globally Rigid Supergraphs.

Given a graph \(G\) , a cost function on the non-edges of \(G\) , and an integer \(d\) , the problem of finding a cheapest globally rigid supergraph of \(G\) in \(\mathbb{R}^d\) is NP-hard for \(d\geq 1\). For this problem, which is a common generalization of several well-studied graph augmentation problems, no approximation algorithm has previously been known for \(d\geq 2\). Our main algorithmic result is a 5-approximation algorithm in the \(d=2\) case. We achieve this by proving numerous new structural results on rigid graphs and globally linked vertex pairs. In particular, we show that every rigid graph in \(\mathbb{R}^2\) has a tree-like structure, which conveys all the information regarding its globally rigid augmentations. Our results also yield a new, simple solution to the minimum cardinality version (where the cost function is uniform) for rigid input graphs, a problem which is known to be solvable in polynomial time. [ABSTRACT FROM AUTHOR]