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?)

  • [1] 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.
  • [2] H. Gluck, Almost all simply connected closed surfaces are rigid, Geometric Topology, Lecture Notes in Math., no. 438, Springer-Verlag, Berlin, 1975, pp. 225-239. MR 0400239 (53:4074)
  • [3] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331-340. MR 0269535 (42:4430)
  • [4] J. Milnor, Singular points of complex hypersurfaces, Ann. of Math. Studies, no. 61, Princeton Univ. Press, Princeton, N.J., 1968. MR 0239612 (39:969)
  • [5] A. Wallace, Algebraic approximation of curves, Canad. J. Math. 10 (1958), 242-278. MR 0094355 (20:873)

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

American Mathematical Society