Skip to main content
SpringerLink
Log in

Reconstructing a Simple Polytope from Its Graph

  • Chapter
  • First Online:
Combinatorial Optimization — Eureka, You Shrink!

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2570))

Abstract

Blind and Mani [2] 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 [15] 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 Körner [12].

Supported by the Deutsche Forschungsgemeinschaft, FOR 413/1-1 (Zi 475/3-1).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
eBook
USD 16.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 16.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented Matroids (2nd ed.), volume 46 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 1999.

    Google Scholar 

  2. R. Blind and P. Mani-Levitska. Puzzles and polytope isomorphisms. Aequationes Math., 34:287–297, 1987.

    Article  MATH  MathSciNet  Google Scholar 

  3. J. Bokowski and B. Sturmfels. Computational Synthetic Geometry, volume 1355 of Lecture Notes in Mathematics. Springer, Heidelberg, 1989.

    MATH  Google Scholar 

  4. M. Develin. E-mail conversation, Nov 2000. develin@bantha.org.

    Google Scholar 

  5. J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. — B (Math. and Math. Phys.), 69B:125–130, 1965.

    MathSciNet  Google Scholar 

  6. J. Edmonds. Paths, trees, and flowers. Can. J. Math., 17:449–467, 1965.

    MATH  MathSciNet  Google Scholar 

  7. M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.

    Google Scholar 

  8. M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In D. Hochbaum, editor, Approximation Algorithms, chapter 4. PWS Publishing Company, 1997.

    Google Scholar 

  9. J. E. Goodman, R. Pollack, and B. Sturmfels. The intrinsic spread of a configuration in ℝd. J. Am. Math. Soc., 3(3):639–651, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  10. C. Haase and G. M. Ziegler. Examples and counterexamples for Perles’ conjecture. Technical report, TU Berlin, 2001. To appear in: Discrete Comput. Geometry.

    Google Scholar 

  11. P. L. Hammer, B. Simeone, T. M. Liebling, and D. de Werra. From linear separability to unimodality: A hierarchy of pseudo-boolean functions. SIAM J. Discrete Math., 1:174–184, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  12. M. Joswig, V. Kaibel, and F. Körner. On the k-systems of a simple polytope. Technical report, TU Berlin, 2001. arXiv: math.CO/0012204, to appear in: Israel J. Math.

    Google Scholar 

  13. M. Joswig and G.M. Ziegler. Neighborly cubical polytopes. Discrete Comput. Geometry, 24:325–344, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  14. V. Kaibel and M. Pfetsch. Computing the face lattice of a polytope from its vertex-facet incidences. Technical report, TU Berlin, 2001. arXiv:math.MG/01060043, submitted.

    Google Scholar 

  15. G. Kalai. A simple way to tell a simple polytope from its graph. J. Comb. Theory, Ser. A, 49(2):381–383, 1988.

    Article  MATH  MathSciNet  Google Scholar 

  16. N. E. Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In O. Ya. Viro, editor, Topology and Geometry–Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pages 527–543. Springer, Heidelberg, 1988.

    Google Scholar 

  17. W. T. Tutte. A short proof of the factor theorem for finite graphs. Can. J. Math., 6:347–352, 1954.

    MATH  MathSciNet  Google Scholar 

  18. H. Whitney. Congruent graphs and the connectivity of graphs. Am. J. Math., 54:150–168, 1932.

    Article  MATH  MathSciNet  Google Scholar 

  19. G. M. Ziegler. Lectures on Polytopes. Springer-Verlag, New York, 1995. Revised edition 1998.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. TU Berlin, MA 6-2 Straße des 17. Juni 136, 10623, Berlin, Germany

    Volker Kaibel

Authors
  1. Volker Kaibel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany

    Michael Jünger

  2. Institut für Informatik, Universität Heidelberg, Im Neuenheimer Feld 368, 69120, Heidelberg, Germany

    Gerhard Reinelt

  3. Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, CNR, viale Manzoni 30, 00185, Rome, Italy

    Giovanni Rinaldi

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Kaibel, V. (2003). Reconstructing a Simple Polytope from Its Graph. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds) Combinatorial Optimization — Eureka, You Shrink!. Lecture Notes in Computer Science, vol 2570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36478-1_11

Download citation

  • DOI: https://doi.org/10.1007/3-540-36478-1_11

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00580-3

  • Online ISBN: 978-3-540-36478-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation