Abstract
A typical census of 3manifolds contains all manifolds (under various constraints) that can be triangulated with at most n tetrahedra. Although 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 4regular multigraphs on n nodes, and then (ii) for each multigraph G they enumerate possible 3manifold triangulations with G as their dual 1skeleton, 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.
BibTeX  Entry
@InProceedings{burton_et_al:LIPIcs:2015:5148,
author = {Benjamin A. Burton and William Pettersson},
title = {{An EdgeBased Framework for Enumerating 3Manifold Triangulations}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {270284},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5148},
URN = {urn:nbn:de:0030drops51485},
doi = {10.4230/LIPIcs.SOCG.2015.270},
annote = {Keywords: triangulations, enumeration, graph theory}
}
Keywords: 

triangulations, enumeration, graph theory 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015) 
Issue Date: 

2015 
Date of publication: 

11.06.2015 