backup forward

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
XHTML 1.0

16 Reconstruction of Simple Polytopes

Input: The (abstract) graph GP of a simple polytope P
Output: The family of the subsets of nodes of GP 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 GP (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 GP (in the sense of Edmonds [18]). The problem is polynomial time equivalent to computing the cycles in GP 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]).


backup forward Why are some symbols not displayed correctly?