Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 73
Edited by: B.H.V. Topping
Paper 15

Efficient Graph Theoretical Methods for Examining the Rigidity of Planar Trusses

A. Kaveh+ and F.N. Ehsani*

+Iran University of Science and Technology, Narmak, Tehran, Iran
*Mazandaran University of Sciences and Technologies, Babol, Iran

Full Bibliographic Reference for this paper
A. Kaveh, F.N. Ehsani, "Efficient Graph Theoretical Methods for Examining the Rigidity of Planar Trusses", in B.H.V. Topping, (Editor), "Proceedings of the Eighth International Conference on Civil and Structural Engineering Computing", Civil-Comp Press, Stirlingshire, UK, Paper 15, 2001. doi:10.4203/ccp.73.15
Keywords: rigidity, graph, truss, matching, decomposition, Henneberg sequence, generic independence.


The first combinatorial approach to the study of rigidity is due to Laman [2] who found the necessary and sufficient conditions for a graph to be rigid, when its member and nodes correspond to rigid rods (bars) and rotatable pinned-joints of a planar truss. Two main types of methods are discussed for recognizing the generic independence of graphs, which use complete matching and decomposition approaches. The Edmonds' algorithm is studied in detail and a computer code is developed based on the modified version of the Edmonds' algorithm. A second algorithm is presented based on the Henneberg sequence.

Methods for Examining the Rigidity of Trusses

Laman proved a basic theorem on rigidity as follows: The graph is generically independent if and only if for any non-empty subset of . For any subset of , is defined as , where . is stiff there exists such that and for every non-empty subset of . is stiff and generically independent if and for every non-empty subset .

This method is developed by Sugihara [3] and it is a polynomial bounded algorithm. The method uses the following theorem for the recognition. The graph model is generically independent if for any and , has a complete matching with respect to .

Lovász and Yemini [4] proved a theorem that a graph is generically independent iff doubling any member of results in a graph, which is the union of two forests. Graph is stiff and generically independent (isostatic) if doubling any member of results in a graph that is the union of two spanning trees.

A. Kaveh, Structural Mechanics: Graph and Matrix Methods, RSP (John Wiley), UK, 1995.
G. Laman, On graphs and rigidity of plane skeletal structures, J. Eng. Math., 4, 331�340, 1970. doi:10.1007/BF01534980
K. Sugihara, On some problems in the design of plane skeletal structures, SIAM J. Alg. Disc. Meth., 4, 335�362, 1983. doi:10.1137/0604035
L. Lovász, and Y. Yemini, On generic rigidity in the plane, SIAM J. Alg. Disc. Meth., 3, 91-98, 1982. doi:10.1137/0603009
J. Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standard Sect. B, 69B, 67�72,1965.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description