License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.50
URN: urn:nbn:de:0030-drops-179002
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17900/
Go to the corresponding LIPIcs Volume Portal

Lunel, Corentin ; de Mesmay, Arnaud

A Structural Approach to Tree Decompositions of Knots and Spatial Graphs

pdf-format:
LIPIcs-SoCG-2023-50.pdf (0.7 MB)

Abstract

Knots are commonly represented and manipulated via diagrams, which are decorated planar graphs. When such a knot diagram has low treewidth, parameterized graph algorithms can be leveraged to ensure the fast computation of many invariants and properties of the knot. It was recently proved that there exist knots which do not admit any diagram of low treewidth, and the proof relied on intricate low-dimensional topology techniques. In this work, we initiate a thorough investigation of tree decompositions of knot diagrams (or more generally, diagrams of spatial graphs) using ideas from structural graph theory. We define an obstruction on spatial embeddings that forbids low tree width diagrams, and we prove that it is optimal with respect to a related width invariant. We then show the existence of this obstruction for knots of high representativity, which include for example torus knots, providing a new and self-contained proof that those do not admit diagrams of low treewidth. This last step is inspired by a result of Pardon on knot distortion.

BibTeX - Entry

@InProceedings{lunel_et_al:LIPIcs.SoCG.2023.50,
  author =	{Lunel, Corentin and de Mesmay, Arnaud},
  title =	{{A Structural Approach to Tree Decompositions of Knots and Spatial Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17900},
  URN =		{urn:nbn:de:0030-drops-179002},
  doi =		{10.4230/LIPIcs.SoCG.2023.50},
  annote =	{Keywords: Knots, Spatial Graphs, Tree Decompositions, Tangle, Representativity}
}

Keywords: Knots, Spatial Graphs, Tree Decompositions, Tangle, Representativity
Collection: 39th International Symposium on Computational Geometry (SoCG 2023)
Issue Date: 2023
Date of publication: 09.06.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI