A new approach to crushing 3-manifold triangulations

DOI10.1007/S00454-014-9572-YzbMATH Open1317.57012arXiv1212.1441OpenAlexW3098571429MaRDI QIDQ742827FDOQ742827

Authors: Benjamin A. Burton 

Publication date: 19 September 2014

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: The crushing operation of Jaco and Rubinstein is a powerful technique in algorithmic 3-manifold topology: it enabled the first practical implementations of 3-sphere recognition and prime decomposition of orientable manifolds, and it plays a prominent role in state-of-the-art algorithms for unknot recognition and testing for essential surfaces. Although the crushing operation will always reduce the size of a triangulation, it might alter its topology, and so it requires a careful theoretical analysis for the settings in which it is used. The aim of this short paper is to make the crushing operation more accessible to practitioners, and easier to generalise to new settings. When the crushing operation was first introduced, the analysis was powerful but extremely complex. Here we give a new treatment that reduces the crushing process to a sequential combination of three "atomic" operations on a cell decomposition, all of which are simple to analyse. As an application, we generalise the crushing operation to the setting of non-orientable 3-manifolds, where we obtain a new practical and robust algorithm for non-orientable prime decomposition. We also apply our crushing techniques to the study of non-orientable minimal triangulations.

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

Recommendations

• A new approach to crushing 3-manifold triangulations
• The Pachner graph and the simplification of 3-sphere triangulations
• scientific article; zbMATH DE number 1857881
• Simplifying triangulations of \(S^3\).
• Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find

zbMATH Keywords

algorithmstriangulations3-manifoldsprime decompositionnormal surfaces

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Triangulating manifolds (57Q15)

Cites Work

• Algorithms for the complete decomposition of a closed \(3\)-manifold
• A new decomposition theorem for 3-manifolds
• Decision problems in the space of Dehn fillings
• Title not available (Why is that?)
• Algorithmic topology and classification of 3-manifolds
• 0-efficient triangulations of 3-manifolds
• Computational topology with Regina: algorithms, heuristics and implementations
• Computing closed essential surfaces in knot complements
• Introducing Regina, The 3-Manifold Topology Software
• Complexity theory of three-dimensional manifolds
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Title not available (Why is that?)
• Three-Manifolds Having Complexity At Most 9
• FACE PAIRING GRAPHS AND 3-MANIFOLD ENUMERATION
• Über das Homöomorphieproblem der 3-Mannigfaltigkeiten. I
• An algorithm to determine the Heegaard genus of a 3-manifold
• Quadrilateral–Octagon Coordinates for Almost Normal Surfaces
• The Weber-Seifert dodecahedral space is non-Haken
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• A polynomial-time algorithm to compute Turaev-Viro invariants \(\mathrm{TV}_{4,q}\) of 3-manifolds with bounded first Betti number
• Treewidth, crushing and hyperbolic volume
• Algorithms for contractibility of compressed curves on 3-manifold boundaries
• On the hardness of finding normal surfaces
• Finding non-orientable surfaces in 3-manifolds
• On the pathwidth of hyperbolic 3-manifolds
• A new approach to crushing 3-manifold triangulations
• The computational complexity of classical knot recognition
• Frontiers of sphere recognition in practice

Uses Software

• Regina
• Homology

This page was built for publication: A new approach to crushing 3-manifold triangulations

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