Diagrams 2000

Diagrams 2000 Programme - Presentation Abstracts

Updating abstracts: These abstracts were submitted by authors in advance of the full paper. In some cases, the paper presented at Diagrams 2000 and published in the proceedings may differ from the abstract on this page. If authors wish to update details on this page, please copy the relevant section of the HTML source into a plain text email message, make the required alterations, and email to alan.blackwell@cl.cam.ac.uk. You may also wish to update the entry on the programme page.


Representations to mediate geospatial collaborative reasoning: A cognitive-semiotic perspective

Alan M. MacEachren
GeoVISTA Center (www.geovista.psu.edu),
Department of Geography
Penn State University
USA (alan@geog.psu.edu)

This presentation will address the representation of geospatial information in the context of group work. The focus is on visual representations that mediate between human collaborators who are participating in a joint reasoning process, within a place and/or space-based problem context. The perspective developed for addressing the challenges involved builds upon the cognitive-semiotic approach outlined in How Maps Work, extending it to consider the issues that underlie creation of maps and related diagrams that work in a group work context. This context requires representations that depict not only geospatial information but also individual perspectives on that information, the process of negotiation among those perspectives, and the behaviors (work) of individuals participating in that negotiation.


Treatment of Diagrams in Document Image Analysis

Dorothea Blostein, Edward Lank, Richard Zanibbi
Department of Computing and Information Science
Queen's University
Kingston, Ontario
Canada K7L 3N6

Document image analysis converts documents from paper form to an electronic form that captures the information content of the document. Necessary processing includes recognition of document layout (to determine reading order, and to distinguish text from diagrams), recognition of text (known as OCR, Optical Character Recognition), and processing of diagrams and photographs.

This paper provides an overview of diagram recognition, which has been an active research area for several decades. Challenging problems in diagram recognition include (1) the great diversity of diagram types, (2)the difficulty of adequately describing the syntax and semantics of diagram notations, and (3) the need to handle noise and uncertainty. Recognition techniques that are surveyed include blackboard systems, stochastic grammars, Hidden Markov Models, and graph grammars.

Universal Arrow Foundations for Visual Modeling

Zinovy Diskin, Boris Kadish, Frank Piessens & Michael Johnson

The goal of the paper is to explicate some common formal logic underlying various notational systems used in visual modeling. The idea is to treat the notational diversity as the diversity of visualizations of the same basic specificational format. It is argued that the task can be well approached in the arrow-diagram logic framework where specifications are directed graphs carrying a structure of diagram predicates and operations.

How People Extract Information from Graphs: Evidence from a Sentence-Graph Verification Paradigm

Aidan Feeney, Ala K.W. Hola, Simon P. Liversedge, John M. Findlay and Robert Metcalf
Department of Psychology
University of Durham
Science Laboratories, South Road
Durham DH1 3LE,
United Kingdom

Graph comprehension is constrained by the goals of the cognitive system that processes the graph and by the context in which the graph appears. In this paper we report the results of a study using a sentence-graph verification paradigm. We recorded participants' reaction times to indicate whether the information contained in a simple bar graph matched a written description of the graph. Aside from the consistency of visual and verbal information, we manipulated whether the graph was ascending or descending, the relational term in the verbal description, and the labels of the bars of the graph. Our results showed that the biggest source of variance in people's reaction times is whether the order in which the referents appear in the graph is the same as the order in which they appear in the sentence. The implications of this finding for contemporary theories of graph comprehension are discussed.

Diagrammatic Acquisition of Functional Knowledge for Product Configuration Systems with the Unified Modeling Language

Alexander Felfernig,
Markus Zanker
Universität Klagenfurt
A-9020 Klagenfurt, Austria

Shorter product cycles, lower prices of products, and the production of goods that are tailored to the customers made knowledge-based product configuration systems a great success of AI technology. However these knowledge bases tend to become large and complex. Therefor, knowledge acquisition and maintenance are crucial phases in the life-cycle of a configurator. We will show how we can meet this challenge by extending a standard design language from the area of Software Engineering with classical description concepts for expressing configuration knowledge. We automatically translate this graphical depiction into logical sentences which can be exploited by a general inference engine in order to solve the configuration task. In order to overcome usability restrictions of diagrammatic notations for large applications, we introduce the usage of contextual diagrams, views and a packaging mechanism. These mechanisms make the conceptual model more readable and understandable and support intuitively the acquisition of configuration knowledge.

MetaBuilder: The diagrammer's diagrammer

R.I. Ferguson, A. Hunter and C. Hardy
School of Computing, Engineering and Technology
University of Sunderland

A software tool named MetaBuilder is described. MetaBuilder's purpose is to enable the rapid creation of computerised diagram editing tools for structured diagrammatic notations. At its heart is an object-oriented, graphical meta-modelling technique - a diagrammatic notation for describing other diagrammatic notations. The notation is based upon the concept of a mathematical graph consisting of nodes and edges. Construction of a "target tool" proceeds by drawing a meta-model of the target notation. Items in the target notation are modelled as "node objects" and the "rules" of the target notation such as connectivity between elements are expressed as edges between the node objects. The actual appearance of symbols in the target notation can be entered using a built in graphical editor. Nodes can have "actions" associated with them which allows different computational behaviour to be assigned to different nodes. Typically this is used to allow textual reports to be generated from a diagram. Once the meta-model is complete, the new tool can be generated automatically. Thus the time to develop such notation specific drawing tools can be dramatically reduced. As the design of a piece of software can be expressed diagrammatically, the MetaBuilder software can be used to build itself! MetaBuilder has its origins in the field of software engineering where it is used to generate diagrammatic notation editors for CASE tools. In such an application, automated reasoning based on the semantics of the target notation can be used to provide automated aid to the process of diagram construction.

