Computer-based information plays a crucial role in our society. As a result, an important responsibility of a user interface is to make intelligent use of human visual abilities and output media whenever it presents information to the user. For example, a color medium makes it possible to use graphical techniques based on the fact that the human visual system is very effective at distinguishing a small number of distinct colors [13, 23]. A monochrome medium requires other graphical techniques that utilize other capabilities of the human visual system.

Building user interfaces that intelligently present information is a difficult task. At the current time, an application designer is forced to anticipate every presentation situation that might arise in the application and decide which graphical techniques are most effective in each situation. Not only does the application designer have to ``pre-design'' the presentations, but he or she must be a graphic design expert to ensure that the resulting presentations are effective.

An obvious solution is to build a system, called a presentation tool, that automatically designs graphical presentations of information. Using such a system, application designers need not pre-design the presentations, and the graphic design issues are the responsibility of the presentation tool. Figure 1 illustrates how an application designer would use such a tool. The application extracts some information from its database (perhaps using statistical analysis). The presentation tool then synthesizes a graphical design and renders an image that presents this information. A graphical design is an abstract description of an image that indicates the graphical techniques (such as color variation or position on an axis) that are used to encode information.

There are two open problems that must be solved before such a presentation tool can be constructed: graphic design criteria must be codified before the presentation tool can synthesize effective designs, and a wide variation of designs must be generated before the presentation tool can handle a wide variety of input.

This paper describes research that begins to solve these problems by focusing on automating the design of two dimensional (2D) static presentations (such as bar charts, scatter plots, and connected graphs) of relational information. The cornerstone of this research is the development of precise definitions of graphical languages that describe the syntactic and semantic properties of graphical presentations. The framework established by these definitions addresses the two problems mentioned above. Graphic design issues are codified with expressiveness and effectiveness criteria. Expressiveness criteria identify graphical languages that express the desired information. Effectiveness criteria identify which of these graphical languages is the most effective in a given situation at exploiting the capabilities of the output medium and the human visual system. A wide variation of designs are systematically generated using a composition algebra, which is a collection of primitive graphical languages and composition operators that can form complex presentations. This framework is implemented with artificial intelligence techniques. A prototype application-independent presentation tool called APT (A Presentation Tool) has been built. Even though only the basic framework has been implemented, APT can synthesize a wide variation of useful designs.

The paper is a topdown description of the two types of graphic design criteria and the composition algebra mentioned above. Related work is described in section 2. Section 3 uses three examples to motivate the development of the criteria and algebra. Section 4 gives a detailed overview of the results described in this paper. The core of the paper is contained in sections 5, 6, and 7, which describe the details of the expressiveness and effectiveness criteria and the composition algebra. Sections 8 and 9 describe how APT uses these results to synthesize presentations. Finally, section 10 considers how the research can be extended.

The automatic design of graphical presentations of information is a relatively unexplored research area. As a result, the existing work has focused on restricted aspects of the problem. Aside from the early unfocused work, the following three foci categorize the existing work: content issues, graphic design issues, and design variation issues. Content issues are central to systems that automatically determine the content of presentations, such as adding or removing details to generate an effective presentation or developing a sequence of related presentations. The graphic design and design variation issues have already been described. Another useful categorization is the graphical techniques used by the system (2D, 3D, animation).

Two of the early, less focused, pieces of work deserve mention. The first piece of work developed the AIPS system, which was one of the earliest attempts to separate the presentation process from the rest of an application [24]. AIPS used the KLONE representation system to specify and refined a high-level specification of a 2D information display. The second piece of early work studied automatic animation scripting and the rule-based layout of node-link diagrams [12].

Content issues were the primary focus for the work on two systems. The first system is the VIEW system developed by Friedell, which automatically generated 2D icons describing the properties of ships stored in a naval database [10]. A stepwise refinement of icon templates, using subicon templates, terminated when sufficient detail was generated for a given icon size. The templates were designed by hand rather than by the system. The second system is the APEX system developed by Feiner, which automatically generated a sequence of images that describe action in a 3D world consisting of some sonar cabinets [8]. The system carefully tailored the sequence of images to omit irrelevant or redundant details. The graphic design issues surrounding the merging of icons and 3D images were also considered.

