---
_id: '6556'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Kristóf
  full_name: Huszár, Kristóf
  id: 33C26278-F248-11E8-B48F-1D18A9856A87
  last_name: Huszár
  orcid: 0000-0002-5445-5057
- first_name: Jonathan
  full_name: Spreer, Jonathan
  last_name: Spreer
citation:
  ama: 'Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: <i>35th
    International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">10.4230/LIPIcs.SoCG.2019.44</a>'
  apa: 'Huszár, K., &#38; Spreer, J. (2019). 3-manifold triangulations with small
    treewidth. In <i>35th International Symposium on Computational Geometry</i> (Vol.
    129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>'
  chicago: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
    Treewidth.” In <i>35th International Symposium on Computational Geometry</i>,
    129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">https://doi.org/10.4230/LIPIcs.SoCG.2019.44</a>.
  ieee: K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,”
    in <i>35th International Symposium on Computational Geometry</i>, Portland, Oregon,
    United States, 2019, vol. 129, p. 44:1-44:20.
  ista: 'Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth.
    35th International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 129, 44:1-44:20.'
  mla: Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small
    Treewidth.” <i>35th International Symposium on Computational Geometry</i>, vol.
    129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:<a
    href="https://doi.org/10.4230/LIPIcs.SoCG.2019.44">10.4230/LIPIcs.SoCG.2019.44</a>.
  short: K. Huszár, J. Spreer, in:, 35th International Symposium on Computational
    Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.
conference:
  end_date: 2019-06-21
  location: Portland, Oregon, United States
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2019-06-18
corr_author: '1'
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-08T07:21:27Z
day: '01'
ddc:
- '516'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2019.44
external_id:
  arxiv:
  - '1812.05528'
file:
- access_level: open_access
  checksum: 29d18c435368468aa85823dabb157e43
  content_type: application/pdf
  creator: kschuh
  date_created: 2019-06-12T06:45:33Z
  date_updated: 2020-07-14T12:47:33Z
  file_id: '6557'
  file_name: 2019_LIPIcs-Huszar.pdf
  file_size: 905885
  relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: '       129'
keyword:
- computational 3-manifold topology
- fixed-parameter tractability
- layered triangulations
- structural graph theory
- treewidth
- cutwidth
- Heegaard genus
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 44:1-44:20
publication: 35th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - 978-3-95977-104-7
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '8032'
    relation: part_of_dissertation
    status: public
scopus_import: '1'
status: public
title: 3-manifold triangulations with small treewidth
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 129
year: '2019'
...