The Use of Intermediate Graphical Constructions in Problem Solving with Dynamic, Pixel-level Diagrams

George Furnas, Yan Qu, Sanjeev Shrivastava, and Gregory Peters
School of Information
University of Michigan

Many diagrams can be thought of as graphical representations used to support the solution of problems. Classically, the shapes involved are objects of analytic geometry, like lines, circles, or polygons, and human arranges and interprets them to do the problem solving. The work presented here, based on the Bitpict-2 system, differs in several respects. First the forms involved are arbitrary pixellated shapes, often with no simple sentential characterization, and the problem solving is done directly with those pixel representations by the computer.

This paper focuses on illustrating how this type of diagrammatic computation often makes use of intermediate graphical constructions. On the one hand they are analogous to the static constructions used for alignment in engineering drawing, or in the constructions of classical geometry (e.g., drawing two arcs to bisect a line). On the other hand they are also like intermediate dynamic data structures use in familiar sentential computation. That is to say, they are directly spatial in character, but dynamic and essential to the sophisticated calculation of non-trivial problems. Several examples are used to illustrate how,the graphical substrate itself is used in a central way in the spatial computation process.

Positive Semantics of Projections in Venn-Euler Diagrams Diagrams

Joseph (Yossi) Gil, John Howse and Elena Tulchinsky

Venn diagrams and Euler circles have long been used as means of expressing relationship among sets using visual metaphors such as disjointness and containment of topological contours. Although the presentation is effective in delivering a clear visual modeling of set theoretical relationship, it does not scale very well. The topology of Venn diagrams of four curves or more makes it impractical for visualization. In this work we consider "projection contours", a new means for presenting sets intersections, and study various approach for giving these precise semantics. Informally, a projected contour is a contour describes a set of elements limited to a certain context. The difficulty in introducing the projections notation is giving precise semantics to cases where a diagram comprises more than one projection, and when several projections interact. In particular, we study a semantics by which the meaning of every projections is given by the list of contours with which it interacts, where the contours which are disjoint to it do not change its semantics. The solution is given by an efficient algorithm for solving set equations. We then compare this semantics with the previous attempt of giving non-monotone semantics for projections.

Diagrammatic Control of Diagrammatic Structure Generation

Stefan Gruner & Murat Kurt

Labelled Graphs are a subclass of the class of all diagrams which are widely used in various disciplines of computer science and electical engineering. For example, ER-diagrams (for database schema design), SA-diagrams and class diagrams (for software engineering), semantic networks (in artificial intelligence), or electronic cirquit maps can sensibly be viewed as labelled graphs. In consequence, graph grammars have been developed as powerful and intuitive means for the generation and manipulation of such labelled graphs. Unfortunately, however, the operations of graph grammars are local and non-deterministic in principle so that not all the desired diagram manipulation tasks can be fullfilled by graph grammars in adequate manner. Thus, additional concepts of control are required. While textual control structures for the application of graph grammars are well-known already, more intuitive diagrammatic control mechanisms are still missing. We use a combination of the UML Activity Diagrams and the older Janov Schemas for this purpose. Our main contribution is an already implemented and tested editor which the user can use to build up these diagrammatic control structures for the execution of graph grammar derivations. Moreover, our control diagrams are interpreted and animated by colors such that the the user can observe a graph grammar program run along the specified control diagram.

On the Completeness and Expressiveness of Spider Diagram Systems

John Howse, Fernando Molina and John Taylor
University of Brighton, UK

Spider diagram systems provide a visual language that extends the popular and intuitive Venn diagrams and Euler circles. Designed to complement object-oriented modelling notations in the specification of large software systems they can be used to reason diagrammatically about sets, their cardinalities and their relationships with other sets. A set of reasoning rules for a spider diagram system is shown to be sound and complete. We discuss the extension of this result to diagrammatically richer notations and also consider their expressiveness. Finally we show that for a rich enough complete system we can express the negation of any diagram.

Restricted Focus Viewer: A Tool for Tracking Visual Attention

Alan F. Blackwell, Anthony R. Jansen and Kim Marriott
School of Computer Science and Software Engineering
Monash University, Clayton, Victoria, 3800
Computer Laboratory
Cambridge University.

Eye-tracking equipment has proven useful in examining the cognitive processes people use when understanding and reasoning with diagrams. However, eye-tracking has several drawbacks: accurate eye-tracking equipment is expensive,often awkward for participants, requires frequent re-calibration and the data can be difficult to interpret. We introduce an alternative tool for diagram research: the Restricted Focus Viewer (RFV). This is a computer program which takes an image, blurs it and displays it on a computer monitor, allowing the participant to see only a small region of the image in focus at any time. The region in focus can be moved using the computer mouse. The RFV records what the participant is focussing on at any point in time. It is cheap, non-intrusive, does not require calibration and provides accurate data about which region is being focussed upon. We describe this tool, and also provide an experimental comparison with eye-tracking. We show that the RFV gives similar results to those obtained by Hegarty (1992) when using eye-tracking equipment to investigate reasoning about mechanical diagrams.