Two other pieces of work focused on graphic design issues. The first piece of work is the BHARAT system developed by Gnanamgari, which was an early effort at the automatic generation of 2D presentation graphics [11]. It selected a pie chart, bar chart, or line chart design for a single unary function, which could have multiple numeric ranges. BHARAT was based on a simple design algorithm. When the function was continuous, a line chart design was used. When the user indicated that the range sets could be summed to a meaningful total, a pie chart design was used. Bar chart designs were used in the remaining cases. Although multiple designs were generated, BHARAT's range of designs was limited. It could not present a collection of relations or non-functional relations. Gnanamgari's discussion focused on graphic design issues. However, her effectiveness criteria about issues such as font and color choice were ``wired'' into the code that rendered the design, making it difficult to extend the system to a broader range of input.

The second piece of work that focused on graphic design issues is Beach's system that automated the low-level layout and design of 2D tables whose high-level topology was specified by the user as a matrix of rows and columns [2]. This research utilized a specification called a graphical style [1], which allowed the explicit description of the graphic design properties of the table, such as line widths, background tints, and size constraints. As a result, the user could control parts of the design while the remainder was controlled by the existing default style. Explicit graphical styles made it possible for the system to format the table in different ways for different output media. Although the graphical styles had to be specified by hand, care was taken to make sure that graphic design issues could be addressed in the specification.

Design variation and graphic design are the primary foci of the work described in this paper. This work differs from the previous work in that it focuses directly on the generation of a comprehensive variation of designs for 2D static presentations of relational information. The APT system uses artificial intelligence techniques to implement a ``generate and test'' search for a design: the composition algebra generates design alternatives and the graphic design criteria test the generated alternatives.

The graphical presentation problem is to synthesize a graphical design that expresses a set of relations and their structural properties effectively. This problem is illustrated in this section with three examples that describe the desired behavior of a presentation tool. These examples describe the basic concerns that led to the criteria and algebra described in the remainder of the paper.

Given the process model in Figure 1, the examples of presentation tool behavior begin with the application's database. Figure 2 describes a collection of relation tuples about automobiles that might be contained in such a database. The structural properties of these relations, which might be in the database schema, are shown in Figure 3 using standard database notation [22]. Structural properties include the domain sets and their functional relationships. Given such a database, a typical input from the application to the presentation tool would be the following:

The following three price/mileage examples illustrate the expressiveness, effectiveness, and design variation concerns mentioned above. The scatter plot in Figure 5 illustrates the importance of the expressiveness concern. If the application had not requested that the details about the cars could be omitted, the scatter plot in Figure 5 would not express all the input. Without this request, the scatter plot would have had to include labels as shown in Figure 6.

The following rough estimate indicates that there are many possible inputs to a presentation tool. The price/mileage input consists of two binary relations that share the same first domain set and are functional dependencies from a qualitative domain to a numeric range. The structural properties of the input relations are important factors for designing a graphical presentation. Different structural properties require the presentation tool to synthesize different designs. Furthermore, the ability to vary these properties independently leads to a combinatorial explosion in the number of inputs that might be given to a presentation tool. To see this, abstract the two binary relations by ignoring the functional dependencies, the sharing of domain sets, and the properties of the domain sets:

The preceding formula indicates that there can be many inputs to the presentation tool. For two binary relations, there are over seventeen thousand possibilities. However, the input can include more relations or relations with more domain sets. For example, four binary relations similar to the automobile data presented in Figure 30 can generate over 21 billion different inputs. Furthermore, this estimate does not include other factors that increase the number of designs that must be generated by a presentation tool, such as application requests or properties of the output media.

An expressiveness criterion, which is derived from a precise language definition, is associated with each graphical language. A graphical language can be used to present some information when it includes a graphical sentence that expresses exactly the input information: that is, all the information and only the information. Expressing additional information is potentially dangerous, because it may not be correct.

Effectiveness criteria can be based on a number of different factors. For example, a design can be judged to be effective when it can be interpreted accurately or quickly, when it has visual impact, or when it can be rendered in a cost-effective manner. This paper concentrates on generating designs that can be accurately interpreted. Dealing with multiple, perhaps conflicting, effectiveness criteria is beyond the scope of this research.

