A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\) (Q1699303)

A triangulation of a surface can be viewed as polyhedron on the surface such that each face is a triangle and the intersection of any two distinct triangles is either empty, a vertex, or an edge. Such a triangulation always exists for every compact surface with empty boundary [\textit{J. Gallier} and \textit{D. Xu}, A guide to the classification theorem for compact surfaces. Berlin: Springer (2013; Zbl 1270.57001)]. Moreover, any triangulation can be obtained from an irreducible one i.e., triangulation such that the contraction of an edge does not lead to another triangulation of the surface. In this context, irreducible triangulations are an important tool for tackling problems in combinatorial topology and computational geometry [\textit{H. Schipper}, Lect. Notes Comput. Sci. 553, 237--248 (1991; Zbl 0768.52011); \textit{V. Dujmović} et al., Eur. J. Comb. 32, No. 8, 1244--1252 (2011; Zbl 1229.05139); \textit{A. Nakamoto} and \textit{K. Ota}, J. Graph Theory 20, No. 2, 227--233 (1995; Zbl 0834.05021)]. In the article, starting from any boundaryless compact surface in the Euclidean \(d\)-dimensional space and a triangulation of it, the authors present a new algorithm for computing an irreducible triangulation of a given surface. The algorithm provides an alternative method to the one introduced in [\textit{T. Sulanke}, J. Comb. Theory, Ser. B 96, No. 6, 964--972 (2006; Zbl 1106.05036)]. Furthermore, the results presented have been used for approaching the problem of converting a triangulation of a closed surface into quadrangulations with the same set of vertices [\textit{T. Lemos} et al., ``An experimental comparison of algorithms for converting triangulations of closed surfaces into quadrangulations'', Preprint, \url{http://www.crab.rutgers.edu/~rsuneeta/hpc/research/imr15_long.pdf}].