Playing With Diagrams

Robert K. Lindsay
University of Michigan
205 Zina Pitcher Place
Ann Arbor, Michigan USA

This paper extends previous work in which I developed a programmed model of reasoning with diagrams in which representations of diagrams were first class computational objects. The system reasons about geometric propositions by manipulating these representations and noticing newly emerged facts that are construed as inferences. Although propositional reasoning is also essential for understanding geometric propositions, and was implemented in limited form as well, diagrammatic manipulation is the cental method of the system. The system has been explored as a means of verifying diagrammatic demonstrations of classical geometric propositions and for generating demonstrations of conclusions supplied for the system. The process of discovering propositions to be demonstrated is a more difficult task. This paper argues that central to the discovery process is systematic manipulation of diagrams – playing – and observing consistent relations among features of the diagram as manipulations are made and observed. The play results in the creation of an "episode" of diagram behaviors which is examined for regularities from which a general proposition might be proposed. The paper illustrates this process and discusses the advantages and limitations of this system and of other computational models of diagrammatic reasoning.

Evaluating the Intelligibility of Diagrammatic Languages used in the Specification of Software.

Carol Britton, Sara Jones, Maria Kutar, Martin Loomes and Brian Robinson.
Department of Computer Science
University of Hertfordshire
Hatfield, Herts. UK

Successful development of interactive software systems requires effective communication between developers and users of the system. In order to achieve this, all stakeholders must be able to understand representations of key concepts produced by the developers. Users are often unfamiliar with the languages used to specify software and hence have difficulty in participating in a meaningful way in this aspect of the development process.

In this paper we focus on how languages used to specify software contributeto the ease of understanding of representations. Research suggests that languages can be assessed in terms of properties that influence the intelligibility of representations produced using the languages. The paper describes the properties identified and highlights three in particular that have been shown to influence the intelligibility of representations. The three properties are:
· motivation of symbols in the language;
· the extent to which the language allows exploitation of human visual perception;
· the amount of structure inherent in the language.

The paper provides evidence that the first two of these properties are not present to any great extent in diagrammatic languages used in software specification. We suggest that more attention should be paid into ways in which these languages can exploit the third property: the amount of structure inherent in the language.

Non-standard Logics for Diagram Interpretation

K. Marriott and
B. Meyer
School of Computer Science and Software Engineering
Monash University
Clayton, Victoria 3168

A key component of computational diagrammatic reasoning is the automated interpretation of diagram notations. Currently, most aproaches to this are based on attributed multiset grammars. Their disadvantage is that grammars do not allow ready integration of semantic information and that the underlying theory is not strongly developed. Therefore, embeddings of grammars into first-order logic have been investigated. Unfortunately, these are unsatisfactory: either they are complex and unnatural or else, because of the monotonicity of first-order logic, cannot handle diagrammatic reasoning completely. We investigate the use two non-standard logics, naemly situation theory and linear logic, for the formalization and computational implementation of diagrammatic reasoning.

The unique advantage of linear logic is that it is a resource-oriented logic, which renders the embedding of grammars straight-forward. Situatiuon theory, on the other hand, has been designed for capturing the semantics of natural language and offers much more powerful methods for modelling complex aspects of language, such as focus of attention. We argue that a combination of linear logic with situation theory will provide an expressive and powerful formalism for diagram understanding. The paper demonstrates embeddings of grammar-based interpretation into both formalisms and discusses their integration.

Communicating Dynamic Behaviors: Are Interactive Multimedia Presentations Better Than Static Mixed-Mode Presentations?

N. H. Narayanan & M. Hegarty

Mixed-mode representations comprising verbal explanations illustrated with diagrams have long been used to communicate information. With the advent of multimedia, such representations have become interactive and dynamic, and have migrated from paper to the computer. The conventional wisdom is that computer-based multimedia is better than paper-based representations. However, the question of whether the communicative power of mixed-mode representations stem from their careful design to match cognitive processes involved in comprehension, such as mental animation, or from their interactive and animated nature, has never been investigated. This is an important issue since, if effectiveness of external representations mainly arises from their match with comprehension processes, paper-based representations should perform as well as computer-based ones. On the other hand, if interactivity and explicit animation significantly increase comprehension, computer-based multimedia should outperform paper-based verbal and visual explanations.

This paper first presents a cognitive model of comprehending information from mixed-mode representations. We describe how this model generates design guidelines for mixed-mode representations to present expository material on two domains - the concrete domain of simple mechanical systems and the abstract domain of computer algorithms. We then report on a series of studies that compared interactive multimedia representations and their paper-based counterparts, both designed in accordance with the comprehension model, against each other and against competing representational forms such as books, CD-ROMs and animations. Results of these studies indicate that the effectiveness of textual and diagrammatic representations has more to do with their match with comprehension processes than the medium of presentation. In other words, benefits of interactivity and animation may be being overstated and oversold in this current milieu of fascination with multimedia and the web.

Recording the Future: Some Diagrammatic Aspects of Time Management

