BLOCK-AND-HOLE GRAPHS: CONSTRUCTIBILITY AND (3, 0)-SPARSITY

Bryan Gin–Ge Chen; James Cruickshank; Derek Kitson

doi:10.1353/mpr.2024.a937578

BLOCK-AND-HOLE GRAPHS: CONSTRUCTIBILITY AND (3, 0)-SPARSITY

Bryan Gin–Ge Chen
, James Cruickshank
, Derek Kitson

Mathematics

Research output: Contribution to a Journal (Peer & Non Peer) › Article › peer-review

Abstract

We show that minimally 3-rigid block-and-hole graphs with one block are characterised as those that are constructible from K₃ by vertex splitting, and also as those having associated looped face graphs that are (3, 0)-tight. This latter property can be verified in polynomial time by a form of pebble game algorithm. We also indicate an application to graph rigidity in 3-dimensional normed spaces that are smooth and strictly convex.

Original language	English
Pages (from-to)	53-69
Number of pages	17
Journal	Mathematical Proceedings of the Royal Irish Academy
Volume	124A
Issue number	2
DOIs	https://doi.org/10.1353/mpr.2024.a937578
Publication status	Published - 2024

Access to Document

10.1353/mpr.2024.a937578

Cite this

@article{818558d3a13b4ba7bbde68eeeef9f519,

title = "BLOCK-AND-HOLE GRAPHS: CONSTRUCTIBILITY AND (3, 0)-SPARSITY",

abstract = "We show that minimally 3-rigid block-and-hole graphs with one block are characterised as those that are constructible from K3 by vertex splitting, and also as those having associated looped face graphs that are (3, 0)-tight. This latter property can be verified in polynomial time by a form of pebble game algorithm. We also indicate an application to graph rigidity in 3-dimensional normed spaces that are smooth and strictly convex.",

author = "Chen, \{Bryan Gin–Ge\} and James Cruickshank and Derek Kitson",

note = "Publisher Copyright: {\textcopyright} The Author(s).",

year = "2024",

doi = "10.1353/mpr.2024.a937578",

language = "English",

volume = "124A",

pages = "53--69",

journal = "Mathematical Proceedings of the Royal Irish Academy",

issn = "1393-7197",

publisher = "Royal Irish Academy",

number = "2",

}

TY - JOUR

T1 - BLOCK-AND-HOLE GRAPHS

T2 - CONSTRUCTIBILITY AND (3, 0)-SPARSITY

AU - Chen, Bryan Gin–Ge

AU - Cruickshank, James

AU - Kitson, Derek

N1 - Publisher Copyright: © The Author(s).

PY - 2024

Y1 - 2024

N2 - We show that minimally 3-rigid block-and-hole graphs with one block are characterised as those that are constructible from K3 by vertex splitting, and also as those having associated looped face graphs that are (3, 0)-tight. This latter property can be verified in polynomial time by a form of pebble game algorithm. We also indicate an application to graph rigidity in 3-dimensional normed spaces that are smooth and strictly convex.

AB - We show that minimally 3-rigid block-and-hole graphs with one block are characterised as those that are constructible from K3 by vertex splitting, and also as those having associated looped face graphs that are (3, 0)-tight. This latter property can be verified in polynomial time by a form of pebble game algorithm. We also indicate an application to graph rigidity in 3-dimensional normed spaces that are smooth and strictly convex.

UR - https://www.scopus.com/pages/publications/85205342694

U2 - 10.1353/mpr.2024.a937578

DO - 10.1353/mpr.2024.a937578

M3 - Article

AN - SCOPUS:85205342694

SN - 1393-7197

VL - 124A

SP - 53

EP - 69

JO - Mathematical Proceedings of the Royal Irish Academy

JF - Mathematical Proceedings of the Royal Irish Academy

IS - 2

ER -

BLOCK-AND-HOLE GRAPHS: CONSTRUCTIBILITY AND (3, 0)-SPARSITY

Abstract

Access to Document

Other files and links

Fingerprint

Cite this