On embeddability and stresses of graphs

DOI10.1007/S00493-007-2168-XMaRDI QIDQ950325zbMATHOpenAlexFDO

Authors Eran Nevo

Publication date 22 October 2008

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0411009

zbMATH Keywords

stress-free graphs

Mathematics Subject Classification ID

Graph minors (05C83)

Abstract: Gluck (1975) has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that linklessly embeddable graphs are generically 4-stress free. Both of these results are corollaries of the following theorem: every K_{r+2}-minor free graph is generically r-stress free for 0<r<5. (This assertion is false for r>5.) We give an equivalent formulation of this theorem in the language of symmetric algebraic shifting and show that its analogue for exterior algebraic shifting also holds. Some further extensions are detailed.

Recommendations

• On a conjecture of embeddable graphs
• scientific article; zbMATH DE number 4164896
• On the net-embeddability of graphs
• A universality theorem for stressable graphs in the plane
• On strongly almost trivial embeddings of graphs
• Publication:4716822
• On embedding well-separable graphs
• Stress of a graph and its computation
• scientific article; zbMATH DE number 4012641
• On embeddings of circulant graphs

Cites work

• scientific article; zbMATH DE number 4194602 (Why is no real title available?)
• scientific article; zbMATH DE number 3493472 (Why is no real title available?)
• scientific article; zbMATH DE number 665692 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• Homomorphiesätze für Graphen
• Linkless embeddings of graphs in 3-space
• On embeddability and stresses of graphs
• Rigidity and the lower bound theorem. I
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• The Rigidity of Graphs
• The extremal function for \(K_{8}^{-}\) minors
• The rigidity of graphs. II
• \(3n-5\) edges do force a subdivision of \(K_5\)

Cited in

(15)

• Stress of a graph and its computation
• Bipartite rigidity
• Maximum likelihood thresholds via graph rigidity
• Bipartite rigidity
• The extremal function and Colin de Verdière graph parameter
• Detecting minors in matroids through triangles
• On the embeddability of skeleta of spheres
• Maximum likelihood threshold and generic completion rank of graphs
• Rubber bands, convex embeddings and graph connectivity
• Local degree conditions for \({K}_9\)-minors in graphs
• On embeddability and stresses of graphs
• The Lefschetz property for barycentric subdivisions of shellable complexes
• The Colin de Verdière parameter, excluded minors, and the spectral radius
• A universality theorem for stressable graphs in the plane
• Generic initial ideals and fibre products

This page was built for publication: On embeddability and stresses of graphs

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