Non-Realizable Minimal Vertex Triangulations of Surfaces: Showing Non-Realizability using Oriented Matroids and Satisfiability Solvers

2008/01/16 by Lars Schewe, Schewe, Lars
Computer Science · Mathematics · #52B70 #52C40 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Geometric and Algebraic Topology #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.0801.2582

openalex publication_date 2008/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that no minimal vertex triangulation of a closed, connected, orientable 2-manifold of genus 6 admits a polyhedral embedding in R³. We also provide examples of minimal vertex triangulations of closed, connected, orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings. We construct a new infinite family of non-realizable 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.

Related

• Non-existence of polyhedral immersions of triangulated surfaces in ℝ³
• Polyhedral Embeddings and Immersions of Many Triangulated 2-Manifolds with Few Vertices
• Irreducible triangulations of low genus surfaces
• Polyhedra of genus 3 with 10 vertices and minimal coordinates
• Orienting triangulations