Knot diagrams of treewidth two. (English) Zbl 07636197
Adler, Isolde (ed.) et al., Graph-theoretic concepts in computer science. 46th international workshop, WG 2020, Leeds, UK, June 24–26, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12301, 80-91 (2020).
Summary: 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.
For the entire collection see [Zbl 1502.68016].
For the entire collection see [Zbl 1502.68016].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Alexander, JW; Briggs, GB, On types of knotted curves, Ann. Math. (2), 28, 1-4, 562-586, 1926 · JFM 53.0549.02 · doi:10.2307/1968399 |
| [2] | Bodlaender, HL, A partial \(k\)-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1-45, 1998 · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4 |
| [3] | Bodlaender, H.L., Burton, B.A., Fomin, F.V., Grigoriev, A.: Knot diagrams of treewidth two (2019). http://arxiv.org/abs/1904.03117 |
| [4] | Dasbach, OT; Hougardy, S., Does the Jones polynomial detect unknottedness?, Exp. Math., 6, 1, 51-56, 1997 · Zbl 0883.57006 · doi:10.1080/10586458.1997.10504350 |
| [5] | de Mesmay, A., Rieck, Y.A., Sedgwick, E., Tancer, M.: The unbearable hardness of unknotting. In: 35th International Symposium on Computational Geometry, SoCG 2019, LIPIcs, vol. 129, pp. 49:1-49:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019) · Zbl 07559249 |
| [6] | Haken, W., Theorie der Normalflächen, Acta Math., 105, 245-375, 1961 · Zbl 0100.19402 · doi:10.1007/BF02559591 |
| [7] | Hass, J.; Lagarias, JC, The number of Reidemeister moves needed for unknotting, J. Am. Math. Soc., 14, 2, 399-428, 2001 · Zbl 0964.57005 · doi:10.1090/S0894-0347-01-00358-7 |
| [8] | Hass, J.; Lagarias, JC; Pippenger, N., The computational complexity of knot and link problems, J. ACM, 46, 2, 185-211, 1999 · Zbl 1065.68667 · doi:10.1145/301970.301971 |
| [9] | Henrich, A., Kauffman, L.H.: Unknotting unknots. arXiv preprint arXiv:1006.4176 (2010) |
| [10] | Koenig, D., Tsvietkova, A.: NP-hard problems naturally arising in knot theory. arXiv preprint arXiv:1809.10334 (2018) |
| [11] | Lackenby, M., A polynomial upper bound on Reidemeister moves, Ann. Math., 182, 2, 491-564, 2015 · Zbl 1329.57010 · doi:10.4007/annals.2015.182.2.3 |
| [12] | Lackenby, M.: The efficient certification of knottedness and thurston norm. arXiv preprint arXiv:1604.00290 (2016) |
| [13] | Makowsky, JA; Mariño, JP, The parameterized complexity of knot polynomials, J. Comput. Syst. Sci., 67, 742-756, 2003 · Zbl 1093.68043 · doi:10.1016/S0022-0000(03)00080-1 |
| [14] | Reidemeister, K., Knoten und Gruppen, Abh. Math. Sem. Univ. Hamburg, 5, 1, 7-23, 1927 · JFM 52.0578.04 · doi:10.1007/BF02952506 |
| [15] | Robertson, N.; Seymour, PD, Graph minors . II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309-322, 1986 · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4 |
| [16] | Rué, J.; Thilikos, DM; Velona, V., Structure and enumeration of \(K_4\)-minor-free links and link diagrams, Electron. Notes Discret. Math., 68, 119-124, 2018 · Zbl 1397.05169 · doi:10.1016/j.endm.2018.06.021 |
| [17] | Turing, AM, Solvable and Unsolvable Problems, 1954, London: Penguin Books, London |
| [18] | Torus knot (2019). http://mathworld.wolfram.com/TorusKnot.html |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