Stuart Clink & Julian Newman
Department of Computing
Glasgow Caledonian University,
Glasgow G4 0BA, UK

Management of time and commitments is a central problem for high-discretion employees in the information society. A variety of conventions have evolved for the representation of time in calendars, diaries, and project management packages. Yet current time management products remain very close to paper-based conventions with respect to their support for visualisation of scheduling problems; indeed their displays may be even more restrictive than the paper diary. We report an exploratory study aiming at "thinking outside the box" of current computerised diaries by an empirical investigation in which a heterogeneous sample of white-collar workers generated diagrammatical representations of their time and commitments. Design issues are raised for diagrammatic representations that can empower the user in such an environment.

Differentiating Diagrams: A New Approach

Jesse Norman
University College London

Philosophers, scientists and practitioners commonly distinguish between descriptions, depictions, and diagrams. But how exactly are we to understand the differences between these representational types? Many suggestions have been made, in terms which reflect widely differing goals, methods, background disciplines and governing assumptions. There has been little, if any, consensus. These approaches are, however, united by a common assumption: that the various types must be classified in terms of a single representational property. I argue that this assumption is mistaken. By contrast, I advance an analysis in terms of two defined properties that I call Assimilability and Discretion. I argue that this analysis allows us both to differentiate the various representational types satisfactorily and to understand better the dynamics of change. Within each type, varying the Assimilability or Discretion of a given representation r can explain whether and why we regard it as a "good" or "bad" example of its type, and how the three types relate to each other more generally. And this in turn allows us to give an explanation of the idea of perspicuousness, and to account for the particular perspicuousness of diagrams.

JVenn: A Visual Reasoning System with Diagrams and Sentences

Hajime Sawamura & Kensuke Kiyozuka
Department of Information Engineering, Niigata University
8050, Ninocho, Ikarashi, Niigata, 950-2181 JAPAN

Deduction by a computer studied so far has been centered around symbolic reasoning with formulas. Recently, attention has been directed to reasoning with diagrams as well, in order to augment the deficiency of reasoning with symbols only. In this paper, we propose a visual reasoning system called JVenn which attains a unique amalgamation of the diagrammatic reasoning and the symbolic reasoning, having perspicuity of diagrams and strictness of symbols complementarily. JVenn is unique particularly in the points that it has the strategy for proving a chain of syllogisms, allows for an interplay between diagrams and symbols, and guides reasoning with the beauty measure for diagrams.

Logical Systems and Formality

Patrick Scotto di Luzio
Dept. of Philosophy
Stanford University

The general question is posed: in which respects and to what extent are logical systems which employ diagrammatic representations "formal"? I propose to characterize "formal" rules of inference to be those which are reducible to basic operations on the representations themselves. (This is to be distinguished from a characterization which reduces formality to recursiveness.) Formal systems, then, are those which employ such formal rules of inference. It is argued that this characterization of "formality" has historical and philosophical significance, as it underlies a particular (one may say, "Hilbertian") strategy for dealing with certain epistemological and foundational concerns. I demonstrate that, under this philosophically motivated construal of "formality", diagrammatic systems such as Sun-Joo Shin's Venn-I and heterogeneous systems such as Barwise & Etchemendy's Hyperproof do not count as formal logical systems. It is further suggested that any robust heterogeneous system is unlikely to be formal. The analysis of this paper, then, provides a principled account of how some diagrammatic systems differ radically from linguistic ones. Not only are non-traditional representations being treated in such systems, they are also being treated non-traditionally.

Reviving the iconicity of Beta graphs

Sun-Joo Shin
Department of Philosophy
University of Notre Dame

By devising a new reading method for Peirce's Existential Graphs (EG), this paper moves away from the traditional method of evaluating diagrammatic systems against the criteria appropriate to symbolic systems. As is well-known, symbolic systems have long been preferred to diagrammatic systems and the distinction between the two types of systems has not been well defined. This state of affairs has resulted in a vicious circle: because the unique strengths of visual systems have not been discovered, diagrammatic systems have been criticized for lacking the properties of a symbolic system, which, in turn, reinforces the existing prejudice against non-symbolic systems. Peirce's EG is a classic example of this vicious circle.

Logicians commonly complain that EG is too complicated to put to actual use. This paper locates a main source of this criticism in the traditional reading methods of EG, none of which fully exploits the visual features of the system. By taking full advantage of the iconicity of of EG, I present a much more transparent and useful reading of the Beta graphs. I pursue this project by (i) implementing Peirce's original intuitions for EG, and (ii) uncovering an important visual feature of the system.

Two-Dimensional Positioning as Visual Thinking

Shingo Takada
Dept of Information and Computer Science
Keio University
3-14-1 Hiyoshi, Kohoku-ku
Yokohama, Kanagawa 223-8522 Japan

Yasuhiro Yamamoto, Kumiyo Nakakoji
Nara Institute of Science and Technology

