The rigidity of graphs
Authors:
L. Asimow and B. Roth
Journal:
Trans. Amer. Math. Soc. 245 (1978), 279289
MSC:
Primary 57M15; Secondary 05C10, 52A40, 53B50, 73K05
MathSciNet review:
511410
Fulltext 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 twoelement 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 3polytopes and on some properties of planar graphs, The Many Facets of Graph Theory, Lecture Notes in Math., vol. 110, SpringerVerlag, Berlin, 1969, pp. 2740.
 [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
(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]
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
(39 #969)
 [5]
A.
H. Wallace, Algebraic approximation of curves, Canad. J. Math.
10 (1958), 242–278. MR 0094355
(20 #873)
 [1]
 D. Barnette and B. Grünbaum, On Steinitz's theorem concerning convex 3polytopes and on some properties of planar graphs, The Many Facets of Graph Theory, Lecture Notes in Math., vol. 110, SpringerVerlag, Berlin, 1969, pp. 2740.
 [2]
 H. Gluck, Almost all simply connected closed surfaces are rigid, Geometric Topology, Lecture Notes in Math., no. 438, SpringerVerlag, Berlin, 1975, pp. 225239. MR 0400239 (53:4074)
 [3]
 G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331340. 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), 242278. 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
DOI:
http://dx.doi.org/10.1090/S00029947197805114109
PII:
S 00029947(1978)05114109
Article copyright:
© Copyright 1978
American Mathematical Society
