---
_id: '7944'
abstract:
- lang: eng
  text: "This thesis considers two examples of reconfiguration problems: flipping
    edges in edge-labelled triangulations of planar point sets and swapping labelled
    tokens placed on vertices of a graph. In both cases the studied structures – all
    the triangulations of a given point set or all token placements on a given graph
    – can be thought of as vertices of the so-called reconfiguration graph, in which
    two vertices are adjacent if the corresponding structures differ by a single elementary
    operation – by a flip of a diagonal in a triangulation or by a swap of tokens
    on adjacent vertices, respectively. We study the reconfiguration of one instance
    of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor
    triangulations of point sets in which each edge has a unique label and a flip
    transfers the label from the removed edge to the new edge, we prove a polynomial-time
    testable condition, called the Orbit Theorem, that characterizes when two triangulations
    of the same point set lie in the same connected component of the reconfiguration
    graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot.
    We additionally provide a polynomial time algorithm that computes a reconfiguring
    flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties
    of a certain high-dimensional cell complex that has the usual reconfiguration
    graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph,
    we make partial progress on the problem of finding shortest reconfiguration sequences.
    We disprove the so-called Happy Leaf Conjecture and demonstrate the importance
    of swapping tokens that are already placed at the correct vertices. We also prove
    that a generalization of the problem to weighted coloured token swapping is NP-hard
    on trees but solvable in polynomial time on paths and stars."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Zuzana
  full_name: Masárová, Zuzana
  id: 45CFE238-F248-11E8-B48F-1D18A9856A87
  last_name: Masárová
  orcid: 0000-0002-6660-1322
citation:
  ama: Masárová Z. Reconfiguration problems. 2020. doi:<a href="https://doi.org/10.15479/AT:ISTA:7944">10.15479/AT:ISTA:7944</a>
  apa: Masárová, Z. (2020). <i>Reconfiguration problems</i>. Institute of Science
    and Technology Austria. <a href="https://doi.org/10.15479/AT:ISTA:7944">https://doi.org/10.15479/AT:ISTA:7944</a>
  chicago: Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and
    Technology Austria, 2020. <a href="https://doi.org/10.15479/AT:ISTA:7944">https://doi.org/10.15479/AT:ISTA:7944</a>.
  ieee: Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology
    Austria, 2020.
  ista: Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology
    Austria.
  mla: Masárová, Zuzana. <i>Reconfiguration Problems</i>. Institute of Science and
    Technology Austria, 2020, doi:<a href="https://doi.org/10.15479/AT:ISTA:7944">10.15479/AT:ISTA:7944</a>.
  short: Z. Masárová, Reconfiguration Problems, Institute of Science and Technology
    Austria, 2020.
date_created: 2020-06-08T00:49:46Z
date_published: 2020-06-09T00:00:00Z
date_updated: 2023-09-07T13:17:37Z
day: '09'
ddc:
- '516'
- '514'
degree_awarded: PhD
department:
- _id: HeEd
- _id: UlWa
doi: 10.15479/AT:ISTA:7944
file:
- access_level: open_access
  checksum: df688bc5a82b50baee0b99d25fc7b7f0
  content_type: application/pdf
  creator: zmasarov
  date_created: 2020-06-08T00:34:00Z
  date_updated: 2020-07-14T12:48:05Z
  file_id: '7945'
  file_name: THESIS_Zuzka_Masarova.pdf
  file_size: 13661779
  relation: main_file
- access_level: closed
  checksum: 45341a35b8f5529c74010b7af43ac188
  content_type: application/zip
  creator: zmasarov
  date_created: 2020-06-08T00:35:30Z
  date_updated: 2020-07-14T12:48:05Z
  file_id: '7946'
  file_name: THESIS_Zuzka_Masarova_SOURCE_FILES.zip
  file_size: 32184006
  relation: source_file
file_date_updated: 2020-07-14T12:48:05Z
has_accepted_license: '1'
keyword:
- reconfiguration
- reconfiguration graph
- triangulations
- flip
- constrained triangulations
- shellability
- piecewise-linear balls
- token swapping
- trees
- coloured weighted token swapping
language:
- iso: eng
license: https://creativecommons.org/licenses/by-sa/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: '160'
publication_identifier:
  isbn:
  - 978-3-99078-005-3
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '7950'
    relation: part_of_dissertation
    status: public
  - id: '5986'
    relation: part_of_dissertation
    status: public
status: public
supervisor:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
title: Reconfiguration problems
tmp:
  image: /images/cc_by_sa.png
  legal_code_url: https://creativecommons.org/licenses/by-sa/4.0/legalcode
  name: Creative Commons Attribution-ShareAlike 4.0 International Public License (CC
    BY-SA 4.0)
  short: CC BY-SA (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_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
date_created: 2019-06-11T20:09:57Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:18:26Z
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'
...