Given a Laman graph G, i.e. a minimally rigid graph in R2, we provide a Θ(n2) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP‐hard for an arbitrary rigid graph G in R2.
