A Linear Time Algorithm for Visualizing Knotted Structures in 3 Pages

Kurlin, Vitaliy

doi:10.5220/0005259900050016

A Linear Time Algorithm for Visualizing Knotted Structures in 3 Pages

Kurlin, Vitaliy

Authors

Vitaliy Kurlin

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.

Citation

Kurlin, V. (2015). A Linear Time Algorithm for Visualizing Knotted Structures in 3 Pages. In Proceedings of the 6th International Conference on Information Visualization Theory and Applications, IVAPP-2015, 11-14 March 2015, Berlin, Germany (5-16). https://doi.org/10.5220/0005259900050016

Conference Name	IVAPP 2015 : 6th International Conference on Information Visualization Theory and Applications.
Conference Location	Berlin, Germany
Start Date	Mar 11, 2015
End Date	Mar 14, 2015
Publication Date	Mar 14, 2015
Deposit Date	Feb 6, 2015
Publicly Available Date	Mar 5, 2015
Volume	1
Pages	5-16
Book Title	Proceedings of the 6th International Conference on Information Visualization Theory and Applications, IVAPP-2015, 11-14 March 2015, Berlin, Germany.
DOI	https://doi.org/10.5220/0005259900050016
Keywords	Graph visualization, Graph drawing, Knot, Knotted graph, Book embedding, Plane diagram, Gauss code.