Augmenting the Rigidity of a Graph in R (2)

作者：Garcia A; Tejel J^*

来源：Algorithmica, 2011, 59(2): 145-168.

DOI：10.1007/s00453-009-9300-9

• Rigid graph
• Laman graph
• Augmenting problem
• NP-completeness

Given a Laman graph G, i.e. a minimally rigid graph in R (2), we provide a I similar to(n (2)) 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 R (2).

• 出版日期2011-2