License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.270
URN: urn:nbn:de:0030-drops-51485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5148/
Go to the corresponding LIPIcs Volume Portal

Burton, Benjamin A. ; Pettersson, William

An Edge-Based Framework for Enumerating 3-Manifold Triangulations

pdf-format:
65.pdf (0.5 MB)

Abstract

A typical census of 3-manifolds 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 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.

BibTeX - Entry

@InProceedings{burton_et_al:LIPIcs:2015:5148,
  author =	{Benjamin A. Burton and William Pettersson},
  title =	{{An Edge-Based Framework for Enumerating 3-Manifold Triangulations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{270--284},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5148},
  URN =		{urn:nbn:de:0030-drops-51485},
  doi =		{10.4230/LIPIcs.SOCG.2015.270},
  annote =	{Keywords: triangulations, enumeration, graph theory}
}

Keywords: triangulations, enumeration, graph theory
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI