The rigidity of graphs
Authors:
L. Asimow and B. Roth
Journal:
Trans. Amer. Math. Soc. 245 (1978), 279-289
MSC:
Primary 57M15; Secondary 05C10, 52A40, 53B50, 73K05
DOI:
https://doi.org/10.1090/S0002-9947-1978-0511410-9
MathSciNet review:
511410
Full-text 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 two-element 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 3-polytopes and on some properties of planar graphs, The Many Facets of Graph Theory, Lecture Notes in Math., vol. 110, Springer-Verlag, Berlin, 1969, pp. 27-40.
- 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/CJM-1958-028-5
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