A minmax relationship between embeddable and rigid graphs

DOI10.1016/S0893-9659(97)00062-1MaRDI QIDQ1372309zbMATH OpenFDO

Authors T.-S. Tay, Jurg Nievergelt

Publication date 30 March 1998

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0893-9659(97)00062-1

zbMATH Keywords

elastic embeddingsgeneric graphsweighted graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

An embedding of the vertices of a graph into Euclidean space is infinitesimally rigid if every infinitesimal motion of the vertices which preserves the distance between each pair of adjacent vertices arises from an infinitesimal isometry of the space. An embedding of the vertices of a weighted graph is elastic if every sufficiently small perturbation of the distances between adjacent vertices can be realized by an embedding close to the given embedding. This paper points out a minimax relation between the generic rigidity and elasticity of graphs, that is, that a graph is edge-minimally generically rigid, i.e. isostatic, if and only if it is maximally elastic.

Recommendations

• On the number of embeddings of minimally rigid graphs
• The number of embeddings of minimally rigid graphs
• New upper bounds for the number of embeddings of minimally rigid graphs
• scientific article; zbMATH DE number 683300
• On the maximal number of real embeddings of spatial minimally rigid graphs
• Minimally globally rigid graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• scientific article; zbMATH DE number 3926946
• On minimally highly vertex-redundantly rigid graphs
• Minors, embeddability, and extremal problems for hypergraphs

Cites work

• scientific article; zbMATH DE number 3846996 (Why is no real title available?)
• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 17636 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 3294853 (Why is no real title available?)
• Metric graphs elastically embeddable in the plane
• The Rigidity of Graphs

Cited in

(3)

• The number of embeddings of minimally rigid graphs
• scientific article; zbMATH DE number 683300 (Why is no real title available?)
• Elastic graphs

This page was built for publication: A minmax relationship between embeddable and rigid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372309)