On rigidity properties of unit-distance graphs
Abstract
A unit-distance graph is a graph which admits a realisation in Euclidean space in which every edge has unit length. Imposing further geometric conditions on the non-edges gives a family of natural subclasses. Requiring that no two vertices lie at distance less than one gives penny and marble graphs: the contact graphs of collections of equal radii d-dimensional spheres with non-overlapping interiors for d=2,3. Requiring instead that the straight-line drawing in the plane be non-crossing gives matchstick graphs. Since any motion of a realisation must preserve these extra conditions, the rigidity and flexibility properties of the resulting frameworks differ from those of classical bar-joint rigidity theory. In this note we analyse various rigidity problems for penny and marble graphs, matchstick graphs and unit-distance graphs. In particular we answer a recent open problem on penny and marble graph rigidity and establish a link between penny graphs and the concept of NAC-colourings.
Related
- Small 5-chromatic unit-distance graphs in disks of radius 3/2, 5/4 and 23/20
- The crossing number and the unit-distance crossing number of the Hamming graphs H(d,3)=K_3^{box d}, and their realizations over many coordinate fields
- An explicit lower bound for the unit distance problem
- Optimizing Explicit Unit-Distance Lower-Bound Certificates
- Perspectives on the unit distance problem
BibTeX
@misc{dewar2026rigidity,
title = {{On rigidity properties of unit-distance graphs}},
author = {Sean Dewar and Georg Grasegger and Alison La Porta and Jan Legerský and Anthony Nixon},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06246},
eprint = {2610.06246},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06246},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On rigidity properties of unit-distance graphs
AU - Sean Dewar
AU - Georg Grasegger
AU - Alison La Porta
AU - Jan Legerský
AU - Anthony Nixon
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06246
UR - https://arxiv.org/abs/2610.06246
AB - A unit-distance graph is a graph which admits a realisation in Euclidean space in which every edge has unit length. Imposing further geometric conditions on the non-edges gives a family of natural subclasses. Requiring that no two vertices lie at distance less than one gives penny and marble graphs: the contact graphs of collections of equal radii d-dimensional spheres with non-overlapping interiors for d=2,3. Requiring instead that the straight-line drawing in the plane be non-crossing gives matchstick graphs. Since any motion of a realisation must preserve these extra conditions, the rigidity and flexibility properties of the resulting frameworks differ from those of classical bar-joint rigidity theory. In this note we analyse various rigidity problems for penny and marble graphs, matchstick graphs and unit-distance graphs. In particular we answer a recent open problem on penny and marble graph rigidity and establish a link between penny graphs and the concept of NAC-colourings.
ER -