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 - http://www.scopus.com/inward/record.url?scp=85205342694&partnerID=8YFLogxK
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 -