Nonrealizable Minimal Vertex Triangulations of Surfaces: Showing Nonrealizability Using Oriented Matroids and Satisfiability Solvers

作者：Schewe Lars^*

来源：Discrete & Computational Geometry, 2010, 43(2): 289-302.

DOI：10.1007/s00454-009-9222-y

• Polyhedral surfaces
• Embeddings
• Oriented matroids
• Satisfiability

We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in a"e(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.

• 出版日期2010-3