Knot Diagrams of Treewidth Two

April 05, 2019 Β· Declared Dead Β· πŸ› International Workshop on Graph-Theoretic Concepts in Computer Science

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Hans L. Bodlaender, Benjamin Burton, Fedor V. Fomin, Alexander Grigoriev arXiv ID 1904.03117 Category cs.DS: Data Structures & Algorithms Citations 3 Venue International Workshop on Graph-Theoretic Concepts in Computer Science Last Checked 4 months ago
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 unknot? 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 unknot of treewidth 2 can always be reduced to the trivial diagram with at most $n$ (un)twist and (un)poke Reidemeister moves.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted