Abstract | ||
---|---|---|
We show that any graph that is generically globally rigid in ℝd has a realization in ℝd that is both generic and universally rigid. This also implies that the graph also must have a realization in ℝd that is both infinitesimally rigid and universally rigid; such a realization serves as a certificate of generic global rigidity. Our approach involves an algorithm by Lovász, Saks and Schrijver that, for a sufficiently connected graph, constructs a general position orthogonal representation of the vertices, and a result of Alfakih that shows how this representation leads to a stress matrix and a universally rigid framework of the graph. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1007/s00493-018-3694-4 | Combinatorica |
Keywords | Field | DocType |
52C25, 05C62 | Rigidity (psychology),Topology,Discrete mathematics,Graph,General position,Vertex (geometry),Matrix (mathematics),Connectivity,Mathematics,Infinitesimal,Certificate | Journal |
Volume | Issue | ISSN |
40 | 1 | 0209-9683 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Robert Connelly | 1 | 5 | 2.20 |
Steven J. Gortler | 2 | 4205 | 366.17 |
Louis Theran | 3 | 106 | 16.33 |