Cargando…

Lower Bounds on the Number of Realizations of Rigid Graphs

Computing the number of realizations of a minimally rigid graph is a notoriously difficult problem. Toward this goal, for graphs that are minimally rigid in the plane, we take advantage of a recently published algorithm, which is the fastest available method, although its complexity is still exponen...

Descripción completa

Detalles Bibliográficos
Autores principales: Grasegger, Georg, Koutschan, Christoph, Tsigaridas, Elias
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Taylor & Francis 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7324120/
https://www.ncbi.nlm.nih.gov/pubmed/32655833
http://dx.doi.org/10.1080/10586458.2018.1437851
_version_ 1783551884638814208
author Grasegger, Georg
Koutschan, Christoph
Tsigaridas, Elias
author_facet Grasegger, Georg
Koutschan, Christoph
Tsigaridas, Elias
author_sort Grasegger, Georg
collection PubMed
description Computing the number of realizations of a minimally rigid graph is a notoriously difficult problem. Toward this goal, for graphs that are minimally rigid in the plane, we take advantage of a recently published algorithm, which is the fastest available method, although its complexity is still exponential. Combining computational results with the theory of constructing new rigid graphs by gluing, we give a new lower bound on the maximal possible number of (complex) realizations for graphs with a given number of vertices. We extend these ideas to rigid graphs in three dimensions and we derive similar lower bounds, by exploiting data from extensive Gröbner basis computations.
format Online
Article
Text
id pubmed-7324120
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Taylor & Francis
record_format MEDLINE/PubMed
spelling pubmed-73241202020-07-10 Lower Bounds on the Number of Realizations of Rigid Graphs Grasegger, Georg Koutschan, Christoph Tsigaridas, Elias Exp Math Original Articles Computing the number of realizations of a minimally rigid graph is a notoriously difficult problem. Toward this goal, for graphs that are minimally rigid in the plane, we take advantage of a recently published algorithm, which is the fastest available method, although its complexity is still exponential. Combining computational results with the theory of constructing new rigid graphs by gluing, we give a new lower bound on the maximal possible number of (complex) realizations for graphs with a given number of vertices. We extend these ideas to rigid graphs in three dimensions and we derive similar lower bounds, by exploiting data from extensive Gröbner basis computations. Taylor & Francis 2018-03-27 /pmc/articles/PMC7324120/ /pubmed/32655833 http://dx.doi.org/10.1080/10586458.2018.1437851 Text en © 2018 Taylor & Francis https://creativecommons.org/licenses/by/4.0/This is an Open Access article distributed under the terms of the Creative Commons Attribution-Non-Commercial License http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. The moral rights of the named author(s) have been asserted.
spellingShingle Original Articles
Grasegger, Georg
Koutschan, Christoph
Tsigaridas, Elias
Lower Bounds on the Number of Realizations of Rigid Graphs
title Lower Bounds on the Number of Realizations of Rigid Graphs
title_full Lower Bounds on the Number of Realizations of Rigid Graphs
title_fullStr Lower Bounds on the Number of Realizations of Rigid Graphs
title_full_unstemmed Lower Bounds on the Number of Realizations of Rigid Graphs
title_short Lower Bounds on the Number of Realizations of Rigid Graphs
title_sort lower bounds on the number of realizations of rigid graphs
topic Original Articles
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7324120/
https://www.ncbi.nlm.nih.gov/pubmed/32655833
http://dx.doi.org/10.1080/10586458.2018.1437851
work_keys_str_mv AT graseggergeorg lowerboundsonthenumberofrealizationsofrigidgraphs
AT koutschanchristoph lowerboundsonthenumberofrealizationsofrigidgraphs
AT tsigaridaselias lowerboundsonthenumberofrealizationsofrigidgraphs