Topology Atlas | Conferences

Knots in Washington XXXIII; Categorification of Knots, Algebras, and Quandles; Quantum Computing
December 2-4, 2011
George Washington University
Washington, DC, USA

Organizers
Valentina Harizanov (GWU),Mark Kidwell (U.S. Naval Academy and GWU), Jozef H. Przytycki (GWU), Yongwu Rong (GWU), Radmila Sazdanovic (U.Penn), Alexander Shumakovitch (GWU), Hao Wu (GWU)

Conference Homepage


Grid2Mosaic2Grid: A Complete Pair of Polynomial Knot Algorithms
by
Omar Shehab
University of Maryland, Baltimore County
Coauthors: Sumeetkumar Bagde (University of Maryland, Baltimore County) Samuel J. Lomonaco Jr. (University of Maryland, Baltimore County)

Tame Knot Diagrams can be represented by two different discrete structures, namely, Grid Diagrams and Knot Mosaics. This report proposes two polynomial time algorithms for translations between Grid Diagrams and Knot Mosaics. It is shown that that the time complexity of both algorithms is O(n3). These results prove that Grid Diagrams and Knot Mosaics are topologically equivalent. This equivalence is efficiently computable. We also conjecture that the two Cromwell moves of Grid Diagrams, i.e. Castling and Stabilization, are equivalent to sequences of planar moves defined for Knot Mosaics. These equivalences are also conjectured to be polynomially computable.

Date received: November 23, 2011

Copyright © 2011 by the author(s). The author(s) of this work and the organizers of the conference have granted their consent to include this abstract in Topology Atlas. Document # cbdt-24.