2002/02/12 by Volker Kaibel, Kaibel, Volker
Computer Science · Mathematics · #52B11 (Primary) 52B05 #52B22 (Secondary) #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:52B05 #msc:52B11 #msc:52B22
paper · pdf · doi:10.48550/arxiv.math/0202103
14 pages
arxiv created 2002/02/12 · openalex publication_date 2002/02/12 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Blind and Mani (1987) proved that the entire combinatorial structure (the vertex-facet incidences) of a simple convex polytope is determined by its abstract graph. Their proof is not constructive. Kalai (1988) found a short, elegant, and algorithmic proof of that result. However, his algorithm has always exponential running time. We show that the problem to reconstruct the vertex-facet incidences of a simple polytope P from its graph can be formulated as a combinatorial optimization problem that is strongly dual to the problem of finding an abstract objective function on P (i.e., a shelling order of the facets of the dual polytope of P). Thereby, we derive polynomial certificates for both the vertex-facet incidences as well as for the abstract objective functions in terms of the graph of P. The paper is a variation on joint work with Michael Joswig and Friederike Koerner (2001).