On embeddability and stresses of graphs

DOI10.1007/S00493-007-2168-XzbMATH Open1157.05331arXivmath/0411009OpenAlexW2016748008MaRDI QIDQ950325FDOQ950325

Authors: Eran Nevo 

Publication date: 22 October 2008

Published in: Combinatorica (Search for Journal in Brave)

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.

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

Recommendations

• On a conjecture of embeddable graphs
• scientific article
• 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

zbMATH Keywords

stress-free graphs

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Homomorphiesätze für Graphen
• Title not available (Why is that?)
• The Rigidity of Graphs
• The rigidity of graphs. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)
• \(3n-5\) edges do force a subdivision of \(K_5\)
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
• Linkless embeddings of graphs in 3-space
• On embeddability and stresses of graphs
• The extremal function for \(K_{8}^{-}\) minors
• Title not available (Why is that?)

Cited In (15)

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

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)