---
res:
bibo_abstract:
- 'Motivated by fixed-parameter tractable (FPT) problems in computational topology,
we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined
to be the minimum treewidth of the face pairing graph of any triangulation T of
M. In this setting the relationship between the topology of a 3-manifold and its
treewidth is of particular interest. First, as a corollary of work of Jaco and
Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth
tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination
with our earlier work with Wagner, this yields that for non-Haken manifolds the
Heegaard genus and the treewidth are within a constant factor. Second, we characterize
all 3-manifolds of treewidth one: These are precisely the lens spaces and a single
other Seifert fibered space. Furthermore, we show that all remaining orientable
Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth
two. In particular, for every spherical 3-manifold we exhibit a triangulation
of treewidth at most two. Our results further validate the parameter of treewidth
(and other related parameters such as cutwidth or congestion) to be useful for
topological computing, and also shed more light on the scope of existing FPT-algorithms
in the field.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Kristóf
foaf_name: Huszár, Kristóf
foaf_surname: Huszár
foaf_workInfoHomepage: http://www.librecat.org/personId=33C26278-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-5445-5057
- foaf_Person:
foaf_givenName: Jonathan
foaf_name: Spreer, Jonathan
foaf_surname: Spreer
bibo_doi: 10.4230/LIPIcs.SoCG.2019.44
bibo_volume: 129
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/978-3-95977-104-7
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik@
dct_subject:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
dct_title: 3-manifold triangulations with small treewidth@
...