Skip to content

Research at St Andrews

Generically globally rigid graphs have generic universally rigid frameworks

Research output: Contribution to journalArticle

Open Access permissions

Open

Open Access Status

  • Embargoed (until 1/01/50)

Links

Author(s)

Robert Connelly, Steven Gortler, Louis Simon Theran

School/Research organisations

Abstract

We show that any graph that is generically globally rigid in ℝd has a realization in ℝd that is both generic and universally rigid. It also must have a realization in ℝd that is both infinitesimally rigid and universally rigid. Such a realization serves as a certificate of generic global rigidity. Previous certificates for generic global rigidity, even though they did involve calculations for particular configurations, did not necessarily guarantee that those configurations were globally rigid.

Our approach involves an algorithm by Lovász, Saks and Schrijver that constructs a general position orthogonal representation of the vertices, when the graph is vertex (d+1)-connected, and a result of Alfakih that shows how this representation leads to a stress matrix and a universally rigid framework of the graph.
Close

Details

Original languageEnglish
JournalCombinatorica
Publication statusAccepted/In press - 14 Aug 2018

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Generic unlabeled global rigidity

    Gortler, S., Theran, L. & Thurston, D., 30 Jul 2019, In : Forum of Mathematics, Sigma. 7, 34 p., e21.

    Research output: Contribution to journalArticle

  2. Rigidity for sticky disks

    Connelly, R., Gortler, S. J. & Theran, L. S., 27 Feb 2019, In : Proceedings of the Royal Society A - Mathematical, Physical & Engineering Sciences. 475, 2222, 16 p., 20180773.

    Research output: Contribution to journalArticle

  3. Affine rigidity and conics at infinity

    Connelly, R., Gortler, S. J. & Theran, L., Jul 2018, In : International Mathematics Research Notices. 2018, 13, p. 4084-4102 19 p.

    Research output: Contribution to journalArticle

  4. Analytic analysis of auxetic metamaterials through analogy with rigid link systems

    Rayneau-Kirkhope, D., Zhang, C., Theran, L. S. & Dias, M., 21 Feb 2018, In : Proceedings of the Royal Society A - Mathematical, Physical & Engineering Sciences. 474, 2210, 12 p., 20170753.

    Research output: Contribution to journalArticle

  5. Algorithms for detecting dependencies and rigid subsystems for CAD

    Farre, J., Kleinschmidt, H., Sidman, J., John, A. S., Stark, S., Theran, L. & Yu, X., 1 Oct 2016, In : Computer Aided Geometric Design. 47, p. 130-149 20 p.

    Research output: Contribution to journalArticle

Related by journal

  1. Decomposing simple permutations with enumerative consequences

    Brignall, R., Huczynska, S. & Vatter, V., Jul 2008, In : Combinatorica. 28, 4, p. 385-400 16 p.

    Research output: Contribution to journalArticle

  2. Infinite highly arc transitive digraphs and universal covering digraphs

    Cameron, P. J., Praeger, C. E. & Wormald, N. C., 1 Dec 1993, In : Combinatorica. 13, 4, p. 377-396 20 p.

    Research output: Contribution to journalArticle

  3. Intersection theorems in permutation groups

    Cameron, P. J., Deza, M. & Frankl, P., 1 Sep 1988, In : Combinatorica. 8, 3, p. 249-260 12 p.

    Research output: Contribution to journalArticle

  4. There are only finitely many finite distance-transitive graphs of given valency greater than two

    Cameron, P. J., 1 Mar 1982, In : Combinatorica. 2, 1, p. 9-13 5 p.

    Research output: Contribution to journalArticle

ID: 255207120

Top