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
|
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 |
| 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]). |
| Related problems: | 17, 18, 19 |
|---|
|
|
Why are some symbols not displayed correctly? |