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)

Abstract

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
Volume8881
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this