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 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]**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)**

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