People depend on various external representations in various design situations. These external representations can be categorized along a spectrum: on the one end are representations that are necessary at the time of creation in early stages of a design task, and on the other end are those that are necessary in the future as a design solution or design alternatives. Diagrams and sketches used for design often belong to the former end; designers create diagrams to visualize what they are currently thinking, and to help them continue their task in the process of reflection-in-action. There, however, are domains where such diagrams do not exist. We take writing and programming as two example domains, and argue that two-dimensional positioning serve the same purpose for those domains as "diagrams" do for architectural design. We describe two tools, ART for writing and RemBoard for component-based programming, which help writers or programmers visualize what they are thinking through positioning parts of writing or software components on a two-dimensional space. We examine differences that exist between these two domains, and explore the effects these differences have on the visualization.

Executing Diagram Sequences

Joe Thurbon
Knowledge Systems Group
Dept of A.I.
School of Computer Science & Engineering
University of New South Wales

We present a general framework for using diagram sequences as plan specifications. We also present an implemented system that generates imperative program code from diagram sequences similar to those used in teaching programming. The specific notations we use in the system are based closely on the diagrams typically used for teaching introductory programming, but the framework is general enough to account for and express many uses of diagram sequences. The system and the underlying theory highlight some areas where planning, reasoning about action, the refinement calculus and diagrammatic reasoning are synergistic. For example, by framing the definition of algorithms as a type of plan specification, it becomes clear that refinement, in the software engineering sense, is equivalent to the decomposition of a planning problem into sub-plans. More importantly, the system gives insight into the underlying structure of the largely informal use of diagrams that is routinely found in the explanation of algorithms. Obvious applications include teaching (since the inspiration for the system is a common method for teaching) and software engineering, where diagrams are often used to specify type systems rigorously (e.g. class diagrams), but usually not the actual dynamics of the code.

Lines, Blobs, Crosses, and Arrows: Diagrammatic Communication with Schematic figures

Barbara Tversky, Jeff Zacks, Paul Lee and Julie Heiser
Stanford University
Washington University at St. Louis

In producing diagrams for a variety of contexts, people use a small similar set of schematic figures to convey certain context specific concepts. These same set of schematic figures are also appropriately interpreted. Three examples will support these conclusions: lines, crosses, and blobs in sketch maps; bars and lines in graphs; and arrows in diagrams of complex systems.

Constraint matching for diagram design: Qualitative visual languages

Ana von Klopp Lemon
Sun Microsystems

Oliver von Klopp Lemon

This paper examines diagrams which exploit qualitative spatial relations for representation. The starting point is the theory that such diagrams systems are most effective when their formal properties match those of the domain features that are represented (e.g. Barwise & Shimojima 1995, Stenning & Lemon 2000). We discuss a cognitively salient repertoire of elements in qualitative visual languages (QVLs), which is different from the set of primitives in mathematical topology, and explore how this repertoire affects the expressivity of QVLs in terms of their vocabulary and the possible spatial relations between diagram elements.

We then give a detailed analysis of the formal properties of relations between the QVL elements. It is shown that the analysis can be exploited systematically for the purposes of designing a diagram system. The design process consists first of identifying the categories in the domain and the formal properties of the relations that hold between them. Then the sets of possible spatial relations and diagram elements are evaluated until suitable sets, if any, are identified. We demonstrate this methodology with reference to several domains, e.g. diagrams for file systems and set theory (see e.g. von Klopp Lemon & von Klopp Lemon 2000).

A Proposal for Automatic Diagrammatic Reasoning in Continuous Domains

Daniel Winterstein, Alan Bundy and
Mateja Jamnik
Division of Informatics
University of Edinburgh
School of Computer Science
University of Birmingham, UK

This paper presents one approach to the formalisation of diagrammatic proofs as an alternative to algebraic reasoning. An idea of 'generic diagrams' is developed whereby one diagram (or rather, one sequence of diagrams) can be used to prove many instances of a theorem. This extends Jamnik's ideas in the Diamond system to continuous domains.

The domain is restricted to non-recursive proofs in real analysis whose statement and proof have a strong geometric component. The aim is to develop a system of diagrams and redrawing rules to allow a proof. This approach involves creating a diagrammatic theory. The method is justified formally by (a) a diagrammatic axiomatisation, and (b) an appeal to analysis, viewing the diagram as an object in Real^2. An isomorphism can then be established between diagrams acted on by redrawing rules and instances of a theorem acted on by rewrite rules.

The aim is to implement these ideas in an interactive prover entitled RAT (the Real Analysis Tutor).

Distinctions with differences: comparing criteria for distinguishing diagrammatic from sentential systems

Keith Stenning

A number of grounds for discriminating diagrammatic from sentential semantics have been proposed. Often some sort of spatial homomorphism between diagram and its referent is said to distinguish diagrammatic from sentential systems (e.g. Barwise \& Etchemendy 19??). Or the distinction is analysed in terms of Peirce's distinctions between symbol, icon and index (Peirce ; Shin 19??). Shimojima has proposed that the sharing of logical properties between representing and represented relations is what is critical (Shimojima 19??). We have proposed that the fundamental distinction is between direct and indirect systems of representation, where indirect systems have an abstract syntax interposed between representation and represented entities (Stenning \& Inder 1994; Gurr, Lee \& Stenning 1999; Stenning \& Lemon (in press).

The purpose of the present paper is to illustrate the distinction between directness and indirectness through a comparison of Euler Diagrams and Peirce's Existential Graphs. Peirce's system is a particularly interesting case because its semantics can be viewed as either direct or indirect according to one's construal of its ontology, and secondly because although it has an abstract syntax, it is not the concatenative syntax of sentential languages.

