Basser Seminar Series

Combinatorial Rigidity: Theory, Algorithms and Applications

Speaker: Professor Naoki Katoh
Kyoto University

Time: Friday 27 August 2010, 4:00-5:00pm
Refreshments will be available from 3:30pm

Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Add seminar to my diary


A set of rigid bars connected by pin joints in two or three dimensional space is called a framework. A framework is called rigid if it cannot be deformed to a non-congruent framework by perturbing the positions of joints. The central issue of a rigidity theory is to test whether a framework is rigid or not and to determine the rigid portion of a framework if it is not rigid. Rigidity theory has a wide range of applications such as mechanical and structural engineering, behavior analysis of molecules, sensor networks, robotics, CAD, and so on. The abstract essense of a framework can be modeled as a graph. Then, the theory of combinatroial rigidity determines the rigidity of a framework by examining the mathematical properties of the underlying graph.

In this talk, we will give an introduction to combinatorial rigidity, as well as our recent results concerning molecular conjecture, and explain applications in mechanical and structural engineering, molecular biology, and sensor networks.

Speaker's biography

Naoki Katoh has obtained his PhD from Kyoto University in 1981 and now is a professor of Kyoto University, Japan since 1997 where he teaches optimization theory, data mining, and etc. He has been working in the field of combinatorial optimization, computational geometry and data mining.