Optimally bracing grid frameworks with holes

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

Research output: Journal PublicationArticlepeer-review

1 Citation (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)474-489
Number of pages16
JournalLecture Notes in Computer Science
Publication statusPublished - 2014
Externally publishedYes


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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this