Polyhedral Combinatorics - Graph-theoretic Properties

Graph-theoretic Properties

Along with investigating the numbers of faces of polytopes, researchers have studied other combinatorial properties of them, such as descriptions of the graphs obtained from the vertices and edges of polytopes (their 1-skeleta).

Balinski's theorem states that the graph obtained in this way from any d-dimensional convex polytope is d-vertex-connected. In the case of three-dimensional polyhedra, this property and planarity may be used to exactly characterize the graphs of polyhedra: Steinitz's theorem states that G is the skeleton of a three-dimensional polyhedron if and only if G is a 3-vertex-connected planar graph.

A theorem of Blind and Mani states that one can reconstruct the face structure of a simple polytope from its graph. This is in sharp contrast with (non-simple) neighborly polytopes whose graph is a complete graph. An elegant proof is due to Kalai and a polynomial time algorithm to recognize a face was recently found by Friedman.

In the context of the simplex method for linear programming, it is important to understand the diameter of a polytope, the minimum number of edges needed to reach any vertex by a path from any other vertex. The system of linear inequalities of a linear program define facets of a polytope representing all feasible solutions to the program, and the simplex method finds the optimal solution by following a path in this polytope. Thus, the diameter provides a lower bound on the number of steps this method requires.