Some Results in Computational Topology
George Tourlakis, John Mylopoulos · Journal of the ACM · 1973
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.