On visual formalisms.

ON VISUAL FORMALISMS Visualizing information, especially information of complex and intricate nature, has for many years been the subject of considerable work by many people. The information that interests us here is nonquantitative, but rather, of a structural, set-theoretical, and relational nature. This should be contrasted with the kinds of quantitative information discussed at length in [43] and [46]. Consequently, we shall be interested in diagrammatic paradigms that are essentially topological in nature, not geometric, terming them topovisual in the sequel.

Two of the best known topo-visual formalisms have their roots in the work of the famous Swiss mathematician Leonhard Euler (1707-1783). The first, of course, is the formalism of graphs, and the second is the notion of Euler circles, which later evolved into Venn diagrams. Graphs are implicit in Euler's celebrated 1736 paper, in which he solved the problem of the bridges of Konigsberg [12]. (An English translation appears in [3].) Euler circles first appear in letters written by Euler in the early 1760s [13], and were modified to improve their ability to represent logical propositions by John Venn in 1880 [48, 49]. (See [19, chap. 2] for more information.)

A graph, in its most basic form, is simply a set of points, or nodes, connected by edges or arcs. Its role is to represent a (single) set of elements S and some binary relation R on them. The precise meaning of the relation R is part of the application and has little to do with the mathematical properties of the graph itself. Centain restrictions on the relation R yield special classes of graphs that are of particular interest, such as ones that are connected, directed, acyclic, planar, or bipartite. There is no need to elaborate on the use of graphs in computer science--they are used extensively in virtually all branches of the field. The elements represented by the nodes in these applications range from the most concrete (e.g., physical gates in a circuit diagram) to the most abstract (e.g., complexity classes in a classification schema), and the edges have been used to represent almost any conceivable kind of relation, including ones of temporal, causal, functional, or epistemological nature. Obviously, graphs can be modified to support a number of different kinds of nodes and edges, representing different kinds of elements and relationships.

A somewhat less widely used extension of graphis is the formalism of hypergraphs (see, e.g., [1]), though these are also finding applications in computer science, mainly in database theory (see [14], [15], and [31]). A hypergraph is a graph in which the relation being specified is not necessarily binary; in fact, it need not even be of fixed arity. Formally, an edge no longer connects a pair of nodes, but rather a subset thereof. This makes hypergraphs somewhat less amenable to visual representation, but various ways of overcoming this difficulty can be conceived (see Figure 1). In analogy with graphs, several spec ial kinds of hypergraphs are of particular interest, such as directed or acyclic.

It is important to emhasize that the information conveyed by a graph or a hypergraph is nonmetric and captured by the purely topological notion of connectedness (a term taken from [18]); shapes, locations, distances, and sizes, for example, have no significance.

Although not quite as widely used as graphs, Euler circles, or Venn diagrams, are often used to represent logical propositions, color charts, etc. (see Figure 2). The basic idea is to appeal to the two-dimensional case of the Jordan curve theorem (e.g., [11, 30]), which establishes that simple closed curves partition the plane into disjoint inside and outside regions. A set is then represented by the inside of such a curve, giving the topological notions of enclosure, exclusion, and intersection of the curves their obvious set-theoretic meanings: being a subset of, being disjoit from, and having a nonempty intersection with, respectively.

The bottom line is that, whereas graphs and hypergraphs are a nice way of representing a set of elements together with some special relation(s) on them, Euler/Venn diagrams are a nice way of representing a collection of sets, together with some structural (i.e., set-theoretical) relationships between them. The difference between the two types of relationships is obvious. The structural ones are uniformly interpreted in the obvious set-theoretic fashion, in much the same way as the = symbol in logical formalisms is uniformly interpreted as the equality predicate, whereas the edge relations of graphs and hypergraphs attain different meanings in different applications.

The main observation motivating the present work is that in numerous computer-related applications the complexity of the objects, systems, or situations under consideration is due in large part to the fact that both capabilities are needed. We have a (usually large) number of sets that are interrelated in nontrivial set-theoretic ways, but they are also related via one or more additional relationships of special nature, depending on the application at hand. Furthermore, among the structural, set-theoretic relationships it is often desirable to identify the Cartesian product of some of the sets--an action that can be crucial in preventing certain kinds of representations from growing exponentially in size. In line with these observations, which will be supported by examples in the sequel, the purpose of this article is to extend and combine Euler's two topo-visual formalisms into a tool suitable for dealing with such cases.

In the next section, we introduce higraphs, first modifying Euler/Venn diagrams somewhat, then extending them to represent the Cartesian product, and finally connecting the resulting curves by edges or hyperedges. (The appendix contains the formal syntax and semantics of simple higraphs.) We will then illustrate the power of the formalism by briefly discussing higraph-based versions of such graphical languages as entity-relationship diagrams, semantic and associative networks, and dataflow diagrams. Later we will detail a less obvious application called statecharts [21], which are essentially a higraph-based version of finite-state machines and their transition diagrams.

HIGRAPHS

Let us start with a simple example of Euler circler (Figure 3). As can be seen, we prefer to use rounded rectangles, or rounded rectilinear shapes (rountangles?), rather tha circles or unrestricted curves, and shall all the areas, or zones, they enclose blobs in the sequel. Second, as the formal definition supplied in the appendix shows, we regad each blob as denoting a certain kind of set, with the nesting of curves denoting set inclusion, not set membership. Thus, Figure 3 can be seen to contain several cases of inclusion, disjointness, and intersection of sets.

For our first real departure from Euler and Venn's treatment, we now require that every set of interest be represented by a unique blob, …