Pebble game algorithms and sparse graphs

DOI10.1016/J.DISC.2007.07.104MaRDI QIDQ2476285zbMATH OpenOpenAlexFDO

Authors Audrey Lee, Ileana Streinu

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

rigiditycircuitmatroidsparse graphpebble gameHenneberg sequence

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Games involving graphs (91A43)

Abstract: A multi-graph $G$ on $n$ vertices is $(k,ell)$-sparse if every subset of $n^{\prime }leqn$ vertices spans at most $k{n}^{\prime }-ell$ edges. $G$ is {em tight} if, in addition, it has exactly $kn-ell$ edges. For integer values $k$ and $ellin[0,2k)$, we characterize the $(k,ell)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,ell)$-pebble games.

Recommendations

• Pebble game algorithms and \((k,l)\)-sparse graphs
• Sparse hypergraphs and pebble game algorithms
• Sparsity-certifying graph decompositions
• A note on \([k,l]\)-sparse graphs
• Sparsity. Graphs, structures, and algorithms

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 2188414 (Why is no real title available?)
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection
• Algorithms for graph rigidity and scene analysis
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Certifying and constructing minimally rigid graphs in the plane
• Conditions for Unique Graph Realizations
• Constructive characterizations for packing and covering with trees
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-disjoint spanning trees and depth-first search
• On Generic Rigidity in the Plane
• On graphs and rigidity of plane skeletal structures
• On matroidal families
• On the Problem of Decomposing a Graph into n Connected Factors
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• The Molecule Problem: Exploiting Structure in Global Optimization
• The Union of Matroids and the Rigidity of Frameworks

Cited in

(67)

• Inapproximability of the standard pebble game and hard to pebble graphs
• Synchronized traveling salesman problem
• Graph rigidity for unitarily invariant matrix norms
• Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid
• Gain-sparsity and symmetry-forced rigidity in the plane
• Symmetry-forced rigidity of frameworks on surfaces
• Sparse graphs are near-bipartite
• A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid
• Linking rigid bodies symmetrically
• Rigid cylindrical frameworks with two coincident points
• Eigenvalue asymptotics for Schrödinger operators on sparse graphs
• Mixed volume techniques for embeddings of Laman graphs
• A proof of the molecular conjecture
• A characterisation of the generic rigidity of 2-dimensional point-line frameworks
• Bounded direction-length frameworks
• Computing Circuit Polynomials in the Algebraic Rigidity Matroid
• Enumerating combinatorial resultant trees
• A New Pebble Game that Characterizes Parallel Complexity Classes
• Frameworks with forced symmetry. I: Reflections and rotations
• Combinatorial rigidity of incidence systems and application to dictionary learning
• A rooted-forest partition with uniform vertex demand
• Treasure hunt in graph using pebbles
• Maximum likelihood thresholds via graph rigidity
• Sparse graphs and an augmentation problem
• scientific article; zbMATH DE number 4189511 (Why is no real title available?)
• Global rigidity of generic frameworks on the cylinder
• Sparse graphs and an augmentation problem
• The frictional pebble game: an algorithm for rigidity percolation in saturated frictional assemblies
• An inductive construction of minimally rigid body-hinge simple graphs
• Optimal decomposition and recombination of isostatic geometric constraint systems for designing layered materials
• Algorithms for detecting dependencies and rigid subsystems for CAD
• Necessary conditions for the generic global rigidity of frameworks on surfaces
• An inductive construction of minimally rigid body-hinge simple graphs
• Recognizing planar Laman graphs
• The Steiner Problem for Count Matroids
• Infinitesimal rigidity for non-Euclidean bar-joint frameworks
• Topological inductive constructions for tight surface graphs
• A note on \([k,l]\)-sparse graphs
• Body-and-cad geometric constraint systems
• Slider-pinning rigidity: a Maxwell-Laman-type theorem
• Rigidity of symmetric frameworks in normed spaces
• Sparsity-certifying graph decompositions
• Sparse hypergraphs and pebble game algorithms
• Inductive constructions for frameworks on a two-dimensional fixed torus
• Frameworks with forced symmetry. II: Orientation-preserving crystallographic groups
• Proportional contact representations of planar graphs
• On the edge crossing properties of Euclidean minimum weight Laman graphs
• One brick at a time: a survey of inductive constructions in rigidity theory
• Global rigidity of direction-length frameworks
• Spy game: FPT-algorithm, hardness and graph products
• Sharp threshold for rigidity of random graphs
• Fast enumeration algorithms for non-crossing geometric graphs
• Contact Graphs of Circular Arcs
• Frameworks with Coordinated Edge Motions
• Rigidity of symmetric linearly constrained frameworks in the plane
• PEBBLE GAMES AND LINEAR EQUATIONS
• The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus
• When is a planar rod configuration infinitesimally rigid?
• Multitriangulations as complexes of star polygons
• Assur decompositions of direction-length frameworks
• Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs
• Pebble game algorithms and \((k,l)\)-sparse graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• Combinatorial models of rigidity and renormalization
• Directed graphs, decompositions, and spatial linkages
• Rigidity, global rigidity, and graph decomposition
• Globally rigid augmentation of rigid graphs

This page was built for publication: Pebble game algorithms and sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476285)