Representing Topological Structures with Degeneracies
Gary Miller, Computer Science Department, Carnegie Mellon University
October 15, 2004

Abstract

The ability to represent and manipulate topological structures on a computer is central to many areas such as computational geometry, computer graphics, solid modeling, and scientific visualization. A classic example is the representation of a graph embedded on a surface. In this case we have three types of objects: vertices, edges, and faces. One of the early representations of graphs on surfaces was given by Edmonds 1960 and Tutte 1973. In the case where none of the faces have pinched boundaries, no degeneracies, Brisson has given a very simple a elegant representation using triples consisting of a vertex, edges, and face called cell-tuples. Brisson showed that cell-tuples generalize to non-degenerate cell partitions of any manifold.

We present a new topological representation of surfaces in higher dimensions, cell-chains, a generalization of the cell-tuples of Brisson. Cell-chains are identical with cell-tuples when there is no degeneracies.

In general it is undecidable to determine if a representation is a manifold. Thus it is undecidable if a given represented topology satisfies the hypothesis of being a manifold. We show that our representation works even for non-manifolds and thus circumvents the decidability problem. We use an axiomatic approach by adding a critical new condition to the n-G-maps of Lienhardt, cell-maps. We show that our cell-maps and cell-chains characterize the same topological structure.

Joint work with David Cardoze Gary Miller Todd Phillips