Cargando…
Which graphs are rigid in [Formula: see text] ?
We present three results which support the conjecture that a graph is minimally rigid in d-dimensional [Formula: see text] -space, where [Formula: see text] and [Formula: see text] , if and only if it is (d, d)-tight. Firstly, we introduce a graph bracing operation which preserves independence in th...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer US
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9033754/ https://www.ncbi.nlm.nih.gov/pubmed/35528137 http://dx.doi.org/10.1007/s10898-021-01008-z |
_version_ | 1784692966810451968 |
---|---|
author | Dewar, Sean Kitson, Derek Nixon, Anthony |
author_facet | Dewar, Sean Kitson, Derek Nixon, Anthony |
author_sort | Dewar, Sean |
collection | PubMed |
description | We present three results which support the conjecture that a graph is minimally rigid in d-dimensional [Formula: see text] -space, where [Formula: see text] and [Formula: see text] , if and only if it is (d, d)-tight. Firstly, we introduce a graph bracing operation which preserves independence in the generic rigidity matroid when passing from [Formula: see text] to [Formula: see text] . We then prove that every (d, d)-sparse graph with minimum degree at most [Formula: see text] and maximum degree at most [Formula: see text] is independent in [Formula: see text] . Finally, we prove that every triangulation of the projective plane is minimally rigid in [Formula: see text] . A catalogue of rigidity preserving graph moves is also provided for the more general class of strictly convex and smooth normed spaces and we show that every triangulation of the sphere is independent for 3-dimensional spaces in this class. |
format | Online Article Text |
id | pubmed-9033754 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | Springer US |
record_format | MEDLINE/PubMed |
spelling | pubmed-90337542022-05-06 Which graphs are rigid in [Formula: see text] ? Dewar, Sean Kitson, Derek Nixon, Anthony J Glob Optim Article We present three results which support the conjecture that a graph is minimally rigid in d-dimensional [Formula: see text] -space, where [Formula: see text] and [Formula: see text] , if and only if it is (d, d)-tight. Firstly, we introduce a graph bracing operation which preserves independence in the generic rigidity matroid when passing from [Formula: see text] to [Formula: see text] . We then prove that every (d, d)-sparse graph with minimum degree at most [Formula: see text] and maximum degree at most [Formula: see text] is independent in [Formula: see text] . Finally, we prove that every triangulation of the projective plane is minimally rigid in [Formula: see text] . A catalogue of rigidity preserving graph moves is also provided for the more general class of strictly convex and smooth normed spaces and we show that every triangulation of the sphere is independent for 3-dimensional spaces in this class. Springer US 2021-03-13 2022 /pmc/articles/PMC9033754/ /pubmed/35528137 http://dx.doi.org/10.1007/s10898-021-01008-z Text en © The Author(s) 2021 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . |
spellingShingle | Article Dewar, Sean Kitson, Derek Nixon, Anthony Which graphs are rigid in [Formula: see text] ? |
title | Which graphs are rigid in [Formula: see text] ? |
title_full | Which graphs are rigid in [Formula: see text] ? |
title_fullStr | Which graphs are rigid in [Formula: see text] ? |
title_full_unstemmed | Which graphs are rigid in [Formula: see text] ? |
title_short | Which graphs are rigid in [Formula: see text] ? |
title_sort | which graphs are rigid in [formula: see text] ? |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9033754/ https://www.ncbi.nlm.nih.gov/pubmed/35528137 http://dx.doi.org/10.1007/s10898-021-01008-z |
work_keys_str_mv | AT dewarsean whichgraphsarerigidinformulaseetext AT kitsonderek whichgraphsarerigidinformulaseetext AT nixonanthony whichgraphsarerigidinformulaseetext |