Operations preserving the global rigidity of graphs and frameworks in the plane

T Jordán, Z Szabadka - Computational Geometry, 2009 - Elsevier
T Jordán, Z Szabadka
Computational Geometry, 2009Elsevier
A straight-line realization of (or a bar-and-joint framework on) graph G in Rd is said to be
globally rigid if it is congruent to every other realization of G with the same edge lengths. A
graph G is called globally rigid in Rd if every generic realization of G is globally rigid. We
give an algorithm for constructing a globally rigid realization of globally rigid graphs in R2. If
G is triangle-reducible, which is a subfamily of globally rigid graphs that includes Cauchy
graphs as well as Grünbaum graphs, the constructed realization will also be infinitesimally …
A straight-line realization of (or a bar-and-joint framework on) graph G in Rd is said to be globally rigid if it is congruent to every other realization of G with the same edge lengths. A graph G is called globally rigid in Rd if every generic realization of G is globally rigid. We give an algorithm for constructing a globally rigid realization of globally rigid graphs in R2. If G is triangle-reducible, which is a subfamily of globally rigid graphs that includes Cauchy graphs as well as Grünbaum graphs, the constructed realization will also be infinitesimally rigid. Our algorithm relies on the inductive construction of globally rigid graphs which uses edge additions and one of the Henneberg operations. We also show that vertex splitting, which is another well-known operation in combinatorial rigidity, preserves global rigidity in R2.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果