  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.
