Jordan graphs

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 that provided by the edge-adjacency. The customary choice became the use of a pair of adjacencies; one for the 1-pixels and another 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 sufficies to usefully define connectivity. This not only makes the resulting mathematics more elegant, but it also brings the subject nearer to classical graph theory and 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 paper we define such a notion of a strong Jordan graph. We show that some previously studied classes (such as those of 1-simply connected digital spaces and of bridged graphs) are subclasses of strong Jordan graphs. 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. (C) 1996 Academic Press, Inc.