Pebble games for rigidity Overview Introduction The game of pebbling was first suggested by Lagarias and Saks, as a tool for solving a particular problem in number theory. The

algorithm can be used for analyzing the rigidity and flexibility of a variety of structures (mechanisms, molecules exc. ) Rigidity in 2D Bar and Joint Introduced by Jacobs & Hendrickson 1997 , based on Laman condition Laman

graph of n vertices (1970) The whole graph has exactly 2n 3 edges For all k, every k-vertex subgraph has at most 2k 3 edges The graph describes a minimally rigid systems of rods (edges) and joints (vertices) in the plane. What does Laman mean? For the whole

graph |e|+3=2|v| |e|=2|v|-3 Number of edges (constrains) For Trivial DOFs of a Number of body in 2D vertices x 2 DOFs of a point

in 2D The edges (constrains) subgraphs are well distributed |e|2|v|-3 Laman condition Taking Laman condition literally leads to exponential time complexity Every sub-graph must be tested for the number

of vertices vs. edges Alternate Laman condition: The edges in G are independent in 2D if and only if for each edge (a, b), the graph formed by quadrupling (a, b) has no induced subgraph of k nodes and >2k edges => Building the graph from sub-graph and

testing each new edge for independence leads to polynomial time complexity Example Lets take the 2D undirected graph and run pebble game in 2D Corresponds to 2D bar & joint floating framework Example Lets take a floating bar and joint framework in 2D

Each vertex is given two pebbles, corresponding to the two degrees of freedom of a point in 2D A vertex can use its pebbles to cover any two edges which are incident to that vertex. Starting point is arbitrary. Building directed graph We will build directed edges by extending independent sub-group Quadrupling each new edge to test

independence with the sub-group we already have Quadrupl e the edge Begin with a single vertex (clearly independent) Direct an edge move General direct an edge move If i and j are vertices with two pebbles on each (corresponding to independent constraint), add the edge ij (oriented toward j) and pick up one of the

pebbles from i. In case 2 pebbles cannot be found at the ends of that constraint after an exhaustive search, the constraint is redundant (and therefore can to be directed). Pebble slide move Pebble slide move If ij is an edge in the pebble game's graph and there is a on j, reverse ij and move the pebble from j to i. pebble

Result The algorithm ends when all the edges have been processed. Result : 3 pebbles (only trivial DOFs) Redundant edge What happens to over constraints ? example with SS :

Any edge that cant be directed corresponds to redundant constraint. This happens when the length between its end point is already set by other constrains. Inside the rigid region any edge can be redundant. DOF number The resulting number of pebbles after all edges were processed, gives the number of DOFs of the corresponding

mechanism. For floating mechanism there are 3 trivial DOFs => 3 remaining pebbles is an indicator for rigidity For grounded mechanism 0 pebbles indicate rigidity (edges linked to gnd vertices are directed in the end, with any free pebble) Actually this is the number of non preset vertices (that have pebbles = DOFs)

Partition to Assur graphs A directed cut defines a partition to Assur graphs. Algorithm summary Find a subset of independent edges. Use an incremental algorithm: pick an edge, test if its independent of the current subset. Alternate Laman theorem: The edges in G are independent in 2D if and only if for each edge (a, b), the graph formed by

quadrupling (a, b) has no induced subgraph of k nodes and >2k edges Grow a maximal set of independent edges one at a time. New edge is added if it is independent of existing set. Quadruple the new edge and test the Laman condition. If Laman failed, then output not rigid. If 2n-3 independent edges are found, then graph is rigid (n = number of vertices). Testing an edge for independence takes O(n) time: we do 3 depth-first search in a graph with O(n) edges. At most m edges will be tested. The total running time is O(nm)

Rigidity in 2D Body & Bar Body & Bar subgroup of Bar & Joint Graph representation: Every rigid body = vertex The rest are bars Laman for Body & Bar in 2D

Laman graph for this case: The whole graph has exactly 3n 3 edges For all k, every k-vertex subgraph has at most 3k 3 edges |e|+3=3|v| Number of edges

(constrains) Trivial DOFs of a Number of body in 2D vertices x 3 DOFs of a body in 2D Pebble game for Body & Bar 2D Every vertex is given 3 pebbles The condition to direct an edge is

to have 4 pebbles on the incident vertices The rest is the same (example follows) Example Bb 2D 4 1 1 Grounded body (vertex)

2 3 Grounded mechanism with 1 DOF Partition to Assur groups : 4 can be analyzed as stand alone (dyad) Rigidity in 3D Body and bar Introduced by Tay and Whiteley Vertices -> rigid bodies

Edges -> bars Hinge = 5 bars Laman graph for this case: The whole graph has exactly 6n 6 edges For all k, every k-vertex subgraph has at most 6k 6 edges Need edge

at least 7 pebbles to direct an Examples Minimally rigid Flexible with 1 DOF Thank You !