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 3-dimensional Space.
 |
|
@incollection{Kur17MV, author = {Kurlin,V.}, title = {Computing invariants of knotted graphs given by sequences of points in 3-dimensional space}, booktitle = {Mathematics and Visualization IV (post-proceedings of TopoInVis 2015)}, publisher = {Springer}, pages = {349-363}, year = {2017} }- Abstract. We design a fast algorithm for computing the fundamental group of the complement to any knotted polygonal graph in 3-space. A polygonal graph consists of straight segments and is given by sequences of vertices along edge-paths. 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 3-space.
- Input : 3D coordinates of vertices of a polygonal chain K.
- Output : a presentation of the fundamental group of R3 - K.
- Running time : O(n2) for the length n of a polygonal chain K.
- C++ code : invariants-knotted-graphs.cpp, e-mail 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 3-page book.
 |
|
@incollection{KS16CCIS, author = {Kurlin, V. and Smithers, C.}, title = {A linear time algorithm for embedding arbitrary knotted graphs into a 3-page book}, booktitle = {Computer Vision, Imaging and Computer Graphics Theory and Applications}, publisher = {Springer}, year = {2016}, pages = {99-122} }
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 = {5-16}, publisher = {SciTePress} year = {2015} }- ISBN : 978-989-758-088-8 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 3-space. 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 3-space. Second we design a fast algorithm for drawing any knotted graph in the 3-page book, which is a union of 3 half-planes 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. Three-page embeddings provide simple linear codes of knotted graphs so that the isotopy problem for all graphs in 3-space completely reduces to a word problem in finitely presented semigroups.
- Input : a Gauss code of a plane diagram of a knotted graph in 3-space.
- Output : an embedding of the given knotted graph into the 3-page book.
- Running time : O(n) for the length n of a Gauss code of a knotted graph.
- C++ code : 3page-embeddings-graphs.cpp, e-mail vitaliy.kurlin@gmail.com for support.
Back to Top of this page | Back to Research & papers | Back to Home page