The paper attempts to relate account in terms of directness of semantics to the various other accounts that have been offered.

Reordering the Reorderable Matrix as an Algorithmic Problem

Erkki Mäkinen,
Harri Siirtola
University of Tampere
Department. of Computer Science
HCI Group
Tampere / Pinnink

The Reorderable Matrix is a visualization method for tabular data. This paper deals with the algorithmic problems related to ordering the rows and columns in a Reorderable Matrix. We establish links between ordering the matrix and the well-known and much studied problem of drawing graphs. First, we show that, as in graph drawing, our problem allows different aesthetic criterions which reduce to known NP-complete problems. Second, we apply and compare two simple heuristics to the problem of reordering the Reorderable Matrix: a two-dimensional sort and a graph drawing algorithm.

Animated diagrams: An investigation into the cognitive effects of using animation to illustrate dynamic processes.

Sara Jones
University of Sussex

With increased use of multimedia and computers in education, the use of animation to illustrate dynamics is becoming more commonplace. Previous research suggests that diagrams may reduce cognitive processing as all information is perceptually available, making it more explicit and therefore requiring less inferencing (e.g. Simon and Larkin 1987). Animation, therefore, may be assumed to enhance learning, especially when illustrating dynamic processes, as motion is depicted more visually explicitly, thus reducing cognitive processing. However, although use of animation may mean an increase in explicit perceptually available information, this may not automatically translate into improved understanding. Visual explicitness itself does not necessarily guarantee accurate perception of specific information, nor does perception of information guarantee comprehension. Initial studies suggest that certain characteristics of diagrammatic animation have significant effects on cognitive interaction with material and therefore on comprehension. Current computer technology not only enables improved graphical animated illustration, but also provides the facility to physically interact with information on the screen. This in itself may influence the kind of learning that takes place. This paper presents research investigating how different ways of both representing and interacting with animated diagrams influence the kinds of cognitive interactions that may take place.

Diagramming Aesthetics: Modernism and Architecture in the 21st Century

Mark J. Clayton
Department of Architecture
Texas A&M University
College Station, TX

In architectural design, diagramming has an equally important role in functional studies and in aesthetic studies. Diagrams are used to create and explore alternative schemes at the very early stages. They are also used to explain concepts once a project is completed. Learning to diagram is an important part of architectural education. A particular diagramming vocabulary can help to guide students into an appreciation and consciousness of aesthetics. As an introduction to theories of modernism, students have been instructed in the use of a set of diagrams that express abstract qualities of architectural aesthetics. The exercises are designed to wean students from a naïve aesthetic that merely mimics popular taste and introduce them to the field of aesthetics as an intellectual discipline. The diagramming vocabulary has been developed from the “seven invariables,” described by Bruno Zevi in The Modern Language of Architecture. Students apply the diagrams to analyze examples of famous buildings. They then design a house, applying the aesthetic principles expressed by the diagrams. The resulting designs are compared to previous designs produced by the students to reveal the change that is due in part to learning the diagramming vocabulary.

A Comparison of Graphics and Speech in a Task-Oriented Interaction

Patrick G.T. Healey, Rosemarie McCabe and Yasuhiro Katagiri
Department of Computer Science
Queen Mary and Westfield College
University of London
London, UK

The sychronous use of graphical media to communicate has received relatively little attention. This paper reports the results of an experimental study of graphical communication that systematically compares speech only interaction with speech and whiteboard interaction in a task oriented dialogue. Analyses of both overall performance and communicative process demonstrate that, in contrast to current VMC and text-based media, shared whiteboards can provide a clear transactional advantage in multi-media communication systems. The results also indicate a systematic move toward more abstract graphical representations with experience.

Picking Knots from Trees - The Syntactic Structure of Celtic Knotwork

Frank Drewes, Renate Klempien-Hinrichs
Department of Computer Science
University of Bremen
Bremen, Germany

A typical characteristic of visual languages is that the diagrams in such a language are related by a common structure and layout: the language is defined by a set of syntactic visual rules yielding the acceptable pictures. Formal picture-generating methods help to understand the structure of the languages in question, to classify them, and to generate them automatically by means of computer programs. Artists from many cultures have been using visual rules since ancient times in order to design diagrams of various sorts. A famous visual language of this type is given by the class of celtic diagrams, and in particular celtic knotwork. In this paper, we study the syntactic generation of celtic knots using collage grammars, one of the picture-generating devices studied in computer science. We describe (a picture of) a knot by a term, i.e. an expression over graphical operations and primitives. Such a term corresponds to a derivation tree in a collage grammar, the value of the term being the generated knot. Thus, the tree describes the syntactic structure of the knot, whereas the evaluation of the tree yields the actual knot. Interestingly, two knots may share their syntactic structure although their visual appearance differs. This is reflected in the formal model by the fact that the syntax trees are identical, but their symbols are given different interpretations as picture operations.

Capacity Limits in Diagrammatic Reasoning

Mary Hegarty
University of California, Santa Barbara

