Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE EIGHTH INTERNATIONAL CONFERENCE ON CIVIL AND STRUCTURAL ENGINEERING COMPUTING
Edited by: B.H.V. Topping
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
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  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  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  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.
purchase the full-text of this paper (price £20)
go to the previous paper