Some Results in Computational Topology

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 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 (homotogy, homology, and cohomology groups) are ∼-invariants; (b) for graphs embedded 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 in this paper lead to graphs whose corresponding homology groups are isomorphic.

REFERENCES

• 1: Azriel Rosenfeld, Connectivity in Digital Pictures, Journal of the ACM (JACM), v.17 n.1, p.146-160, Jan. 1970 [doi>10.1145/321556.321570]
• 2: SPANIER, E }-IAlgebraic Topology McGraw-Hill, New York, 1966
• 3: GREENBERG, M Lectures ~n Algebrazc Topology W A. Benjamin, Inc, Menlo Park, Cahf, 1967
• 4: J. P. Mylopoulos , T. Pavlidis, On the Topological Properties of Quantized Spaces, II. Connectivity and Order of Connectivity, Journal of the ACM (JACM), v.18 n.2, p.247-254, April 1971 [doi>10.1145/321637.321645]
• 5: HUDSON, J P P P~ecew~se L~ear Topology W A Benjamin, Inc, Menlo Park, Cahf, 1969
• 6: W. T. Beyer, RECOGNITION OF TOPOLOGICAL INVARIANTS BY ITERATIVE ARRAYS, Massachusetts Institute of Technology, Cambridge, MA, 1969
• 7: SEIFERT, H , AND THRELFALL, W Lehrbuch der Topologie Chelsea, Bronx, New York, 1947
• 8: MARKOV, A A Unsolvabflity of the problem of homeomorphlsm Proc Internatmnal Congress of Mathematics, 1958, Cambridge University Press, 1960, pp. 300-306.
• 9: ADYAN, S.I. Dokl. Akad Nauk SSSR I08 (1955), 533-535.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Design, Performance, Theory, Verification