How to test that this 3D graph is rigid?

379 Views Asked by At

I have constructed a lattice as a 3D graph while ensuring that it is rigid. I would like to find a way to test it to verify. Any thoughts? Links to papers?

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

This seems to be an open problem.

The Laman condition in 2D does not have a neat extension to 3D. The following condition is necessary but not sufficient for rigidity in 3D : the graph must have $3n - 6$ edges and no subgraph of $k$ vertices has more than $3k- 6$ edges. The combinatorial condition for rigidity in 3D is a long standing open problem. We will state the theorem of global rigidity before we move to the next section on the computational aspect of testing rigidity.

This link is probably a good starting point: http://www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf