Jordan Graphs
by
Gabor T. Herman
University of Pennsylvania
Coauthors: Ron Aharoni, Martin Loebl

Early development of digital topology concentrated on tessellations of the plane into square-shaped pixels, each one of which had a 1 or a 0 assigned to it. It became quickly apparent that in order to avoid some ``paradoxes'' one needs to consider adjacencies in addition to the one provided by the edge-adjacency. The customary choice became to use a pair of adjacencies; one for the 1-pixels and another one for the 0-pixels. While this approach can be treated in a mathematically rigorous fashion, it nevertheless remains attractive to consider those digital spaces in which a single adjacency suffices to usefully define connectivity. This not only makes the resulting mathematics more elegant, but it also brings the subject nearer to classical graph theory together with its enormous wealth of results. This is what motivated us to search for an appropriate new concept.

Jordan curves have an interior and an exterior which between them contain all the points not on the curve and both of which are connected, but are disconnected from each other. Generalization to surfaces in digital spaces is useful when displaying (only the exterior of a surface is visible from any direction) or analyzing (the interior volume is well-defined). Boundaries in digital spaces may or may not be Jordan, but are ``guaranteed'' to be Jordan in spaces we call strong Jordan graphs.

In this talk we define such a notion of a strong Jordan graph. We also define Jordan graphs as those digital spaces in which finite boundaries are guaranteed to be Jordan, and show that there are Jordan graphs which are not strong Jordan graphs. (Strong) Jordan graphs are characterized by the existence of ``cuts'' in associated graphs, by the acyclic nature of the adjacency graphs of binary pictures and also by the connectedness of the immediate interiors (or exteriors) of certain types of surfaces. The surfaces of the last category include the so-called minimally near-Jordan surfaces, which are shown to be of some interest. Finally, we tie some of these notions to standard notions of graph theory, such as the notion of a separating set.

Our overall conclusion is that those digital spaces which are Jordan graphs have some very desirable properties which make their use advantageous whenever the underlying situation allows us to use them.

Date received: April 12, 1996

Copyright © 1996 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caae-35.