This paper examines capacity limits in mental animation of static diagrams of mechanical systems and interprets these limits within current theories of working memory. I review empirical studies of mental animation that examined (1) the relation of spatial ability to mental animation (2) the effects of working memory loads on mental animation, (3) use of external memory in mental animation and (4) strategies for task decomposition that enable complex mental animation problems to be accomplished within the limited capacity of working memory. The effects of capacity limits on mental animation are explored by implementing a simple production system model of mental animation in the 3CAPS production system architecture, limiting the working memory resources available to the model, and implementing strategies for managing scarce working memory resources. It is proposed that mental animation involves the visual-spatial and executive components of working memory and that individual differences in mental animation reflect the operation of these working memory components.


Clouds: A Module for Automatic Learning of Concept Maps

Francisco Câmara Pereira and Amilcar Cardoso

There are currently several interesting works on interactive concept map construction. This simple representation of knowledge - the concept maps - is widely accepted as a promising device for helping in complex tasks such as planning and learning. Moreover, several psychologists (mainly from the constructivist stream) argue that the use of concept maps in teaching can bring relevant improvements in students. Nevertheless, as far as we know, these tools for interactive construction of concept map diagrams have a passive role in the sense that their main concerns rely upon interface and generality. If a Machine Learning based module was added to such frameworks, the computer could have an active role in participating in the concept map construction. This paper presents Clouds, a module that uses Inductive Learning methods to help a user build her own concept maps. It uses each new entry on the map as an example for the learning algorithms and then feeds back its conclusions, suggesting new concepts and relations.

A diagrammatic notation for interval algebra

Zenon Kulpa
Institute of Fundamental Technological Research
00-049 Warszawa, POLAND

In this paper a two-dimensional, diagrammatic representation of the space of intervals, called an MR-diagram is presented, together with another diagrammatic notation based on it -- the so-called W-diagram. Examples of the use of the notation in the algebra of interval relations, in interval arithmetic, and in commonplace reasoning about time intervals are given.

Animation of diagrams: An aid to learning?

Richard K. Lowe
Faculty of Education
Curtin University of Technology

The animation of diagrams is generally assumed to facilitate the learning of subject matter for which both visuospatial and dynamic information are important. However, in cases where the visual complexity of a static diagram is already considerable and the dynamics it represents are also complex, the use of animated presentation has the potential to increase the perceptual and cognitive processing load beyond capacity limits. This paper reports an investigation of how a weather map animation was processed by non-meteorologists who were studying the way meteorological patterns change over time. Subjects completed a learning task then an application task which required them to generate predictions of the changes in a meteorological pattern that would be expected after a 24-hour period elapsed. The findings suggest that under the conditions of high load imposed by this animation, the domain novices adopted perceptually-driven processing strategies that are likely to be counterproductive in terms of the desired learnings. This study reinforces and extends previous work indicating that explicit representation of the dynamics of a situation via the use of animations may not always result in the instructional benefits widely attributed to animated displays.

Diagrams as Components of Multimedia Discourse: A Semiotic Approach

John H. Connolly
Department of Computer Science
Loughborough University, UK

In accordance with the interdisciplinary nature of the conference, this paper draws on semiotics, linguistics and general system theory in an attempt to enhance our understanding of diagrams as elements in the process of communication within multimedia environments. Particular attention will be focussed on the relationship between the graphical aspects of the diagram and the associated text (which includes both the text belonging to the diagram itself and the text which surrounds it).

The main theoretical basis of the paper is founded on a synthesis of concepts from linguistic discourse analysis and from semiotics. From this perspective, diagrams and the elements of which they consist are seen not merely as passive representations of information, but as dynamic complexes of acts, whose purpose is to help to drive the process of communication along.

Given this focus on the actual use of diagrams within the context of communicative activity, a pragmatic (as opposed to a syntactic or semantic) approach is adopted. Accordingly, particular attention is paid to the rhetorical relations which exist between graphical and textual elements. Moreover, the unusual structure of the text typically found within diagrams is discussed with reference to its pragmatic consequences for the reader, involving, as it does, a high degree of reliance on context. In this way, it is hoped that the paper casts some light upon the nature of multimedia communication involving diagrams.

Formalising the Essence of Diagrammatic Syntax

C. Gurr and K. Tourlas
Division of Informatics
University of Edinburgh

Diagrams are commonly regarded as consisting of visual objects engaged in a variety of primitive visual relations. An inherent feature of most diagrammatic notations is that new, implicit relations are perceived to emerge from the explicitly present, primitive relations. This phenomenon is key to the role of diagrams as reasoning and visualisation aids.

We lay the foundation for a general but flexible algebraic framework in which emergent relations, morphisms of diagrams and diagram semantics may be studied. A notion of diagram type is introduced which records symbolically the arities of primitive relations featured by diagrams in a given class. We demonstrate how adding composite relations to a diagram type gives rise to a category C, allowing models of diagrams to be formalised in terms of functors from C to a category of finite sets and relations.

