Symbolic Topology in Two and Three Dimensions

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

DMS-0308840 Tibor Beke This is a CARGO incubation award made under solicitation http://www.nsf.gov/pubs/2002/nsf02155/nsf02155.htm. The main motivation of this project is computational cartography. The underlying mathematical observation is that symbolic map layers are isotopy invariants. Transcribing the topological information that resides in a map amounts, in practice, to specifying an isotopy class of nested, labelled planar graphs. The deliverable of this project is a portable specification language for doing that. While the case of two-dimensional planar configurations is essentially solved, its extension to surfaces of higher genus is of interest even as fundamental research. Its importance is also highlighted by its connection to the description of solid bodies, such as those encountered in computer-aided design. Present-day Geographic Information Systems tend to treat maps as superimposed layers of graphic images. But a map also contains information that is topological, meaning, metric-independent. Examples of this are road or other infrastructure networks, where one is only interested in the connectivity between certain nodes, and rough qualitative features of the lines connecting them. The storage, indexing and transmission of this symbolic topological information may be both more important and easier than that of the entire graphical image. The authors outline an algorithm for schematic rendering, and a method of attacking the map isomorphism problem, where by map one may mean both actual images and maps encoded by their proposed scheme. Both of those ideas, however, are in need of experimental verification.