Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

CivilComp Proceedings
ISSN 17593433 CCP: 73
PROCEEDINGS OF THE EIGHTH INTERNATIONAL CONFERENCE ON CIVIL AND STRUCTURAL ENGINEERING COMPUTING 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
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", CivilComp Press, Stirlingshire, UK, Paper 15, 2001. doi:10.4203/ccp.73.15
Keywords: rigidity, graph, truss, matching, decomposition, Henneberg sequence, generic independence.
Summary
Introduction
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 pinnedjoints 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 nonempty subset of . For any subset of , is defined as , where . is stiff there exists such that and for every nonempty subset of . is stiff and generically independent if and for every nonempty 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. References
purchase the fulltext of this paper (price £20)
go to the previous paper 
