backup forward

Go backward to 17 Facet System Verification for Simple Polytopes
Go up to 3 Combinatorial Structure
Go forward to 19 US-Orientation
XHTML 1.0

18 AOF-Orientation

Input: The (abstract) graph GP of a simple polytope P
Output: An AOF-orientation of GP
Status (general): Open
Status (fixed dim.): Open
(Simple) polytopes admit AOF-orientations because every linear function in general position induces an AOF-orientation.

In [32] it is shown that one can formulate the problem as a combinatorial optimization problem, for which a strongly dual problem in the sense of combinatorial optimization exists (see the comments to Problem 16). Thus, the AOF-orientations of GP have a good characterization (see Problem 17) in terms of GP, i.e., there are polynomial size proofs for both cases an orientation being an AOF-orientation or not (provided that the integrity of the input data is guaranteed). However, it is unknown if it is possible to check in polynomial time if a given orientation is an AOF-orientation.

In dimensions one and two the problem is trivial. For a three-dimensional polytope P the problem can be solved in polynomial time, e.g., by producing a plane drawing of GP with convex faces (see Tutte [64]) and sorting the nodes with respect to a linear function (in general position).

A polynomial time algorithm would lead to a polynomial algorithm for Problem 17 (see [32]).

By duality of polytopes, the problem is equivalent to the problem of finding a shelling order of the facets of a simplicial polytope from the upper two layers of its face lattice. It is unknown whether it is possible to find in polynomial time a shelling order of the facets, even if the polytope is given by its entire face lattice. With this larger input, however, it is possible to check in polynomial time whether a given ordering of the facets is a shelling order.


backup forward Why are some symbols not displayed correctly?