|
Abstract:
Laman's characterization of minimally rigid 2-dimensional generic
frameworks gives a matroid structure on the edge set of the underlying
graph, as was first pointed out and exploited by L. Lovasz and Y.
Yemini. Global rigidity has only recently been characterized by a
combination of two results due to T. Jordan B. Jackson, and R.Connelly,
respectively. We use these characterizations to investigate how graph
theoretic properties such as transitivity, connectivity and regularity
influence (2-dimensional generic) rigidity and global rigidity and
apply some of these results to reveal rigidity properties of random
graphs.
In particular, we characterize the globally rigid vertex transitive
graphs, and show that a random d-regular graph is asymptotically almost
surely globally rigid for all d greater than or equal to 4.
This is joint work with Bill Jackson and Herman Servatius
|
