Optimally bracing grid frameworks with holes

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

doi:10.1016/j.tcs.2015.07.062

Optimally bracing grid frameworks with holes

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

Research output: Journal Publication › Article › peer-review

3 Citations (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 language	English
Pages (from-to)	337-350
Number of pages	14
Journal	Theoretical Computer Science
Volume	607
DOIs	https://doi.org/10.1016/j.tcs.2015.07.062
Publication status	Published - 1 Nov 2015
Externally published	Yes

Keywords

Bar-joint framework
Bracing
Combinatorial rigidity
Square grid framework

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2015.07.062

Cite this

@article{5a9fd226a8aa42b88d0fb892f4981c3e,

title = "Optimally bracing grid frameworks with holes",

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{\'a}sp{\'a}r, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1].",

keywords = "Bar-joint framework, Bracing, Combinatorial rigidity, Square grid framework",

author = "Yoshihiko Ito and Yuki Kobayashi and Yuya Higashikawa and Naoki Katoh and Poon, {Sheung Hung} and Maria Saumell",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = nov,

day = "1",

doi = "10.1016/j.tcs.2015.07.062",

language = "English",

volume = "607",

pages = "337--350",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Optimally bracing grid frameworks with holes

AU - Ito, Yoshihiko

AU - Kobayashi, Yuki

AU - Higashikawa, Yuya

AU - Katoh, Naoki

AU - Poon, Sheung Hung

AU - Saumell, Maria

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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].

AB - 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].

KW - Bar-joint framework

KW - Bracing

KW - Combinatorial rigidity

KW - Square grid framework

UR - http://www.scopus.com/inward/record.url?scp=84951067136&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2015.07.062

DO - 10.1016/j.tcs.2015.07.062

M3 - Article

AN - SCOPUS:84951067136

SN - 0304-3975

VL - 607

SP - 337

EP - 350

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Optimally bracing grid frameworks with holes

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this