Computing linking numbers of a filtration. (English) Zbl 1032.92014

From the introduction: The focus of this paper is the linking number. Intuitively, this invariant detects if components of a complex are linked and cannot be separated. We hope to eventually incorporate our algorithm into publicly available software as a tool for detecting existence of interlocked molecular rings. Given a filtration, the main contributions of this paper are:
(i) the extension of the definition of the linking number to graphs, using a canonical basis,
(ii) an algorithm for enumerating and generating all cycles and their spanning surfaces within a filtration,
(iii) data structures for efficient enumeration of co-existing pairs of cycles in different components,
(iv) an algorithm for computing the linking number of a pair of cycles,
(v) and the implementation of the algorithms and experimentation on real data sets.
Algorithm (iv) is based on spanning surfaces of cycles, giving us an approximation to the linking number in the case of non-orientable or self-intersecting surfaces. Such cases do not arise often in practice, as shown in Section 6. However, we note in Section 2 that the linking number of a pair may be also computed by alternate algorithms. Regardless of the approach taken, pairs of potentially linked cycles must be first detected and enumerated. We provide the algorithms and data structures of such enumeration in (i–iii).


92C40 Biochemistry, molecular biology
57M99 General low-dimensional topology
57Q99 PL-topology
92-08 Computational methods for problems pertaining to biology