Go backward to 16 Reconstruction of Simple Polytopes
Go up to 3 Combinatorial Structure
Go forward to 18 AOF-Orientation
|
Go backward to 16 Reconstruction of Simple Polytopes Go up to 3 Combinatorial Structure Go forward to 18 AOF-Orientation |
XHTML 1.0 |
| 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 |
|---|
|
|
Why are some symbols not displayed correctly? |