Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Pebble Game Algorith ...
Conference paper

Pebble Game Algorithms and (k,l)-Sparse Graphs

Audrey Lee (1), Ileana Streinu (2)
(1) Department of Computer Science [Amherst]
(2) Computer Science Department
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3394
License
https://about.hal.science/hal-authorisation-v1
Folding and Unfolding of Polygonal Linkages, with Applications to Structural Biology
Indicators
744
Views
872
Downloads

Pebble Game Algorithms and (k,l)-Sparse Graphs

Audrey Lee (1), Ileana Streinu (2)
(1) Department of Computer Science [Amherst]
(2) Computer Science Department
Abstract
A multi-graph $G$ on n vertices is $(k,l)$-sparse if every subset of $n'≤n$ vertices spans at most $kn'-l$ edges, $0 ≤l < 2k$. $G$ is tight if, in addition, it has exactly $kn - l$ edges. We characterize $(k,l)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,l)$-pebble games. As applications, we use the pebble games for computing components (maximal tight subgraphs) in sparse graphs, to obtain inductive (Henneberg) constructions, and, when $l=k$, edge-disjoint tree decompositions.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • sparse graph
  • pebble game
  • rigidity
  • arboricity
  • graph orientation with bounded degree
Cited by

Source: OpenCitations

  • Enumerating Non-crossing Minimally Rigid Frameworks

    Lecture notes in computer science

    Authors : David Avis, Naoki Katoh, Makoto Ohsaki ORCID, Ileana Streinu ORCID, Shin-ichi Tanigawa ORCID

    Journal reference : Volume , 2006, pp. 205-215

    DOI : 10.1007/11809678_23

  • Augmenting the Rigidity of a Graph in R 2

    Algorithmica

    Authors : A. García, J. Tejel

    Journal reference : Volume 59, 2009, pp. 145-168

    DOI : 10.1007/s00453-009-9300-9

  • A virtual pebble game to ensemble average graph rigidity

    Algorithms for Molecular Biology

    Authors : Luis C González ORCID, Hui Wang ORCID, Dennis R Livesay, Donald J Jacobs ORCID

    Journal reference : Volume 10, 2015, pp. 11

    DOI : 10.1186/s13015-015-0039-3

  • Enumerating Constrained Non-crossing Minimally Rigid Frameworks

    Discrete & Computational Geometry

    Authors : David Avis, Naoki Katoh, Makoto Ohsaki ORCID, Ileana Streinu ORCID, Shin-ichi Tanigawa ORCID

    Journal reference : Volume 40, 2007, pp. 31-46

    DOI : 10.1007/s00454-007-9026-x

  • On Finding Socially Tenuous Groups for Online Social Networks

    Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    Authors : Chih-Ya Shen ORCID, Liang-Hao Huang ORCID, De-Nian Yang ORCID, Hong-Han Shuai ORCID, Wang-Chien Lee ORCID, Ming-Syan Chen ORCID

    Journal reference : Volume , 2017, pp. 415-424

    DOI : 10.1145/3097983.3097995

  • TRAMbio: a flexible python package for graph rigidity analysis of macromolecules

    BMC Bioinformatics

    Authors : Nicolas Handke ORCID, Thomas Gatter ORCID, Franziska Reinhardt ORCID, Peter F. Stadler ORCID

    Journal reference : Volume 26, 2025, pp. 266

    DOI : 10.1186/s12859-025-06300-3

  • Enumerating Non-crossing Minimally Rigid Frameworks

    Graphs and Combinatorics

    Authors : David Avis, Naoki Katoh, Makoto Ohsaki ORCID, Ileana Streinu ORCID, Shin-ichi Tanigawa ORCID

    Journal reference : Volume 23, 2007, pp. 117-134

    DOI : 10.1007/s00373-007-0709-0
Preview
Loading PDF preview...