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

circuitHenneberg sequencematroidpebble gamerigiditysparse graph

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) 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

• A network theory approach to the rigidity of skeletal structures. I: Modelling and interconnection
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• 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 and depth-first search
• Edge-Disjoint Spanning Trees of Finite Graphs
• 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?)
• 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

(77)

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

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)