Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds

2006/08/31 by Stefan Hougardy, T. Sulanke, Frank H. Lutz +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Computational Geometry and Mesh Generation #Geometric and Algebraic Topology #math.CO #math.MG #msc:52B70 #msc:57Q15

paper · pdf · doi:10.1016/j.ejc.2008.12.016

22 pages, 11 figures, various minor revisions, to appear in Experimental Mathematics

openalex publication_date 2009/01/14 · arxiv created 2009/05/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

Deciding realizability of a given polyhedral map on a (compact, connected) surface belongs to the hard problems in discrete geometry, from the theoretical, the algorithmic, and the practical point of view. In this paper, we present a heuristic algorithm for the realization of simplicial maps, based on the intersection edge functional. The heuristic was used to find geometric realizations in R³ for all vertex-minimal triangulations of the orientable surfaces of genus g=3 and g=4. Moreover, for the first time, examples of simplicial polyhedra in R³ of genus 5 with 12 vertices were obtained.

Citations

• Using the Borsuk–Ulam Theorem
• Combinatorial 3-manifolds with 10 vertices
• Generating irreducible triangulations of surfaces
• Knotted Polyhedral Tori
• Irreducible triangulations of low genus surfaces
• Triangulated Manifolds with Few Vertices: Vertex-Transitive Triangulations I
• A note on the existence of k, k-equivelar polyhedral maps
• Polyhedra of genus 2 with 10 vertices and minimal coordinates
• Triangulated Manifolds with Few Vertices: Combinatorial Manifolds
• Finite extinction time for the solutions to the Ricci flow on certain three-manifolds
• Ricci flow with surgery on three-manifolds
• Polyhedral Surfaces in Wedge Products
• Non-Realizable Minimal Vertex Triangulations of Surfaces: Showing Non-Realizability using Oriented Matroids and Satisfiability Solvers
• Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds