backup forward

Go backward to 16 Reconstruction of Simple Polytopes
Go up to 3 Combinatorial Structure
Go forward to 18 AOF-Orientation

17 Facet System Verification for Simple Polytopes

Input: The (abstract) graph GP of a simple polytope P and a family F of subsets of nodes of GP
Output: "Yes" if F is the family of subsets of nodes of GP that correspond to the vertex sets of the facets of P, "No" otherwise
Status (general): Open
Status (fixed dim.): Open
In [32] it is shown that both the "Yes"- as well as the "No"-answer can be proved in polynomial time in the size of GP (provided that the integrity of the input data is guaranteed). Any polynomial time algorithm for the construction of an AOF- or US-orientation (see Problems 18 and 19) of GP would yield a polynomial time algorithm for this problem (see [32]).

Up to dimension three the problem can be solved in polynomial time (see the comments to Problems 16 and 18).

backup forward Why are some symbols not displayed correctly?