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

Abstract | References | Similar Articles | Additional Information

Abstract: We regard a graph *G* as a set together with a nonempty set *E* of two-element subsets of . Let be an element of representing *v* points in . Consider the figure in consisting of the line segments in for . The figure is said to be rigid in if every continuous path in , beginning at *p* and preserving the edge lengths of , terminates at a point which is the image of *p* under an isometry *T* of . Otherwise, is flexible in . Our main result establishes a formula for determining whether is rigid in for almost all locations *p* of the vertices. Applications of the formula are made to complete graphs, planar graphs, convex polyhedra in , and other related matters.

**[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]**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****[3]**G. Laman,*On graphs and rigidity of plane skeletal structures*, J. Engrg. Math.**4**(1970), 331–340. MR**0269535**, https://doi.org/10.1007/BF01534980**[4]**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****[5]**A. H. Wallace,*Algebraic approximation of curves*, Canad. J. Math.**10**(1958), 242–278. MR**0094355**, 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

DOI:
https://doi.org/10.1090/S0002-9947-1978-0511410-9

Article copyright:
© Copyright 1978
American Mathematical Society