Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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
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.

References [Enhancements On Off] (What's this?)

    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
  • 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

Similar Articles

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