Given the focus on accuracy, effectiveness criteria are based on the observation that a graphical language uses specific graphical techniques to encode information. When interpreting a graphical sentence, a person is confronted with perceptual tasks that correspond to these graphical encoding techniques. Since some perceptual tasks are accomplished more accurately than others, effectiveness criteria can be based on the comparison of the perceptual tasks required by alternative graphical languages.

Since most graphical presentations of relational information are based on a general vocabulary of graphical techniques, a wide variation of designs can be generated with a composition algebra that describes this graphical vocabulary. Figure 8 summarizes graphic designer Jacques Bertin's vocabulary of the graphical techniques commonly used to encode information in presentation graphics [3].

Graphical presentations use graphical marks, such as points, lines, and areas, to encode information via their positional, temporal, and ``retinal'' properties.2 The composition algebra consists of a basis set that contains primitive graphical languages each of which embodies one of Bertin's graphical techniques for encoding information and composition operators that are able to generate a wide range of presentations by composing the primitive languages.

All communication is based on the fact that the participants share conventions that determine how messages are constructed and interpreted. For graphical communication these conventions indicate how arrangements of graphical objects encode information. This section shows how to formalize these conventions by taking the view that graphical presentations are actually sentences of graphical languages that have precise syntactic and semantic definitions. Such definitions make it possible to determine the expressiveness and effectiveness properties of graphical languages.

