AProPo -- 19 US-Orientation

Go backward to 18 AOF-Orientation
Go up to 3 Combinatorial Structure

19 US-Orientation

Input:	The (abstract) graph G_P of a simple polytope P
Output:	A US-orientation of G_P

Status (general):	Open
Status (fixed dim.):	Open

Since AOF-orientations are US-orientations, it follows from the remarks on Problem 18 that (simple) polytopes admit US-orientations and that the problem can be solved in polynomial time up to dimension three. By slight adaptions of the arguments given in [32], one can prove that a polynomial time algorithm for this problem would yield a polynomial time algorithm for Problem 17 as well.

In contrast to Problem 18, no good characterization of US-orientations is known.

It is not hard to see that, by duality of polytopes, the problem is equivalent to the problem of finding from the upper two layers a partition of the face lattice of a simplicial polytope into intervals whose upper bounds are the facets (i.e., a partition in the sense of Stanley [60]). Similar to the situation with shelling orders, it is even unknown whether such a partition can be found in polynomial time if the polytope is specified by its entire face lattice. Again, with the entire face lattice as input it can be checked in polynomial time whether a family of subsets of the face lattice is a partition in that sense.