Some Results in Computational Topology
Authors:
Open Access
- 1 July 1973
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 20 (3) , 439-455
Abstract
It is the object of this paper to study the topological properties of finite graphs that can be embedded in the n -dimensional integral lattice (denoted N n ). The basic notion of deletability of a node is first introduced. A node is deletable with respect to a graph if certain computable conditions are satisfied on its neighborhood. An equivalence relation on graphs called reducibility and denoted by “∼” is then defined in terms of deletability, and it is shown that (a) most important topological properties of the graph (homotogy, homology, and cohomology groups) are ∼-invariants; (b) for graphs embedded in N 3 , different knot types belong to different ∼-equivalence classes; (c) it is decidable whether two graphs are reducible to each other in N 2 but this problem is undecidable in N n for n ≥ 4. Finally, it is shown that two different methods of approximating an n -dimensional closed manifold with boundary by a graph of the type studied in this paper lead to graphs whose corresponding homology groups are isomorphic.Keywords
This publication has 3 references indexed in Scilit:
- On the Topological Properties of Quantized Spaces, II. Connectivity and Order of ConnectivityJournal of the ACM, 1971
- Connectivity in Digital PicturesJournal of the ACM, 1970
- Homology1966