---
_id: '7093'
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.\r\nIn 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).\r\nWe derive
    these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann,
    Schultens and Saito 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 18(k+1) (resp. 4(3k+1))."
article_processing_charge: No
article_type: original
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.
    <i>Journal of Computational Geometry</i>. 2019;10(2):70–98. doi:<a href="https://doi.org/10.20382/JOGC.V10I2A5">10.20382/JOGC.V10I2A5</a>
  apa: Huszár, K., Spreer, J., &#38; Wagner, U. (2019). On the treewidth of triangulated
    3-manifolds. <i>Journal of Computational Geometry</i>. Computational Geometry
    Laborartoy. <a href="https://doi.org/10.20382/JOGC.V10I2A5">https://doi.org/10.20382/JOGC.V10I2A5</a>
  chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
    Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>. Computational
    Geometry Laborartoy, 2019. <a href="https://doi.org/10.20382/JOGC.V10I2A5">https://doi.org/10.20382/JOGC.V10I2A5</a>.
  ieee: K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
    <i>Journal of Computational Geometry</i>, vol. 10, no. 2. Computational Geometry
    Laborartoy, pp. 70–98, 2019.
  ista: Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds.
    Journal of Computational Geometry. 10(2), 70–98.
  mla: Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal
    of Computational Geometry</i>, vol. 10, no. 2, Computational Geometry Laborartoy,
    2019, pp. 70–98, doi:<a href="https://doi.org/10.20382/JOGC.V10I2A5">10.20382/JOGC.V10I2A5</a>.
  short: K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019)
    70–98.
date_created: 2019-11-23T12:14:09Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2025-07-10T11:52:21Z
day: '01'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.20382/JOGC.V10I2A5
external_id:
  arxiv:
  - '1712.00434'
file:
- access_level: open_access
  checksum: c872d590d38d538404782bca20c4c3f5
  content_type: application/pdf
  creator: khuszar
  date_created: 2019-11-23T12:35:16Z
  date_updated: 2020-07-14T12:47:49Z
  file_id: '7094'
  file_name: 479-1917-1-PB.pdf
  file_size: 857590
  relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
intvolume: '        10'
issue: '2'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 70–98
publication: Journal of Computational Geometry
publication_identifier:
  issn:
  - 1920-180X
publication_status: published
publisher: Computational Geometry Laborartoy
quality_controlled: '1'
related_material:
  record:
  - id: '8032'
    relation: part_of_dissertation
    status: public
  - id: '285'
    relation: earlier_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: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10
year: '2019'
...