Reconstructing a simple polytope from its graph
A theorem of \textit{R. Blind} and \textit{P. Mani-Levitska} [Aequationes Math. 34, 287-297 (1987; Zbl 0634.52005)] says that the combinatorial type of a simple polytope is already determined by its graph. \textit{G. Kalai} gave a constructive proof [J. Comb. Theory, Ser. A 49, No. 2, 381-383 (1988; Zbl 0673.05087)], which has a horrendous time-complexity though. In the paper under review the authors suggest a reconstruction algorithm which is based on Kalai's ideas combined with techniques from combinatorial optimization. Empirically, this yields a faster method, although the algorithm still requires exponential running time. The paper also reports on the results of experiments on various classes of simple polytopes in dimensions up to~\(8\). A key concept in the algorithm is the notion of a quasi-facet of a simple \(d\)-polytope, that is, a \((d-1)\)-regular, connected, and non-separating subgraph. Perles conjectured that the quasi-facets of a simple polytope are precisely the induced subgraphs of the facets. The reconstruction algorithm discussed in the paper under review would greatly benefit if this conjecture were true. And, in fact, it turned out to be true for all classes of polytopes studied in the aforementioned runtime experiments. However, recently \textit{C. Haase} and \textit{G. M. Ziegler} [arXiv: math.CO/0011170] found a counter-example to Perles' conjecture. For the entire collection see [Zbl 0944.00089].
- On the \(k\)-systems of a simple polytope
- A simple way to tell a simple polytope from its graph
- scientific article; zbMATH DE number 1953195
- scientific article; zbMATH DE number 1961535
- Finding a simple polytope from its graph in polynomial time
- Reconstructibility of matroid polytopes
- On the faces of simple polytopes
- scientific article; zbMATH DE number 1241854
- Examples and counterexamples for the Perles conjecture
- Graphs, skeleta and reconstruction of polytopes
- Finding a simple polytope from its graph in polynomial time
- Gewisse einfache Polytope sind durch ihren Graph eindeutig bestimmt. (Certain simple polytopes are uniquely determined by their graphs)
- On the \(k\)-systems of a simple polytope
- Examples and counterexamples for the Perles conjecture
- Reconstruction of Weakly Simple Polygons from Their Edges
- scientific article; zbMATH DE number 1953195 (Why is no real title available?)
- Reconstructing a non-simple polytope from its graph
- A characterization of triangulations of closed surfaces
- Finding a Polytope from Its Graph in Polynomial Time
- A counterexample to the Perles conjecture
- Graphs, skeleta and reconstruction of polytopes
This page was built for publication: Reconstructing a simple polytope from its graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4518986)
