Nonrealizable minimal vertex triangulations of surfaces: Showing nonrealizability using oriented matroids and satisfiability solvers

Lars Schewe*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in ℝ3. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. Correcting a previous error in the literature, we construct the first infinite family of such nonrealizable triangulations of surfaces. These results were achieved by transforming the problem of finding suitable oriented matroids into a satisfiability problem. This method can be applied to other geometric realizability problems, e. g., for face lattices of polytopes.

Original languageEnglish
Pages (from-to)289-302
Number of pages14
JournalDiscrete and Computational Geometry
Volume43
Issue number2
Early online date2 Sep 2009
DOIs
Publication statusPublished - 1 Mar 2010

Keywords

  • Embeddings
  • Oriented matroids
  • Polyhedral surfaces
  • Satisfiability

Fingerprint

Dive into the research topics of 'Nonrealizable minimal vertex triangulations of surfaces: Showing nonrealizability using oriented matroids and satisfiability solvers'. Together they form a unique fingerprint.

Cite this