Pebble Game (Rigidity)

In the study of combinatoric rigidity the pebble game algorithm was developed as an efficient way of determining whether a given graph is rigid. The algorithm was originally devised for study of rigidity percolation in two dimensions^[1] and has remained one of the main tools utilized in this field. The pebble game algorithm not only determines whether a given graph is rigid but also identifies rigid, floppy and over constrained regions. It is important to note that the type of rigidity assessed by this algorithm is combinatoric or generic rigidity which follows from the Geiringer-Laman theorem.

There are many variants of the pebble game algorithm, each constructed for a different physical context. The original pebble game^[1] was proposed for graphs embedded in the two-dimensional flat plane, without any fixed or grounded elements. This pebble game can be referred to as the (2,3) pebble game.

The ${\displaystyle (k,l)}$ Pebble Game ^[3] takes in as input an undirected graph G and assigns k pebbles to each vertex. Each edge is then checked one at a time. For an edge ${\displaystyle (\mu ,\nu )}$ if the number of pebbles on ${\displaystyle \mu }$ and ${\displaystyle \nu }$ totals ${\displaystyle l+1}$ then one of the ${\displaystyle l+1}$ pebbles is used to cover the edge. This edge is now directed. In Jacobs and Hendrickson's original work this direction was as follows: if the pebble was taken from vertex ${\displaystyle \mu }$ then the edge was directed away from ${\displaystyle \mu }$, similarly for the other vertex. If ${\displaystyle l+1}$ pebbles are not found on the vertices ${\displaystyle \mu }$ and ${\displaystyle \nu }$ then a pebble search is performed on each vertex. The pebble search consist of finding a directed path from the given vertex to a free pebble(one not currently covering an edge). This is done by means of a depth-first search on the directed graph and is optimized by keeping memory of the vertices encountered in failed searches. If a pebble is found it is "brought to" the given vertex and the directed path is reversed. This process repeats until the number of pebbles on ${\displaystyle \mu }$ and ${\displaystyle \nu }$ totals ${\displaystyle l+1}$ . If this is achieved the edge is covered as before if not the edge is not covered and is instead marked as redundant. This process is repeated for each edge. The order in which the edges are checked is arbitrary. The Pebble Game then gives as output a graph that is in general partially covered, un-covered edges are the redundant edges, and some vertices having free pebbles which were not spent in the covering of edges.

A number of properties of the generic realizations of the graph can be read off of the output of the (2,3) pebble game.

Rigidity: A graph will be rigid in the plane if and only if the output contains only 3 free pebbles.

Mechanisms: The number of linearly independent isometries, motions that do not change the length of any edge, is given by the number of free pebbles. Mechanisms(also called floppy modes) exclude the three rigid motions, two translations one rotation, therefore the number of free pebbles minus three gives the number of mechanisms.

Self Stresses: The number of redundant edges,( un-covered edges) equals the number of linearly independent self stresses, which is to say assignments of tensions on the edges that satisfy in force balance on each vertex.

It is worth noting that the orientation of the covered portion of the graph allows for the determination of these properties, rigidity, mechanisms and self-stress, for sub-graphs. This is exploited in the identification of rigid clusters.

A basic implementation of the pebble game algorithm would be as follows.

function  Check_Edge((u,v),pebble_index)  is
	
     Pebbles_Found :=  0
     fail_region={}

     for 1 ≤ i ≤ 2  do
          found,pebble_index,fail_region:= Find_Pebble(u, pebble_index,fail_region)
	  if found then
	       Pebbles_Found:= Pebbles_Found+1

	       found,pebble_index,fail_region:= Find_Pebble(v, pebble_index,fail_region)
	       if found then
	            Pebbles_Found := Pebbles_Found+1
     repeat

	if Pebbles_Found=4 then
		pebble_index :=Cover_Edge((u,v),pebble_index)
	
return pebble_index

function Pebble_Game(G) is:

     initialize pebble_index

     for (u,v) in G do:
          pebble_index=Check_Edge((u,v),pebble_index)
     repeat

return G,pebble_index

Where the Find_Pebble function does the pebble searches and the pebble index is an array like structure that encodes the placement of the pebbles, weather they are free or, if used to cover a bond, which bond they are covering. The fail_region is the set of all vertices found during failed pebble searches. This information is crucial for optimization.^[1]

The output of the pebble game algorithm is often used to identify rigid clusters, which is to say maximal rigid subgraphs. In the (2,3) pebble game, to determine if two edges are rigid with respect to each other three pebbles are fixed on the vertices incident on one edge. Then, a fourth pebble is called to one of the vertices of the second edge, if the pebble cannot be found then the edges are mutually rigid, otherwise they are mutually floppy. A maximal set of edges where all of them are mutually rigid is identified as a rigid cluster.

In actuality it is not true that every edge pair has to be checked in order to identify all rigid clusters. The algorithm is made more efficient by utilizing the fact that all edges traversed during a failed pebble search are mutually rigid.

The pebble game has been adapted to graphs obtained from a physical scenarios distinct from free standing on the flat two dimensional plane. Some examples:

• For pinned graphs on the plane, which have some vertices fixed to the ground.^[4]
• (3,3) Pebble game for frictional jamming in 2d.^[5]
• For some free standing graphs in 3d referred to as bond bending networks. ^[6]
• For graphs embedded on the flat 2d torus, also infinite periodic graphs.^[7]
  

• Laman Graph
• Geiringer-Laman theorem