Project Knotted graphs based on papers in MV 2017 CCIS 2016 IVAPP 2015
Paper: Computing invariants of knotted graphs given by sequences of points in 3dimensional Space.

@incollection{Kur17MV, author = {Kurlin,V.}, title = {Computing invariants of knotted graphs given by sequences of points in 3dimensional space}, booktitle = {Mathematics and Visualization IV (postproceedings of TopoInVis 2015)}, publisher = {Springer}, pages = {349363}, year = {2017} }
 Abstract. We design a fast algorithm for computing the fundamental group of the complement to any knotted polygonal graph in 3space. A polygonal graph consists of straight segments and is given by sequences of vertices along edgepaths. This polygonal model is motivated by protein backbones described in the Protein Data Bank by 3D positions of atoms. The KGG algorithm simplifies a knotted graph and computes a short presentation of the Knotted Graph Group containing powerful invariants for classifying graphs up to isotopy. We use only a reduced plane diagram without building a large complex representing the complement of a graph in 3space.
 Input : 3D coordinates of vertices of a polygonal chain K.
 Output : a presentation of the fundamental group of R^{3}  K.
 Running time : O(n^{2}) for the length n of a polygonal chain K.
 C++ code : invariantsknottedgraphs.cpp, email vitaliy.kurlin@gmail.com for support.
 Demo input : file with 3D coordinates trefoil.txt. Input PDB files from Protein Data Bank: 1V2X, 3OIL, 3OYS, 2RH3, 3NOU, 3NOT, 3NOP, 3ZQ5.
Back to Top of this page  Back to Research & papers  Back to Home page
Paper: A linear time algorithm for embedding arbitrary knotted graphs into a 3page book.

@incollection{KS16CCIS, author = {Kurlin, V. and Smithers, C.}, title = {A linear time algorithm for embedding arbitrary knotted graphs into a 3page book}, booktitle = {Computer Vision, Imaging and Computer Graphics Theory and Applications}, publisher = {Springer}, year = {2016}, pages = {99122} }
Back to Top of this page  Back to Research & papers  Back to Home page
Paper: A linear time algorithm for visualizing knotted structures in 3 pages.

@inproceedings{Kur15IVAPP, author = {Kurlin, V.}, title = {A linear time algorithm for visualizing knotted structures in 3 pages}, booktitle = {Proceedings of IVAPP 2015: Information Visualization Theory and Applications}, pages = {516}, publisher = {SciTePress} year = {2015} }
 ISBN : 9789897580888 DOI : 10.5220/0005259900050016
 Abstract. We introduce simple codes and fast visualization tools for knotted structures in molecules and neural networks. Knots, links and more general knotted graphs are studied up to an ambient isotopy in Euclidean 3space. A knotted graph can be represented by a plane diagram or by an abstract Gauss code. First we recognize in linear time if an abstract Gauss code represents an actual graph embedded in 3space. Second we design a fast algorithm for drawing any knotted graph in the 3page book, which is a union of 3 halfplanes along their common boundary line. The running time of our drawing algorithm is linear in the length of a Gauss code of a given graph. Threepage embeddings provide simple linear codes of knotted graphs so that the isotopy problem for all graphs in 3space completely reduces to a word problem in finitely presented semigroups.
 Input : a Gauss code of a plane diagram of a knotted graph in 3space.
 Output : an embedding of the given knotted graph into the 3page book.
 Running time : O(n) for the length n of a Gauss code of a knotted graph.
 C++ code : 3pageembeddingsgraphs.cpp, email vitaliy.kurlin@gmail.com for support.
Back to Top of this page  Back to Research & papers  Back to Home page