Input: | The (abstract) graph G of a simple polytope _{P}P |
---|---|

Output: | The family of the subsets of nodes of G
corresponding to the vertex sets of the facets of _{P}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 P have a good characterization in terms
of G (in the sense of Edmonds [18]). The problem
is polynomial time equivalent to computing the cycles
in _{P}G that correspond to the _{P}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 |
---|