An edge-based framework for enumerating 3-manifold triangulations

DOI10.4230/LIPICS.SOCG.2015.270zbMATH Open1378.68161arXiv1412.2169MaRDI QIDQ5368693FDOQ5368693

Authors: William Pettersson, Benjamin A. Burton 

Publication date: 10 October 2017

Abstract: A typical census of 3-manifolds contains all manifolds (under various constraints) that can be triangulated with at most n tetrahedra. Al- though censuses are useful resources for mathematicians, constructing them is difficult: the best algorithms to date have not gone beyond n = 12. The underlying algorithms essentially (i) enumerate all relevant 4-regular multigraphs on n nodes, and then (ii) for each multigraph G they enumerate possible 3-manifold triangulations with G as their dual 1-skeleton, of which there could be exponentially many. In practice, a small number of multigraphs often dominate the running times of census algorithms: for example, in a typical census on 10 tetrahedra, almost half of the running time is spent on just 0.3% of the graphs. Here we present a new algorithm for stage (ii), which is the computational bottleneck in this process. The key idea is to build triangulations by recursively constructing neighbourhoods of edges, in contrast to traditional algorithms which recursively glue together pairs of tetrahedron faces. We implement this algorithm, and find experimentally that whilst the overall performance is mixed, the new algorithm runs significantly faster on those "pathological" multigraphs for which existing methods are extremely slow. In this way the old and new algorithms complement one another, and together can yield significant performance improvements over either method alone.

Full work available at URL: https://arxiv.org/abs/1412.2169

Recommendations

• Fixed parameter tractable algorithms in combinatorial topology
• Detecting genus in vertex links for the fast enumeration of \(3\)-manifold triangulations
• Efficient enumeration of 3-manifold triangulations
• Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find
• Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds

zbMATH Keywords

graph theoryenumerationtriangulations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Enumeration in graph theory (05C30) Triangulating manifolds (57Q15)

Cited In (9)

• Fixed parameter tractable algorithms in combinatorial topology
• Efficient enumeration of 3-manifold triangulations
• Knotted 4-regular graphs. II: Consistent application of the Pachner moves
• Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds
• A new combinatorial class of \(3\)-manifold triangulations
• The average edge order of triangulations of 3-manifolds with boundary
• The Pachner graph and the simplification of 3-sphere triangulations
• Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find
• Detecting genus in vertex links for the fast enumeration of \(3\)-manifold triangulations

This page was built for publication: An edge-based framework for enumerating 3-manifold triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368693)