Intuitively, a set of facts is expressible in a language if there is a sentence of the language that encodes every fact in the set. The difficulty with this intuition is that the sentence may encode additional incorrect facts (this is discussed in detail elsewhere [17]. Therefore, the expressiveness criteria for languages contain two conditions:

A set of facts is expressible in a language if it contains a sentence that:

This section presents two examples that demonstrate the importance of these two conditions. The first example shows a case where position on an axis cannot express a one-to-many relation. The second example shows a case where a bar chart expresses additional incorrect facts. Before the examples can be given, however, it is necessary to develop some formal machinery for defining the syntax and semantics of graphical languages. Such machinery makes it possible to determine what information is encoded by the sentences of a language. Evaluating expressiveness requires this ability.

The formal machinery required to define a graphical language is fairly straightforward. A graphical sentence s is defined to be a collection of tuples:

More formally, a graphical sentence s is a legal sentence of the horizontal position language when it consists of the union of a horizontal axis set h and a set of marks m such that each located object <o,l> in m is a plus object plusobj located at a constant height const above the axis:

Given a precise syntactic definition, the semantics of a graphical language can be specified using established formal techniques such as denotational semantics [7]. A collection of located objects representing a graphical sentence can have a denotation in the same way as a collection of characters representing a logic formula. However, a presentation tool designs graphical sentences. It must be able to describe the semantic relationships between a graphical sentence and the encoded facts. For example, the HorzPos language encodes a binary relation with an axis, a set of marks, and the position of the marks on the axis. Formally, a relation called Encodes(s, facts, lang) is used to describe the semantic relationship between the objects and properties of a graphical sentence s and the set of facts that are encoded given the semantic conventions of the language lang.5 For example, given a relation r consisting of tuples r(ai, bi), the following is a formal description of the three basic Encodes relationships for a sentence of the HorzPos language (see Figure 10 for an abstract description of these encodes relations). The axis h encodes the second domain of the relation, Dom2(r):

Given the semantics for the objects in a graphical sentence, it is straightforward to describe the semantics for arrangements of objects. For the HorzPos language, the position of marks on the axis encodes the tuples of the r relation. That is, the first domain value ai of a tuple r(ai, bi) corresponds to a mark oi as described in (2) and the second domain value bi corresponds to the position of the mark oi on the axis h, which is described with the binary function Position(oi, h). More formally, there exist two constants, scale and offset, that equate the domain value bi with the axis position of the mark oi for the domain value ai:

The formal machinery for describing the syntax and semantics of a graphical language leads to a precise statement of expressiveness:

The first example, which focuses on expressing all the facts, is based on the HorzPos language. It turns out that it is possible to prove that one-to-many relations cannot be expressed in the HorzPos language:

Although the previous theorem is not particularly deep, it illustrates the importance of precise definitions of the graphical conventions used to design and interpret information presentations. Not only do precise definitions make theorems possible, but they make it clear which conventions are being used. Different conventions lead to different theorems. For example, the HorzPos language is based on the convention that the marks are uniquely paired with the domain values of the first domain set. Occasionally, graphical presentations use a different convention, which is to pair marks with the tuples rather than the domain values of the first domain set. Given such a convention, the previous theorem is no longer valid because r(ai, bj) and r(ai, bk) can be encoded by the positions of different marks. However, this alternative convention is not as common as the HorzPos convention because it is natural to assume that marks are associated with domain values. For example, it is natural to assume that each mark in Figure 9 represents a unique car.

A second example, which focuses on the second expressiveness condition, illustrates the fact that some graphical languages encode additional information in the geometric relationships of the objects in a graphical sentence. Consider the bar chart diagram of the Nation relation in Figure 11. Most people perceive the lengths of the bars as an encoding of an ordered or quantitative set. That is, given domain tuples r(ai, bi) and r(aj, bj) and the corresponding bar objects bari and barj, an ordering relationship among the bars lengths encodes an ordering relation among the domain values bi and bj:

The plot chart of the Nation relation in Figure 12, which is an alternative design for encoding the Nation relation that avoids the bar length problem, also illustrates the importance of precise language definitions. Sometimes, people use the convention that the sequence of labels on an axis indicates an ordered domain set, which would ruin the expressiveness of the scatter plot design for Figure 12. However, the standard convention is to ignore this sequencing encoding. After all, when the second domain set is ordered, a bar chart can be used. This means that the precise definition for a plot chart language should not include an Encodes predicate for the ordering of the second domain set. Therefore, the plot chart in Figure 12 does not encode additional incorrect facts.6

Given two graphical languages that express some information, the obvious question is which language involves a design that specifies the more effective presentation. For example, Figure 13 expresses the same price/mileage input as the scatter plot in Figure 5, but the prices are encoded with the area of the marks rather than their position on a vertical axis. Which presentation is more effective?

Unlike expressiveness, which only depends on the syntax and semantics of the graphical language, effectiveness also depends on the capabilities of the perceiver. The difficulty is that there does not yet exist an empirically verified theory of human perceptual capabilities that can be used to prove theorems about the effectiveness of graphical languages. Therefore, one must conjecture a theory of effectiveness that is both intuitively motivated and consistent with current empirically verified knowledge about human perceptual capabilities. This section describes such a conjectural theory.

The core of this conjectural theory is an observation, made by Cleveland and McGill, that people accomplish the perceptual tasks associated with the interpretation of graphical presentations with different degrees of accuracy [6]. Cleveland and McGill focused on the presentation of quantitative information. They identified and ranked the tasks shown in Figure 14. Higher tasks are accomplished more accurately than lower tasks. Furthermore, they have some experimental evidence that supports the basic properties of this ranking.

Although the ranking in Figure 14 can be used to compare alternative graphical languages that encode quantitative information, it does not address the encoding of non-quantitative information, which involves additional perceptual tasks and different task rankings. For example, texture is not mentioned in Figure 14, and color, which is at the bottom of the quantitative ranking, is a very effective way of encoding nominal sets [23]. Therefore, it was necessary to extend Cleveland and McGill's ranking as shown in Figure 15. Although this extension was developed using existing psycho-physical results and various analyses of the different perceptual tasks, it has not been empirically verified [16].

An example analysis for area perception is shown in Figure 16. The top line shows that a series of decreasing areas can be used to encode a tenfold quantitative range. Of course, in a real diagram such as Figure 13, the areas would be laid out randomly making it more difficult to accurately judge the relative sizes of different areas (hence, area is ranked fifth in Figure 14). Nevertheless, small misjudgements about the size of an area only leads to small misperceptions about the corresponding quantitative value that is encoded. The middle line shows that area can encode three ordinal values. However, one must be careful to make sure that ordinal areas are different enough that they are not confused with each other. This is indicated by the fact that only three days of the week are encoded. If more days of the week were encoded, the ``step size'' between Tuesday's area and Monday's area would get small enough that people would start to confuse them, which is quite different from confusing two quantitative values that are almost equal. The bottom line shows that area can encode three nominal values. Besides the fact that stepping is also required for nominal information, this case illustrates the additional problem that people often perceive area as an encoding of ordinal information. This analysis indicates that area should have a moderate quantitative ranking and a low non-quantitative rankings.

The ranking in Figure 15 can often be used to determine the relative effectiveness of different graphical languages. For example, Figure 17 compares the scatter plot and position/area designs for the price/mileage input. Since position has a higher ranking than area for quantitative data, it is clear that the scatter plot is a more effective design.

The ranking in Figure 15, however, does not specify a total ordering on the effectiveness of graphical languages. For example, Figure 18 compares two encodings of the Price, Mileage, and Weight relations. Both designs are scatter plots with information also encoded in the area of the marks. Since both designs require the same perceptual tasks, the ranking in Figure 15 does not indicate which design is more effective. The ranking can be extended to generate a lexicographic ordering with the following principle:

Expressiveness and effectiveness criteria, which were described in the previous two sections, are not very useful without a method for generating alternative designs. The naive approach is simply to develop an ad hoc list of graphical languages that can be filtered with the expressiveness criteria and ordered with the effectiveness criteria for each input. The major difficulty with this approach is that there is no guarantee that there will exist appropriate designs for a wide variety of presentation situations. A minor difficulty is that the entire list must always be considered, even when only a few alternatives are suitable for a given input. This section describes an alternative approach based on the idea of a composition algebra. Such an algebra consists of a basis set containing primitive graphical languages and some composition operators that can generate composite designs. A specific choice of basis set and composition operators are described that generate many of the designs commonly found in presentation graphics [3,4,5,15,19,21]. The study of alternative composition algebras is an open area of research.

The idea of a composition algebra occurred to me when I looked at a diagram that was very similar in design to the diagram in Figure 19. The design used in Figure 19 combines two encoding techniques that are generally not seen together. First, the prerequisites among computer science classes are encoded with links that connect nodes that encode the classes. Second, a class schedule is encoded by the position of the nodes on a vertical axis. This diagram is an example of a composite design. The primitive languages used to form this composite design are a node/link language (see Figure 20) and a vertical axis language (see Figure 21). Given this unusual example of a composite design, I realized that many presentations could be describe as compositions of a set of primitive languages.

The theoretical results described in the previous three sections have been combined in a synthesis algorithm that generates designs in order of the effectiveness criteria described above. The synthesis algorithm has been implemented in APT, which consists of a design component followed by a rendering component (see Figure 1). The design component uses logic programming techniques to implement the synthesis algorithm. The rendering component uses object-oriented programming techniques and a device-independent graphics package to render the resulting designs. The rendering component, which was not the focus of this research, places an implementation restriction on the set of primitive languages in Figure 22 that can be used by APT to generate presentations. As of this writing, the following primitive languages remain unimplemented: orientation, texture, line charts, maps, and miscellaneous. Even with these restrictions, the prototype can generate a wide range of useful presentations. The diagrams in this paper with ``apt'' in the lower right corner are examples of APT's output.

APT's synthesis algorithm is based on a divide-and-conquer search strategy. The algorithm has three steps: partition, selection, and composition. These steps, which are described below, involve choices. When a particular set of choices does not lead to a composite design, backtracking is used to consider other choices. APT uses depth-first search with simple backtracking.

The synthesis algorithm involves choices that might not lead to a design, which means that backtracking will occur. When backtracking occurs, the next most effective primitive design or composition operator is chosen until a design is found for all the information. For example, given a request to omit the details about the cars, APT processes the automobile input shown above as follows. The partitioning step generates a partition for the Price relation and a partition for the Mileage relation. The first selection choice is the vertical axis primitive language for both these partitions (because the relations have the same structure.) However, the composition step fails to compose the resulting designs because mark composition, which is the only applicable operator, cannot merge marks that have two different positions on an axis. This failure triggers backtracking. The next most effective choice for the Mileage partition is the horizontal axis primitive language. Mark composition succeeds for this choice and the search proceeds to deal with the remaining relations in the input. Given an indication from the application that the output medium includes color, the resulting design for the four automobile relations is the scatter plot rendered in Figure 30.

The logic program implementing the synthesis algorithm is based on a depth-first9 backward chaining version of a deductive algorithm called Residue [9]. Residue is useful for design problems because predicates describing the design can be declared to be assumable. During a deduction, an assumable predicate can be assumed to be true to make the deduction proceed. At the end of the deduction, all assumed predicates are returned as conditions that must be satisfied. For design problems, these conditions are exactly the design constraints. For example, Figure 29 describes APT's bar chart rule. The assumables are the Encodes relations of the bar chart primitive language. When these predicates are assumed, they can be used to compose this design with others and to render the final image.

APT was developed on a Symbolics Lisp Machine using MRS, a representation and logic programming system [18]. APT is a functional prototype and no effort has been made to make it efficient, although designs are typically generated in 1-2 minutes and images are rendered in less than a minute. The logic program is about 200 rules, and the rendering system is about 60 pages of Lisp code.

APT demonstrates that a synthesis algorithm based on composition can be used to automatically generate effective designs that can express a wide variety of input. Although inefficient, the deductive search strategy used in APT has a number of advantages that recommend it over more procedural approaches. APT can be sensitive to many factors while generating designs. The next section describes how APT is sensitive to the output medium. APT is also sensitive to requests from the application. An application can indicate that a particular primitive language should be used even when it contradicts the effectiveness ranking that APT would normally use. This makes it possible for an application to tailor a presentation to fit the profile of a particular user. Another advantage of the logic programming approach is that it is flexible. The range of designs that can be generated by APT can be modified by changing the rules associated with the primitive languages and the composition operators. The search order can also be modified by changing the expressiveness and effectiveness criteria. This is important because presentation graphics and human perceptual abilities are not yet well understood. As our understanding advances, modifications can be made to APT that will enable it to generate even more effective designs.

Because the synthesis algorithm searches for designs, it can be sensitive to the capabilities of the output medium. For example, when the application indicates that the output medium includes color, APT designs the scatter plot shown in Figure 30 for the automobile input, which is the mark composition of two single position designs and two retinal list designs. When the application restricts APT to a monochrome medium, APT designs the aligned bar chart shown in Figure 31, which is the single axis composition of four bar chart designs.10 Given a color medium, the Repair relation can be encoded by the color list primitive language. However, given a monochrome medium, the only available retinal list primitive languages for ordinal information are texture, saturation, and size (see Figure 25). The texture primitive language was rejected because the rendering portion of APT does not implement texture. The saturation primitive language was rejected by its effectiveness criterion because five levels of gray blend together, making the repair values blend together. The size primitive language can be selected. However, the scatter plot design requires that size must also be used for one of the other relations in the input and mark composition cannot merge two designs that use size to encode different domain sets. APT ultimately settles on the aligned bar chart shown in Figure 31.

The research described in this paper sets the framework for the development of presentation tools that can automatically design effective graphical presentations for a wide variety of information. The formalization of graphical presentation as a collection of graphical languages makes it possible to develop expressiveness and effectiveness criteria and a composition algebra. This formalization provides the basis of a logic program that designs presentations automatically. The prototype implementation called APT demonstrates the feasibility of this approach.

Many problems associated with the automatic generation of graphical designs remain to be solved. The engineering of robust presentation tools will raise many questions about the correct search criteria. Animation and 3D presentation appear to be very powerful techniques for presenting symbolic information and should be incorporated into future tools. Larger search spaces, which can be generated with finer grained sets of primitive languages, make it more difficult to search for an appropriate choice in real time. However, it may be possible to build a discovery system that searches this larger space for unusual but effective designs. These designs can then be cached along with the primitive languages described in this paper to form a small but comprehensive search space.

This research on intelligent presentation applies artificial intelligence techniques to part of the user interface design problem, that of choosing an appropriate graphical presentation of relational data. Graphic design issues are an important concern of user interface design. This presentation research incorporates a formalized body of graphic design knowledge. Future work with these techniques can address other aspects of User Interface Management Systems, perhaps choosing or adapting the dialogue specifications appropriate to the observed skill level of the user. When research develops theoretical results from a careful analysis of user interface systems, such as the graphic design criteria and composition algebra described in this paper, artificial intelligence techniques can be used to develop an intelligent user interface.

I would like to thank the following people: Polle Zellweger for her inspired suggestions that improved every draft of this paper, Rick Beach for his constructive suggestions just before the submission deadline, Matt Ginsberg and Eric Bier for their helpful suggestions on early drafts, and Michael Genesereth, my advisor, for his encouragement and suggestions throughout the research. The suggestions of the referees are also appreciated.