SGML results in computational topology

It is the object of this paper to study the topological properties of finite graphs that can be imbedded in the n-dimensional integral lattice (denoted Nn). 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 (homotopy, homology and cohomology groups) are ∼-invariants, (b) for graphs imbedded in N3 different knot types belong to different ∼-equivalence classes, (c) it is decidable whether two graphs are reducible to each other in N2 but this problem is undecidable in Nn 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 here lead to graphs whose corresponding homology groups are isomorphic.