Globally linked pairs and cheapest globally rigid supergraphs

Tibor Jordán, Soma Villányi

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…