Pebble game algorithms and sparse graphs

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

Ileana Streinu, Audrey Lee

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

Fast enumeration algorithms for non-crossing geometric graphs, Proportional Contact Representations of Planar Graphs, Body-and-cad geometric constraint systems, 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, 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, An Inductive Construction of Minimally Rigid Body-Hinge Simple Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Edge-disjoint spanning trees and depth-first search
• On matroidal families
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Constructive characterizations for packing and covering with trees
• On graphs and rigidity of plane skeletal structures
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• The Union of Matroids and the Rigidity of Frameworks
• On Generic Rigidity in the Plane
• Conditions for Unique Graph Realizations
• The Molecule Problem: Exploiting Structure in Global Optimization
• Certifying and constructing minimally rigid graphs in the plane
• Algorithms - ESA 2003