Steinitz representations of polyhedra and the Colin de Verdière number

DOI10.1006/jctb.2000.2027zbMath1023.05100OpenAlexW2070259181MaRDI QIDQ1850544

László Lovász

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/d19e64e911e390a4c2a7271343da46aff7fd7fc8

zbMATH Keywords

embeddingeigenvaluesplanar graphstress matricesbraced convex polytopes

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Finite geometry and special incidence structures (51E99)

Related Items

Embedding stacked polytopes on a polynomial-size grid ⋮ The Colin de Verdière number and graphs of polytopes ⋮ Optimizing Colin de Verdière matrices of \(K_{4,4}\) ⋮ Realizing Planar Graphs as Convex Polytopes ⋮ Gershgorin Disks for Multiple Eigenvalues of Non-negative Matrices ⋮ Nullspace Embeddings for Outerplanar Graphs ⋮ Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph ⋮ A duality transform for constructing small grid embeddings of 3d polytopes ⋮ The strong Arnold property for 4-connected flat graphs ⋮ Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint ⋮ On a conjecture related to geometric routing ⋮ On Vertex Partitions and the Colin de Verdière Parameter

Cites Work

• Unnamed Item
• Unnamed Item
• Rigidity and energy
• The Colin de Verdière number and sphere representations of a graph
• On the null space of a Colin de Verdière matrix
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• Spaces of stresses, projections and parallel drawings for spherical polyhedra
• Sachs' linkless embedding conjecture
• A short proof of the planarity characterization of Colin de Verdière
• Realization spaces of polytopes
• A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs