| 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). |
| Related problems: | 16, 18, 19, 31 |
|---|