Knot Diagrams of Treewidth Two
Publication date
2020-10-16
Authors
Bodlaender, Hans
Burton, Benjamin
Fomin, Fedor V.
Grigoriev, Alexander
Editors
Adler, Isolde
Müller, Haiko
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
In this paper, we study knot diagrams for which the underlying graph has treewidth two. We give a linear time algorithm for the following problem: given a knot diagram of treewidth two, does it represent the trivial knot? We also show that for a link diagram of treewidth two we can test in linear time if it represents the unlink. From the algorithm, it follows that a diagram of the trivial knot of treewidth 2 can always be reduced to the trivial diagram with at most n untwist and unpoke Reidemeister moves.
Keywords
Graph algorithms, Knot diagrams, Knot theory, Series parallel graphs, Treewidth, Taverne, Theoretical Computer Science, General Computer Science
Citation
Bodlaender, H L, Burton, B, Fomin, F V & Grigoriev, A 2020, Knot Diagrams of Treewidth Two. in I Adler & H Müller (eds), Graph-Theoretic Concepts in Computer Science : 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers. 1 edn, Lecture Notes in Computer Science, vol. 12301 , Theoretical Computer Science and General Issues book sub series, Springer, Cham, pp. 80-91, 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020, Leeds, United Kingdom, 24/06/20. https://doi.org/10.1007/978-3-030-60440-0_7, conference