Optimally bracing grid frameworks with holes

Yoshihiko Ito, Yuki Kobayashi, Yuya Higashikawa, Naoki Katoh, Sheung Hung Poon, Maria Saumell

Research output: Journal PublicationArticlepeer-review

3 Citations (Scopus)


We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces matches the lower bound given by Gáspár, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1].

Original languageEnglish
Pages (from-to)337-350
Number of pages14
JournalTheoretical Computer Science
Publication statusPublished - 1 Nov 2015
Externally publishedYes


  • Bar-joint framework
  • Bracing
  • Combinatorial rigidity
  • Square grid framework

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)


Dive into the research topics of 'Optimally bracing grid frameworks with holes'. Together they form a unique fingerprint.

Cite this