---
_id: '285'
abstract:
- lang: eng
  text: In graph theory, as well as in 3-manifold topology, there exist several width-type
    parameters to describe how "simple" or "thin" a given graph
    or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs,
    or the concept of thin position for 3-manifolds, play an important role when studying
    algorithmic problems; in particular, there is a variety of problems in computational
    3-manifold topology - some of them known to be computationally hard in general
    - that become solvable in polynomial time as soon as the dual graph of the input
    triangulation has bounded treewidth. In view of these algorithmic results, it
    is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth.
    We show that this is not the case, i.e., that there exists an infinite family
    of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth
    (the latter implies the former, but we present two separate proofs). We derive
    these results from work of Agol and of Scharlemann and Thompson, by exhibiting
    explicit connections between the topology of a 3-manifold M on the one hand and
    width-type parameters of the dual graphs of triangulations of M on the other hand,
    answering a question that had been raised repeatedly by researchers in computational
    3-manifold topology. In particular, we show that if a closed, orientable, irreducible,
    non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then
    the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).
acknowledgement: Research of the second author was supported by the Einstein Foundation
  (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons
  Visiting Professors” program).
alternative_title:
- LIPIcs
article_number: '46'
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
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds.
    In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.46">10.4230/LIPIcs.SoCG.2018.46</a>'
  apa: 'Huszár, K., Spreer, J., &#38; Wagner, U. (2018). On the treewidth of triangulated
    3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry,
    Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.46">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>'
  chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
    Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2018. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.46">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>.
  ieee: 'K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
    presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary,
    2018, vol. 99.'
  ista: 'Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds.
    SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.'
  mla: Huszár, Kristóf, et al. <i>On the Treewidth of Triangulated 3-Manifolds</i>.
    Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.46">10.4230/LIPIcs.SoCG.2018.46</a>.
  short: K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2018.
conference:
  end_date: 2018-06-14
  location: Budapest, Hungary
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2018-06-11
date_created: 2018-12-11T11:45:37Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2025-07-10T11:52:21Z
day: '01'
ddc:
- '516'
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.46
external_id:
  arxiv:
  - '1712.00434'
file:
- access_level: open_access
  checksum: 530d084116778135d5bffaa317479cac
  content_type: application/pdf
  creator: dernst
  date_created: 2018-12-17T15:32:38Z
  date_updated: 2020-07-14T12:45:51Z
  file_id: '5713'
  file_name: 2018_LIPIcs_Huszar.pdf
  file_size: 642522
  relation: main_file
file_date_updated: 2020-07-14T12:45:51Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2018.46
has_accepted_license: '1'
intvolume: '        99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
publication_identifier:
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7614'
quality_controlled: '1'
related_material:
  record:
  - id: '7093'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: On the treewidth of triangulated 3-manifolds
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: 99
year: '2018'
...