To add further emergent relations to a type C one specifies a "rule" T which suitably completes C with additional structure. Given any model M of a diagram of type C this induces a model T(M) completed with an algebra of relations generated by T. This is illustrated by considering "unions" of relations in a class of software diagrams. We pinpoint the mathematical properties which all "completion rules"` must share, while allowing the choice of specific T\'s to be entirely application dependent.

Using grids in maps

Alexander Klippel, Lars Kulik
University of Hamburg
Department for Informatics and
Doctoral Program in Cognitive Science

Grid structures are widely used in diagrammatic representations. Characteristic cases are search grids that allow direct locating of objects without scanning the whole representational medium or grids in reference maps providing geographic coordinates. Additionally, grids underlying charts facilitate simple comparisons between different quantities. We present a formal analysis to consider the diverse functions of grid structures and to reveal the various contributions of grids in diagrammatic representations. A growing body of research focuses on discrete global grids and grids in general for technical applications like geographic information systems. As our work is concerned with the use of diagrammatic representations by humans, we focus on a qualitative approach. We pursue two objectives: on the one hand, we analyze the possibilities to encode qualitative information in grid structures. On the other hand, we examine in which way grid structures enrich qualitative spatial representations like schematic maps, for instance subway maps, that focus on selected aspects of spatial information. We show that grids in schematic maps have two complementary benefits. First, they enable inferences that are not possible using only the spatial map features. Second, they provide additional design freedom, as important information that is not coded in the schematic map itself can be read of the grid structure.

Case Analysis in Euclidean Geometry: An Overview

Nathaniel Miller
Department of Mathematics
Cornell University
Ithaca, New York

Case analysis has long been a sticking point in attempts to understand how diagrams are used in mathematics, particularly in geometry. When using diagrams, a question that immediately arises is: how many different diagrams must I consider? Indeed, one of the earliest criticisms of Euclid's Elements, which argues extensively using diagrams, was that he didn't distinguish enough cases. Some more recent commentators have argued that proofs that rely on diagrams are inherently informal because the process of finding all of the cases that need to be considered is a non-algorithmic human process that is perhaps even open-ended: each time someone finds a case that hasn't been dealt with yet, a new proof has to be constructed for that case.

In this talk, I will show that case analysis in Euclidean geometry can be done by an algorithm, and will demonstrate a computerized formal proof system CDEG (Computerized Diagrammatic Euclidean Geometry) that automatically does this case analysis in the course of constructing a proof. This system is based on a well-defined syntax and semantics of Euclidean diagrams, and is powerful enough to formalize most of the proofs in the first several books of the Elements. Looking at a formal system like this can shed a lot of light on normal informal diagrammatic practices. For example, lemma incorporation--the use of previously proven lemmas in the proof of a theorem, which is ubiquitous in Euclidean geometry--can lead to an exponential decrease in the number of cases that need to be considered. It can also shed a lot of light on the earlier controversies about case analysis. Consider the problem of finding all of the new diagrams that can result from extending a line segment in a given diagram outward until it intersects another element of the diagram. The algorithm used by CDEG solves this problem in polynomial time, but may return extra diagrams that don't represent any physically realizable situation. There is in fact a computable algorithm which returns precisely those diagrams that represent the physical situations that could occur when you extend the line--that is, it doesn't return any extra unrealizable cases--but we'll show that the problem of finding precisely the realizable cases is at least NP-hard, which roughly means that no algorithm can solve this problem in a reasonable amount of time. So, in the end, it turns out that both sides in the debate were partially correct: it is possible for a computer algorithm to figure out exactly what cases need to be considered, but it isn't possible to do this effectively in practice, because any such algorithm takes too long to run. CDEG avoids this problem by finding extra cases which need to be disposed of later.

Bar Chart Recognition Using Hough Based Syntactic Segmentation

Yan Ping Zhou and Chew Lim Tan

Bar charts are common data representations in scientific and technical papers. In order to recognize the printed bar chart, we present a new Hough based bar chart recognition algorithm which combines syntactic analysis into segmentation. We first detect the most salient feature in any bar chart, bar patterns, using syntactic analysis in the Hough domain. Then we extract text primitives in the Hough domain by combining the text syntactic information and information from the bar pattern extraction. Finally, we interweave the two extraction processes to refine the recognition results. We also present experiments on our algorithm and performance evaluation. Our recognition algorithm is not dependent heavily on a priori knowledge and can recognize bar charts lying in arbitrary directions, such as slant or skewed bar charts, or even hand-drawn bar charts. Thus the algorithm is an ideal model for generic chart recognition system.

Experimenting with aesthetics-based graph layout

Helen C. Purchase, David Carrington, Jo-Anne Allder
Department of Computer Science and Electrical Engineering
The University of Queensland
St Lucia 4072, Australia

Many automatic graph layout algorithms have been designed and implemented to display relational data in a graphical (usually node-arc) manner. The success of these algorithms is typically measured by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising symmetry). Little research has been performed on the usability aspects of such algorithms: do they produce graph drawings that make the embodied information easy to use and understand? Is the computational effort expended on conforming to the assumed aesthetic criteria justifiable with respect to better usability? This paper reports on usability studies that were performed to investigate the merit of automatic graph layout algorithms with respect to human use.

The paper describes three ways in which this issue has been considered experimentally: first, investigating individual aesthetic criteria in simple, abstract graph structures; second, investigating the results of common automatic graph layout algorithms; and third, investigating individual aesthetic criteria and other relevant secondary notations in UML class and collaboration diagrams. The results show that the use of only some aesthetics affect usability significantly, and that the semantic domain of the graph drawings affects which aesthetic criteria need to be emphasised.

This page is maintained by Alan Blackwell and was last modified on: 20 June 2000.