AProPo -- 16 Reconstruction of Simple Polytopes

Go backward to 15 f-Vector of Combinatorial Polytopes
Go up to 3 Combinatorial Structure
Go forward to 17 Facet System Verification for Simple Polytopes

16 Reconstruction of Simple Polytopes

Input:	The (abstract) graph G_P of a simple polytope P
Output:	The family of the subsets of nodes of G_P corresponding to the vertex sets of the facets of P

Status (general):	Open
Status (fixed dim.):	Open

Blind and Mani [6] proved that the entire combinatorial structure of a simple polytope is determined by its graph. This is false for general polytopes (of dimension at least four), which is the main reason why we restrict our attention to simple polytopes for the remaining problems in this section. Kalai [35] gave a short, elegant, and constructive proof of Blind and Mani's result. However, the algorithm that can be derived from it has a worst-case running time that is exponential in the number of vertices of the polytope.

In [32] it is shown that the problem can be formulated as a combinatorial optimization problem for which the problem to find an AOF-orientation of G_P (see Problem 18) is strongly dual in the sense of combinatorial optimization. In particular, the vertex sets of the facets of P have a good characterization in terms of G_P (in the sense of Edmonds [18]). The problem is polynomial time equivalent to computing the cycles in G_P that correspond to the 2-faces of P.

The problem can be solved in polynomial time in dimension at most three by computing a planar embedding of the graph, which can be done in linear time (Hopcroft and Tarjan [30], Mehlhorn and Mutzel [45]).