In this section we collect problems that are concerned with computing
certain combinatorial information from compact descriptions of the
combinatorial structure of a polytope. Such compact encodings might be
the vertex-facet incidences, or, for simple polytopes, the abstract
graphs. An example of such a problem is to compute the dimension of a
polytope from its vertex-facet incidences. Initialize a set *S* by the
vertex set of an arbitrary facet. For each facet *F* compute the
intersection of *S* with the vertex set of *F*. Replace *S* by a
maximal one among the proper intersections and continue. The dimension
is the number of "rounds" performed until *S* becomes empty.

All data is meant to be purely combinatorial. For all problems in this section it is unknown if the "integrity" of the input data can be checked, proved, or disproved in polynomial time. For instance, it is rather unlikely that one can efficiently prove or disprove that a lattice is the face lattice of some polytope (see Problems 30, 31).

Sometimes, it might be worthwhile to exchange the roles of vertices and facets by duality of polytopes. Our choices of view points have mainly been guided by personal taste.

Some orientations of the abstract graph *G _{P}* of a simple
polytope