up forward

Go up to 3 Combinatorial Structure
Go forward to 15 f-Vector of Combinatorial Polytopes
XHTML 1.0

14 Face Lattice of Combinatorial Polytopes

Input: Vertex-facet incidence matrix of a polytope P
Output: Hasse-diagram of the face lattice of P
Status (general): Polynomial total time
Status (fixed dim.): Polynomial time
Solvable in O(min{m,n}· α· φ) time, where m is the number of facets, n is the number of vertices, α is the number of vertex-facet incidences, and φ is the size of the face lattice [33]. Note that φ is exponential in d (for fixed d it is polynomial in m and n). Without (asymptotically) increasing the running time it is also possible to label each node in the Hasse diagram by the dimension and the vertex set of the corresponding face.

It follows from [33] that one can compute the Hasse-diagram of the k-skeleton (i.e., all faces of dimensions at most k) of P in O(n· α· φ≤k) time, where φ≤k is the number of faces of dimensions at most k. Since the latter number is in O(nk+1), the k-skeleton can be computed in polynomial time (in the input size) for fixed k.


up forward Why are some symbols not displayed correctly?