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

Descripción completa

Detalles Bibliográficos
Autores principales: Dewar, Sean, Kitson, Derek, Nixon, Anthony
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