ABSTRACT
This chapter presents the sufficient and necessary conditions for dimensional rigidity. A necessary and sufficient condition for dimensional rigidity was given by R. Connelly and S. J. Gortler based on the Borwein–Wolkowicz facial reduction algorithm. In addition to being a fundamental problem in distance geometry, the universal rigidity problem of bar frameworks has many important applications in multidimensional scaling in statistics, molecular conformations in chemistry and in ad hoc wireless sensor networks. The universal rigidity problem can be addressed by separately addressing its two easier subproblems, namely dimensional rigidity and affine motions. Many universal rigidity results are direct application of known facts in semidefinite programming. The chapter discusses several universal rigidity results for some special classes of graphs, namely r-lateral graphs, chordal graphs and complete bipartite graphs. Universal rigidity of bar frameworks has a complete characterization under the generic assumption.
