Abstract
Recent results have confirmed that the global rigidity of bar-and-joint frameworks on a graph G is a generic property in Euclidean spaces of all dimensions. Although it is not known if there is a deterministic algorithm that runs in polynomial time and space, to decide if a graph is generically globally rigid, there is an algorithm (Gortler et al. in Characterizing generic global rigidity, arXiv:0710.0907v1, 2007) running in polynomial time and space that will decide with no false positives and only has false negatives with low probability. When there is a framework that is infinitesimally rigid with a stress matrix of maximal rank, we describe it as a certificate which guarantees that the graph is generically globally rigid, although this framework, itself, may not be globally rigid. We present a set of examples which clarify a number of aspects of global rigidity.
There is a technique which transfers rigidity to one dimension higher: coning. Here we confirm that the cone on a graph is generically globally rigid in ℝd+1 if and only if the graph is generically globally rigid in ℝd. As a corollary, we see that a graph is generically globally rigid in the d-dimensional sphere \(\mathbb{S}^{d}\) if and only if it is generically globally rigid in ℝd.
Article PDF
Similar content being viewed by others
References
Anderson, B.D.O., Belhumeur, P., Eren, T., Goldenberg, D., Morse, A.S., Whiteley, W., Yang, Y.: Graphical properties of easily localizable sensor networks. Wirel. Netw. 15(2), 177–191 (2009)
Bolker, E.D., Roth, B.: When is a bipartite graph a rigid framework? Pac. J. Math. 90(1), 27–44 (1980)
Berg, A., Jordán, T.: A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid. J. Comb. Theory, Ser. B 88, 77–97 (2003)
Cheung, M., Whiteley, W.: Transfer of global rigidity results among dimensions: graph powers and coning. Preprint, York University, Revised 2008
Connelly, R.: Rigidity and energy. Invent. Math. 66(1), 11–33 (1982)
Connelly, R.: On generic global rigidity. In: Applied Geometry and Discrete Mathematics. DIMACS Ser. Discrete Math, Theoret. Comput. Sci., vol. 4, pp. 147–155. AMS, Providence (1991)
Connelly, R.: Generic global rigidity. Discrete Comput. Geometry 33, 549–563 (2005)
Connelly, R., Jordán, T., Whiteley, W.: Generic global rigidity of body bar frameworks. Preprint (2009)
Eren, T., Goldenberg, D., Whiteley, W., Morse, A., Anderson, B.D.O., Belhumeur, P.: Rigidity, computation, and randomization in network localization. In: Proceedings of the International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Hong Kong, March 2004, pp. 2673–2684
Gortler, S., Healy, A., Thurston, D.: Characterizing generic global rigidity. arXiv:0710.0907v1 (2007)
Graver, J.: Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures. Dolciani Mathematical Expositions, vol. 25. The Mathematical Association of America, Washington (2001)
Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21, 65–84 (1992)
Jackson, B., Jordán, T.: Connected rigidity matroids and unique realization graphs. J. Comb. Theory B 94, 1–29 (2005)
Jackson, B., Jordán, T., Szabadka, Z.: Globally linked pairs of vertices in equivalent realizations of graphs. Discrete Comput. Geom. 35(3), 493–512 (2006)
Jordán, T., Szabadka, Z.: Operations preserving the global rigidity of graphs and frameworks in the plane. Comput. Geom. 42(6-7), 511–521 (2009)
Pogorelov, A.V.: A Study of Surfaces in an Elliptic Space, (English Translation of the Russian Title “Nekotorye Voprosy Teorii Poverkhnostei”) Hindustan Publishing Corporation (India) 6-U.B., Jawahar Nagar, DELHI-6 (1964)
Saliola, F., Whiteley, W.: Some notes on the equivalence of first-order rigidity in various geometries. Preprint Department of Mathematics, York University (2002)
Saliola, F., Whiteley, W.: Averaging and equivalent frameworks: transfer among various geometries. Draft, Department of Mathematics, York University (2005)
Tay, T.-S., Whiteley, W.: Generating isostatic frameworks. Structural Topology 11, 20–69 (1985)
Whiteley, W.: Cones, infinity and one-story buildings. Struct. Topol. 8, 53–70 (1983)
Whiteley, W.: Vertex splitting in isostatic frameworks. Struct. Topol. 16, 23–30 (1991)
Whiteley, W.: Matroids from discrete geometry, In: Bonin, J.E., Oxley, J.G., Servatius, B. (eds.) Matroid Theory. American Mathematical Society, Contemporary Mathematics, vol. 197, pp. 171–313 (1996)
Whiteley, W.: Rigidity and Scene Analysis, In: Goodman, J., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1327–1354 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of the first author supported in part by NSF Grant No. DMS-0209595 (USA).
Work of the second author supported in part by a grant from NSERC (Canada).
Rights and permissions
About this article
Cite this article
Connelly, R., Whiteley, W.J. Global Rigidity: The Effect of Coning. Discrete Comput Geom 43, 717–735 (2010). https://doi.org/10.1007/s00454-009-9220-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9220-0