Knot Diagrams of Treewidth Two

Hans L. Bodlaender; Benjamin Burton; Fedor V. Fomin; Alexander Grigoriev

doi:10.1007/978-3-030-60440-0_7

Knot Diagrams of Treewidth Two

Hans L. Bodlaender^*, Benjamin Burton, Fedor V. Fomin, Alexander Grigoriev

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers
Editors	Isolde Adler, Haiko Müller
Place of Publication	Cham
Publisher	Springer
Pages	80-91
Number of pages	12
Edition	1
ISBN (Electronic)	978-3-030-60440-0
ISBN (Print)	978-3-030-60439-4
DOIs	https://doi.org/10.1007/978-3-030-60440-0_7
Publication status	Published - 16 Oct 2020
Event	46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020 - Leeds, United Kingdom Duration: 24 Jun 2020 → 26 Jun 2020

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12301
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Theoretical Computer Science and General Issues book sub series
Publisher	Springer
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Conference

Conference	46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020
Country/Territory	United Kingdom
City	Leeds
Period	24/06/20 → 26/06/20

Funding

A large part of this research was done during the workshop Fixed Parameter Computational Geometry at the Lorentz Center in Leiden. The research of the first author was partially supported by the Networks project, supported by the Netherlands Organization for Scientific Research N.W.O. The second author was supported by the Australian Research Council under the Discovery Projects scheme (DP150104108). The third author was supported by the Research Council of Norway via the project “MULTIVAL”.

Keywords

Graph algorithms
Knot diagrams
Knot theory
Series parallel graphs
Treewidth

Access to Document

10.1007/978-3-030-60440-0_7

Bodlaender2020_Chapter_KnotDiagramsOfTreewidthTwoFinal published version, 579 KBLicence: Taverne

Cite this

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 ed., pp. 80-91). (Lecture Notes in Computer Science; Vol. 12301 ), (Theoretical Computer Science and General Issues book sub series). Springer. https://doi.org/10.1007/978-3-030-60440-0_7

Bodlaender, Hans L. ; Burton, Benjamin ; Fomin, Fedor V. et al. / Knot Diagrams of Treewidth Two. Graph-Theoretic Concepts in Computer Science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers. editor / Isolde Adler ; Haiko Müller. 1. ed. Cham : Springer, 2020. pp. 80-91 (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues book sub series).

@inproceedings{86eb1ef212874da79c30ab60443b6a89,

title = "Knot Diagrams of Treewidth Two",

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",

author = "Bodlaender, {Hans L.} and Benjamin Burton and Fomin, {Fedor V.} and Alexander Grigoriev",

year = "2020",

month = oct,

day = "16",

doi = "10.1007/978-3-030-60440-0_7",

language = "English",

isbn = "978-3-030-60439-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "80--91",

editor = "Isolde Adler and Haiko M{\"u}ller",

booktitle = "Graph-Theoretic Concepts in Computer Science",

edition = "1",

note = "46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020 ; Conference date: 24-06-2020 Through 26-06-2020",

}

Bodlaender, HL, Burton, B, Fomin, FV & 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

Knot Diagrams of Treewidth Two. / Bodlaender, Hans L.; Burton, Benjamin; Fomin, Fedor V. et al.
Graph-Theoretic Concepts in Computer Science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers. ed. / Isolde Adler; Haiko Müller. 1. ed. Cham: Springer, 2020. p. 80-91 (Lecture Notes in Computer Science; Vol. 12301 ), (Theoretical Computer Science and General Issues book sub series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Knot Diagrams of Treewidth Two

AU - Bodlaender, Hans L.

AU - Burton, Benjamin

AU - Fomin, Fedor V.

AU - Grigoriev, Alexander

PY - 2020/10/16

Y1 - 2020/10/16

N2 - 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.

AB - 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.

KW - Graph algorithms

KW - Knot diagrams

KW - Knot theory

KW - Series parallel graphs

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85093852390&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-60440-0_7

DO - 10.1007/978-3-030-60440-0_7

M3 - Conference contribution

AN - SCOPUS:85093852390

SN - 978-3-030-60439-4

T3 - Lecture Notes in Computer Science

SP - 80

EP - 91

BT - Graph-Theoretic Concepts in Computer Science

A2 - Adler, Isolde

A2 - Müller, Haiko

PB - Springer

CY - Cham

T2 - 46th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2020

Y2 - 24 June 2020 through 26 June 2020

ER -

Bodlaender HL, Burton B, Fomin FV, Grigoriev A. Knot Diagrams of Treewidth Two. In Adler I, Müller H, editors, Graph-Theoretic Concepts in Computer Science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers. 1 ed. Cham: Springer. 2020. p. 80-91. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues book sub series). doi: 10.1007/978-3-030-60440-0_7

Knot Diagrams of Treewidth Two

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this