An algorithm for two-dimensional rigidity percolation: The pebble game

DOI10.1006/jcph.1997.5809zbMath0894.73004OpenAlexW2121403868MaRDI QIDQ1375495

Donald J. Jacobs, Bruce A. Hendrickson

Publication date: 28 January 1998

Published in: Journal of Computational Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcph.1997.5809

zbMATH Keywords

graph algorithm graph rigidity floppy modes network glass number of internal degrees of freedom overconstrained regions rigid clusters vector percolation

Mathematics Subject Classification ID

Applications of graph theory (05C90) Inhomogeneity in solid mechanics (74E05) Composite and mixture properties (74E30)

Related Items

The unassigned distance geometry problem ⋮ A characterisation of the generic rigidity of 2-dimensional point-line frameworks ⋮ FlexRiLoG—A SageMath Package for Motions of Graphs ⋮ Sparse Graphs and an Augmentation Problem ⋮ Enumerating non-crossing minimally rigid frameworks ⋮ Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials ⋮ Combinatorial Rigidity and Independence of Generalized Pinned Subspace-Incidence Constraint Systems ⋮ Characterizing graphs with convex and connected Cayley configuration spaces ⋮ Stable Camera Motion Estimation Using Convex Programming ⋮ Generic Symmetry-Forced Infinitesimal Rigidity: Translations and Rotations ⋮ The Number of Realizations of a Laman Graph ⋮ A linear programming algorithm to test for jamming in hard-sphere packings ⋮ Symmetric versions of Laman's theorem ⋮ Token graphs ⋮ Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid ⋮ A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid ⋮ Classifying the globally rigid edge‐transitive graphs and distance‐regular graphs in the plane ⋮ Coupler curves of moving graphs and counting realizations of rigid graphs ⋮ The rigidity of periodic body–bar frameworks on the three-dimensional fixed torus ⋮ Exploring the rigidity of planar configurations of points and rods ⋮ Sharp threshold for rigidity of random graphs ⋮ Augmenting the rigidity of a graph in \(\mathbb R^{2}\) ⋮ Multi-color pebble motion on graphs ⋮ When is a symmetric body-bar structure isostatic? ⋮ Unnamed Item ⋮ Recent results on assigned and unassigned distance geometry with applications to protein molecules and nanostructures ⋮ Combinatorial models of rigidity and renormalization ⋮ Geometric analysis characterizes molecular rigidity in generic and non-generic protein configurations ⋮ Enumerating constrained non-crossing minimally rigid frameworks ⋮ Assigned and unassigned distance geometry: applications to biological molecules and nanostructures ⋮ Combinatorial rigidity of incidence systems and application to dictionary learning ⋮ Rigidity for sticky discs ⋮ Pebble game algorithms and sparse graphs ⋮ When is a symmetric pin-jointed framework isostatic? ⋮ Combinatorial characterization of the Assur graphs from engineering ⋮ Unnamed Item ⋮ The number of circles of a maximum state of a plane graph with applications ⋮ The frictional pebble game: an algorithm for rigidity percolation in saturated frictional assemblies ⋮ Rigid Graph Compression: Motif-Based Rigidity Analysis for Disordered Fiber Networks ⋮ A remark on global positioning from local distances ⋮ Combining globally rigid frameworks ⋮ Assur decompositions of direction-length frameworks ⋮ Sparse hypergraphs and pebble game algorithms ⋮ Sparsity-certifying graph decompositions ⋮ Topological inductive constructions for tight surface graphs ⋮ Deterministic and stochastic control of kirigami topology ⋮ Inductive constructions for frameworks on a two-dimensional fixed torus ⋮ Sparse graphs and an augmentation problem

Cites Work