The rigidity of graphs
Authors:
L. Asimow and B. Roth
Journal:
Trans. Amer. Math. Soc. 245 (1978), 279289
MSC:
Primary 57M15; Secondary 05C10, 52A40, 53B50, 73K05
DOI:
https://doi.org/10.1090/S00029947197805114109
MathSciNet review:
511410
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: We regard a graph G as a set $\{ 1, \ldots , v \}$ together with a nonempty set E of twoelement subsets of $\{ 1, \ldots , v \}$. Let $p = ({p_1},\ldots ,{p_v})$ be an element of ${\textbf {R}^{nv}}$ representing v points in ${\textbf {R}^n}$. Consider the figure $G(p)$ in ${\textbf {R}^n}$ consisting of the line segments $[{p_i},{p_j}]$ in ${\textbf {R}^n}$ for $\{ i,j\} \in E$. The figure $G(p)$ is said to be rigid in ${\textbf {R}^n}$ if every continuous path in ${\textbf {R}^{nv}}$, beginning at p and preserving the edge lengths of $G(p)$, terminates at a point $q \in {\textbf {R}^{nv}}$ which is the image $(T{p_1}, \ldots ,T{p_v})$ of p under an isometry T of ${\textbf {R}^n}$. Otherwise, $G(p)$ is flexible in ${\textbf {R}^n}$. Our main result establishes a formula for determining whether $G(p)$ is rigid in ${\textbf {R}^n}$ for almost all locations p of the vertices. Applications of the formula are made to complete graphs, planar graphs, convex polyhedra in ${\textbf {R}^3}$, and other related matters.

D. Barnette and B. Grünbaum, On Steinitz’s theorem concerning convex 3polytopes and on some properties of planar graphs, The Many Facets of Graph Theory, Lecture Notes in Math., vol. 110, SpringerVerlag, Berlin, 1969, pp. 2740.
 Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Springer, Berlin, 1975, pp. 225–239. Lecture Notes in Math., Vol. 438. MR 0400239
 G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI https://doi.org/10.1007/BF01534980
 John Milnor, Singular points of complex hypersurfaces, Annals of Mathematics Studies, No. 61, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1968. MR 0239612
 A. H. Wallace, Algebraic approximation of curves, Canadian J. Math. 10 (1958), 242–278. MR 94355, DOI https://doi.org/10.4153/CJM19580285
Retrieve articles in Transactions of the American Mathematical Society with MSC: 57M15, 05C10, 52A40, 53B50, 73K05
Retrieve articles in all journals with MSC: 57M15, 05C10, 52A40, 53B50, 73K05
Additional Information
Article copyright:
© Copyright 1978
American Mathematical Society