Pebble game algorithms and sparse graphs

DOI10.1016/J.DISC.2007.07.104zbMATH Open1136.05062arXivmath/0702129OpenAlexW2045768640MaRDI QIDQ2476285FDOQ2476285

Authors: Audrey Lee, Ileana Streinu 

Publication date: 18 March 2008

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An algorithm for two-dimensional rigidity percolation: The pebble game
• 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
• Title not available (Why is that?)
• Conditions for Unique Graph Realizations
• Title not available (Why is that?)
• The Molecule Problem: Exploiting Structure in Global Optimization
• Algorithms for graph rigidity and scene analysis
• Edge-disjoint spanning trees and depth-first search
• The Union of Matroids and the Rigidity of Frameworks
• On Generic Rigidity in the Plane
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Constructive characterizations for packing and covering with trees
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Certifying and constructing minimally rigid graphs in the plane
• Title not available (Why is that?)
• On matroidal families
• A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection

Cited In (67)

• Enumerating combinatorial resultant trees
• Treasure hunt in graph using pebbles
• Maximum likelihood thresholds via graph rigidity
• Recognizing planar Laman graphs
• Spy game: FPT-algorithm, hardness and graph products
• Rigidity of symmetric linearly constrained frameworks in the plane
• Frameworks with Coordinated Edge Motions
• When is a planar rod configuration infinitesimally rigid?
• Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs
• Graph rigidity for unitarily invariant matrix norms
• Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid
• Sparse graphs are near-bipartite
• Gain-sparsity and symmetry-forced rigidity in the plane
• Symmetry-forced rigidity of frameworks on surfaces
• Eigenvalue asymptotics for Schrödinger operators on sparse graphs
• Rigid cylindrical frameworks with two coincident points
• A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid
• Linking rigid bodies symmetrically
• Mixed volume techniques for embeddings of Laman graphs
• Computing Circuit Polynomials in the Algebraic Rigidity Matroid
• A proof of the molecular conjecture
• A characterisation of the generic rigidity of 2-dimensional point-line frameworks
• Bounded direction-length frameworks
• 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
• Title not available (Why is that?)
• Sparse graphs and an augmentation problem
• Sparse graphs and an augmentation problem
• Global rigidity of generic frameworks on the cylinder
• The Steiner Problem for Count Matroids
• The frictional pebble game: an algorithm for rigidity percolation in saturated frictional assemblies
• An inductive construction of minimally rigid body-hinge simple graphs
• Infinitesimal rigidity for non-Euclidean bar-joint frameworks
• 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
• 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
• Inductive constructions for frameworks on a two-dimensional fixed torus
• Sparsity-certifying graph decompositions
• Sparse hypergraphs and pebble game algorithms
• 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
• Sharp threshold for rigidity of random graphs
• Fast enumeration algorithms for non-crossing geometric graphs
• Contact Graphs of Circular Arcs
• PEBBLE GAMES AND LINEAR EQUATIONS
• The rigidity of periodic body-bar frameworks on the three-dimensional fixed torus
• Multitriangulations as complexes of star polygons
• Assur decompositions of direction-length frameworks
• Pebble game algorithms and \((k,l)\)-sparse graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• Directed graphs, decompositions, and spatial linkages
• Combinatorial models of rigidity and renormalization
• Globally rigid augmentation of rigid graphs
• Rigidity, global rigidity, and graph decomposition
• Synchronized traveling salesman problem
• Inapproximability of the standard pebble game and hard to pebble 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)