Finding a Polytope from Its Graph in Polynomial Time

摘要

We show that one can compute a (simple) polytope from its graph in Polynomial time. This computation of a polytope from its graph was shown to be solvable by Blind and Mani and more recently Kalai provided a simple proof that leads to an exponential time algorithm. Our proof relies on a Primal-Dual characterization by Joswig, Kaibel and Korner. We describe an exponential Linear Programming which can be used to construct the solution and show that it can be solved in polynomial time.