A
simple d-dimensional polytope is a polytope in which every vertex has exactly
d incident edges. In a unique-sink orientation of a simple polytope, every subset of
k incoming edges at a vertex
v determines a
k-dimensional face for which
v is the unique sink. Therefore, the number of faces of all dimensions of the polytope (including the polytope itself, but not the empty set) can be computed by the sum of the number of subsets of incoming edges, :\sum_{v\in G(P)} 2^{d_{\operatorname{in}}(v)} where
G(
P) is the graph of the polytope, and
din(
v) is the
in-degree (number of incoming edges) of a vertex
v in the given orientation . More generally, for any orientation of a simple polytope, the same sum counts the number of incident pairs of a face of the polytope and a sink of the face. And in an
acyclic orientation, every face must have at least one sink. Therefore, an acyclic orientation is a unique sink orientation if and only if there is no other acyclic orientation with a smaller sum. Additionally, a
k-regular subgraph of the given graph forms a face of the polytope if and only if its vertices form a
lower set for at least one acyclic unique sink orientation. In this way, the
face lattice of the polytope is uniquely determined from the graph . Based on this structure, the face lattices of simple polytopes can be reconstructed from their graphs in
polynomial time using
linear programming . ==References==