|Input:||The (abstract) graph GP of a simple polytope P|
|Output:||An AOF-orientation of GP|
|Status (fixed dim.):||Open|
(Simple) polytopes admit AOF-orientations because every linear
function in general position induces an AOF-orientation.
In  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 ) and sorting the nodes with respect to a linear function (in general position).
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.
|Related problems:||17, 19, 35|