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
- scientific article; zbMATH DE number 951476
- 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
- \(3n-5\) edges do force a subdivision of \(K_5\)
- A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs
- Homomorphiesätze für Graphen
- 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?)
- 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 extremal function for \(K_{8}^{-}\) minors
- The Rigidity of Graphs
- The rigidity of graphs. II
Cited in
(15)- Rubber bands, convex embeddings and graph connectivity
- Maximum likelihood threshold and generic completion rank of graphs
- The extremal function and Colin de Verdière graph parameter
- The Colin de Verdière parameter, excluded minors, and the spectral radius
- On the embeddability of skeleta of spheres
- Bipartite rigidity
- Bipartite rigidity
- The Lefschetz property for barycentric subdivisions of shellable complexes
- A universality theorem for stressable graphs in the plane
- Stress of a graph and its computation
- Maximum likelihood thresholds via graph rigidity
- Local degree conditions for \({K}_9\)-minors in graphs
- Detecting minors in matroids through triangles
- On embeddability and stresses of graphs
- 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)
