Pebble game algorithms and sparse graphs

DOI10.1016/j.disc.2007.07.104zbMath1136.05062arXivmath/0702129MaRDI QIDQ2476285

Publication date: 18 March 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0702129

zbMATH Keywords

rigidity; matroid; circuit; sparse graph; pebble game; Henneberg sequence

Mathematics Subject Classification ID

91A43: Games involving graphs

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05B35: Combinatorial aspects of matroids and geometric lattices

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

One Brick at a Time: A Survey of Inductive Constructions in Rigidity Theory, Infinitesimal rigidity for non-Euclidean bar-joint frameworks, Fast enumeration algorithms for non-crossing geometric graphs, Eigenvalue asymptotics for Schrödinger operators on sparse graphs, Proportional Contact Representations of Planar Graphs, Gain-sparsity and symmetry-forced rigidity in the plane, A characterisation of the generic rigidity of 2-dimensional point-line frameworks, Symmetry-forced rigidity of frameworks on surfaces, An inductive construction of minimally rigid body-hinge simple 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, Linking rigid bodies symmetrically, Body-and-cad geometric constraint systems, Necessary conditions for the generic global rigidity of frameworks on surfaces, A proof of the molecular conjecture, Bounded direction-length frameworks, Slider-pinning rigidity: a Maxwell-Laman-type theorem, Combinatorial models of rigidity and renormalization, A rooted-forest partition with uniform vertex demand, Frameworks with forced symmetry. I: Reflections and rotations, On the edge crossing properties of Euclidean minimum weight Laman graphs, Rigidity, global rigidity, and graph decomposition, Multitriangulations as complexes of star polygons, Mixed volume techniques for embeddings of Laman graphs, Sparse hypergraphs and pebble game algorithms, Sparsity-certifying graph decompositions, Inductive constructions for frameworks on a two-dimensional fixed torus, Directed graphs, decompositions, and spatial linkages, Frameworks with forced symmetry. II: Orientation-preserving crystallographic groups, An Inductive Construction of Minimally Rigid Body-Hinge Simple Graphs, The rigidity of periodic body–bar frameworks on the three-dimensional fixed torus, Contact Graphs of Circular Arcs

Cites Work