Structure and Semantics of Arrow Diagrams
Yohei Kurata and Max J. Egenhofer
National Center for Geographic Information and Analysis,
Department of Spatial Information Science and Engineering,
Boardman Hall, University of Maine, Orono, ME 04469-5711, USA{yohei, max}@spatial.maine.edu

Abstract. Arrows are major components of diagrams, where they are typicallyused to facilitate the communication of spatial and temporal knowledge. An
automated interpretation of arrow diagrams would be highly desirable in pen-based
interfaces. This paper develops a method for deducing possible interpretations ofarrow diagrams, which is composed of a uni-directional arrow symbol and one ormore components. Based on a study of the use of arrow diagrams, we classify theirsemantics into properties, annotations, actions, and conjunctions. Then, we discuss
the structural requirements of arrow diagrams for illustrating each class ofsemantics, as well as the structural rules for adding optional components. Finally,
we investigate all possible structures of simple arrow diagrams for each class ofsemantics and demonstrate that knowledge about the structure of an arrow diagram
reduces the ambiguity of its interpretation.

1 Introduction
Diagrams are frequently used in people’s daily communications. If computers could
understand diagrams as well, then people could operate a computer system moreintuitively, for instance, by sketching diagrams. Indeed, a number of pen-based systems
that understand human-sketched diagrams have been developed in various fields, andtheir usefulness has been reported repeatedly (Oviatt 1996, Egenhofer 1997, Landay
and Myers 2001, Davis 2002, Ferguson and Forbus 2002). Thus, computational
diagram understanding is one of the highly prospective technologies for enriching
human-computer interactions.
Arrows are major components of diagrams. Arrows appear in various types of diagrams,
such as traffic signs, guideboards, route maps, flowcharts, and illustrations (Horn 1998,
Wildbur and Burke 1998). One reason for such popularity is that arrows capture a large
variety of semantics with their simple shape (Section 2). Another reason is that theexistence of arrows encourages people to interpret causal and functional aspects in a
diagram (Tversky et al. 2000). For instance, Fig. 1 contains only a few words and somearrow symbols over a background map, but people easily read the mechanism of a
spatio-temporal process—the El Niño effect in the Southeastern Pacific Ocean indirectly
influences the rise of tofu price in Japan. In this way, arrows are powerful tools thatfacilitate the communication of spatial and temporal knowledge in a static diagram.
A.G. Cohn and D.M. Mark (Eds.): COSIT 2005, LNCS 3693, pp. 232 – 250, 2005.
© Springer-Verlag Berlin Heidelberg 2005

Structure and Semantics of Arrow Diagrams

Tofu Price233

Soybeans Consumption(as feed grains)

Fish Catches
El Niño

Fig. 1. A diagram with arrows, which illustrates a spatio-temporal process that the El Niño effect(i.e., sea temperature rise in the Southeastern Pacific Ocean) indirectly influence the rise of the
tofu price in Japan

People can interpret such diagrams almost intuitively. Interpretation ofarrow-containing diagrams is, however, a difficult task for computers due to thepolysemy of arrows. For example, in Fig. 1, the arrow symbol departing from El Niño
could be interpreted as a spatial movement (i.e., El Niño is approaching South America)
or an annotation (i.e., a fish species whose catches are declining is El Niño), without
any knowledge about El Niño. To avoid such misinterpretations, the current pen-based
systems require their users to specify the meaning of every arrow (Forbus and Usher
2002) or restrict the meaning of arrows to a small set (Alvarado and Davis 2001,
Landay and Myers 2001, Kurtoglu and Stahovich 2002). Consequently, people cannot
illustrate their knowledge naturally in current pen-based systems. An automatedinterpretation of arrow-containing diagrams, therefore, remains a challenging problem
for developing useful pen-based interfaces.
This paper develops a method for deducing possible interpretations ofarrow-containing diagrams. Here, the interpretation of a diagram is referred to as (1)a process to determine the semantics of a diagram by reasoning, or (2) the determinedsemantics itself. The semantics of a diagram is referred to as a state or behavior of anentity or entities, which is represented by a diagram. A diagram contains symbols,
each of which is assigned to an entity or its feature, which is called the meaning of thesymbol. The semantics of a diagram is built from the meaning of each symbol in the
diagram. We assume that the meaning of each symbol except arrows is alreadyknown.
For simplification, we do not consider the appearance of arrow symbols. Although
the appearance of an arrow symbols is subject to a variety of visual variables (Bertin1983), the arrow symbol alone rarely determine any specific meaning. Its semantic roleis usually established when one or more arrow symbols depart from, traverse, or point
to other elements in the diagram. Thus, we focus on the semantics associated with these
related elements.
The combination of arrow symbols and the related elements is considered as a unit ofsyntax, and called an arrow diagram. Then, these arrow-related elements are called thecomponents of the arrow diagram. An arrow diagram must have at least one arrowsymbol and one component. As a first step, we consider the arrow diagram that contains

234

Y. Kurata and M.J. Egenhofer

only a uni-directional arrow symbol and its related elements. Bi-directional arrows are
not considered, because they are regarded as a synthesis of two oppositely-directed
arrow symbols. Also, independent arrow symbols, such as arrow-shaped traffic signs
indicating curving roads and map symbols indicating north direction, are not discussed
in this paper, because they have no components.
The remainder of this paper is structured as follows: Section 2 investigates various
uses of arrow diagrams, and classifies their semantics into four different classes. Section
3 introduces a framework for the structure of arrow diagrams, based on the alignment ofcomponents and their semantic types. Section 4 discusses the structural requirements forillustrating each class of semantics, and Section 5 discusses the structural conditions ofoptional components. With these two bases, Section 6 investigates all structures ofsimple arrow diagrams that possibly illustrate each class of semantics, and demonstrates
that the possible interpretations of arrow diagrams are determined simply by theirstructures. Finally, Section 7 presents conclusions and future work.

2 Semantics of Arrow Diagrams
What are arrows? Tversky (2001) defined an arrow as a special kind of line, with one
end marked, inducing an asymmetry. Linearity and asymmetry are essential features ofarrows. Asymmetry makes it possible to represent a direction or an order, whereas
linearity makes it possible to represent a length, a path, or a connection. With these two
features, arrow diagrams illustrate a large variety of semantics.
2.1 Use of Arrow Diagrams
One of the primary usages of arrow diagrams is to express a direction. Gombrich(1990) reported a very early example of an arrow diagram, where an arrow symbol wasused to represent the direction of a water stream (Fig. 2a). Arrow diagrams may also
refer to metaphorical directions. Upward directions are metaphorically associated withincrease or improvement, whereas downwards directions are associated with decreaseor debasement (Lakoff and Johnson 1980). Accordingly, upward and downward arrowsymbols are used to illustrate those semantics.
An arrow symbol illustrating a direction has a diagrammatic freedom of length. This
freedom allows the representation of a directed quantity, which is called a vector. A
vector is a quantity that is specified by a direction and a magnitude.
Another traditional usage of arrow diagrams is to illustrate a spatial movement.
Spatial movement is an event where an entity changes its spatial position continuously.
Bertin (1983) showed a classic example that illustrates the paths of several expeditionsin the Sahara Desert (Fig. 2b) and claimed that an arrow is the most efficient (and often
the only) formula for representing a complex movement. The linearity and theasymmetry of an arrow symbol are appropriate features for illustrating the p at h a ndthe, direction of the spatial movement respectively.
In geography, the flow of people, goods, or services between specific locations iscalled a spatial interaction (Bailey and Gatrell 1995). Since a spatial interaction is anStructure and Semantics of Arrow Diagrams

235

aggregation of spatial movements, an arrow diagram can illustrate a spatial interaction
just like a spatial movement, although the detailed route is often abbreviated due to thelack of the designer’s concern (Fig. 2c). Monmonier (1990) reports that arrows are
particularly useful for showing such spatial interactions as migration streams, spatial
diffusion of ideas, migrations of tribes and refugees, and advance of armies. The scaleof a spatial interaction is usually illustrated by the width of the arrow symbol, because
people typically perceive the width of lines without a bias (Robinson et al. 1995).
Spatial interactions can be generalized into interactions, which refer to the flow of acertain item from one entity to another entity, such that these two entities communicate
indirectly. The communicating entities are not limited to locations; they can be otherentities, such as people and physical objects (Fig. 2d).
Arrow diagrams are used not only in a spatial context, but also in a temporal context.
For instance, timetables often contain arrow diagrams, each of which illustrates thatsomething continues over a certain period (Fig. 2e). This semantics is called temporalcontinuity. People understand the concept of time with the aid of spatial metaphors(Lakoff and Johnson 1980). Temporal continuity is understood with the metaphor of
travel, in the sense that something travels continuously over time instead of space.
Therefore, arrow diagrams that originally describe travel in space (i.e., spatial
movement) are naturally extended to describe a travel in time (i.e., temporalcontinuity).
Similarly, flowcharts often contain arrow diagrams, each of which captures atemporal order of two components (Fig. 2f). The order is distinctively expressed by the
directionality of an arrow symbol. The connected two components in an arrow diagram
refer to (1) two different entities or (2) two different states of an identical entity. In theformer case, the arrow diagram may imply a conditional relation or a causal relation of
the associated components, such that the proceeding component works as aprecondition or a cause of the subsequent component. In the latter case, the arrow
diagram may imply a change. A change is an event where an entity transforms its
features, such as identity (Hornsby and Egenhofer 2000), appearance, name, andstructure. For instance, a chemical equation, such as 2H2+O2Æ2H2O, illustrates a set ofmaterials transforming its molecular structures.
Arrow diagrams are also used in complicated illustrations, where each arrow symbol
connects an element of the illustration with a short description (Fig. 2g). This use iscalled labeling. Arrow symbols or lines are often used for labeling when the illustration
becomes messy if descriptions are placed directly on it. Although both an arrow symbol
and a line can connect an element and its description, the directionality of the arrowsymbol makes it clear that the description is assigned to the element, and accordingly
people can distinguish the element and its description more easily.
Finally, the use of arrow diagrams to illustrate relations is a widespread convention
in sketches (Forbus and Usher 2002). An arrow diagram visualizes the presence of adirected relation between two components. In mathematics, a set of directed binary
relations is modeled as a directed graph, which is often visualized using arrow diagrams(Fig. 2h). Directed binary relations are a broad concept that includes temporal orders,conditional relations, causal relations, labeling, and so on.

236

Y. Kurata and M.J. Egenhofer

(c)
(a)

(b)

(d)
(e)

(f)

(g)

(h)

Fig. 2. Examples of arrow diagrams illustrating various semantics: (a) a direction (Gombrich1990), (b) spatial movements (Bertin 1983), (c) spatial interactions (Tobler 1987), (d) aninteraction (Worboys and Duckham 2004), (e) temporal continuities (Horn 1998), (f) temporalorders (Horn 1998), (g) labeling (Worboys and Duckham 2004), and (h) ordered relations(Lipschutz and Lipson 1997)

2.2 Classification of Arrow Diagram Semantics
For the following discussions, the semantics of arrow diagrams are classified into four
different classes (Table 1).
First, the arrow-related semantics are divided into semantics that require only one
component and semantics that require two or more components (Fig. 3). In the former

Structure and Semantics of Arrow Diagrams

237

Table 1. Classification of the semantics of arrow diagrams

Example of semantics

Class

Direction, vector

Propertylabeling

Annotation

Spatial movement, temporalcontinuity, interaction

Actiontemporal order, conditional
relation, causal relation,change, ordered relation

conjunction

Definition
modification of a component by attaching anarrow symbol to the component
modification of a component by connecting adescription to the component
a motion of one component that may becaused or cause an interaction with anothercomponent.
association of components, where an arrowsymbol does not express a motion

case, the arrow symbol is attached to a component and modifies it directly. Suchsemantics is called a property. Directions and vectors are examples of properties.
Although an arrow diagram illustrating a property sometimes contains twocomponents, only one of them is essential for illustrating that property (Section 5.2).
Among the arrow-related semantics that require two or more components, labelingis exceptional, because other semantics associate at least two independent componentsthat do not modify each other, while labeling introduces one component only formodifying another component. Thus, labels are distinguished from the other semantics(Fig. 3) and referred to as an independent class of semantics called annotation. An
annotation is defined as a modification of a component by connecting the component
and its description. Annotations and properties are similar in the sense that both of them
modify one component, although their representation styles are different.
The remaining arrow-related semantics are divided into actions and conjunctions(Fig. 3). Actions are the semantics where an arrow symbol illustrates a motion of one
component that may be caused or cause an interaction with another component. Spatial
movements, temporal continuities, and interactions are classified into actions, sincethese semantics refer to a spatial or temporal movement. On the other hand, aconjunction is an association of components, where an arrow symbol does not express amotion. Accordingly, the shape of an arrow symbol is often meaningful for an action,
while it is not for a conjunction.
Arrow-related Semantics
requires one component

requires two or more components

Property
associates the components that
do not modify each otherintroduces one component for
modifying another component

Annotation
mentions a motion by an arrow symbol

Actiondoes not mention a motion by an arrow symbol

Conjunction

Fig. 3. Classification of arrow-related semantics

238

Y. Kurata and M.J. Egenhofer

3 Structures of Arrow Diagrams
Arrow diagrams illustrate a large variety of semantics, which increases the difficulty of
their interpretation. To tackle this problem, we first develop a method for making roughinterpretation of an arrow diagram from its structural pattern alone. As the foundationof this method, this section summarizes the formal structures of arrow diagrams
developed by Kurata and Egenhofer (2005).
The components of an arrow diagram are diagrammatic elements that an arrowsymbol originates from, traverse, or points to. We classify the components of arrow
diagrams into the following five types:• An object takes an action, either independently (e.g., a person in Fig. 4a) or as aresult of interaction (e.g., a bag in Fig. 4a).
• An event occurs in time, and is characterized by a set of changes. An event occurs
over an interval (e.g., snow in Fig. 4b) or at an instant (e.g., a traffic accident in
Fig. 4b).
• A location is a position in space. It may be a point (e.g., a place in Maine in Fig.
4c) or a homogeneous area (e.g., Maine).
• A moment is a position in time. It may be an instant (e.g., 8:20 in Fig. 5a) or ahomogeneous interval (e.g., morning).
• A note is a short description that modifies an arrow symbol (e.g., send in Fig. 4a)or another component (e.g., Mr. K in Fig. 4a and You are here in Fig. 4c). A noteand the modified component are placed adjacently to each other or connectedwith each other by an arrow symbol.
For simplification, an object, an event, a moment, a location, and a note are sometimes
denoted as O, E, M, L, and N, respectively.
Mr. K
send

You are
here

8:20

(a)

(b)

(c)

Fig. 4. Arrow diagrams that contain various types of components

Although a component may be mentioned by an icon, a text, or a specific position ina background drawing, this classification is not concerned with such a descriptive styleof the component. We assume that automated interpreters of arrow semantics will
distinguish these component types based on their knowledge base.
Components of an arrow diagram are located in front of the arrow’s head, behind thearrow’s tail, or along the arrow’s body. We, therefore, consider that an arrow symbol
identifies three different areas where the components of the arrow diagram are located(Fig. 5). These areas are called component slots, and they are further classified into a
tail slot, a head slot, and a body slot. Each component in an arrow diagram is uniquely
assigned to one of these three slots, thereby making the distinction of tail components,
body components, and head components. The component slots need to beStructure and Semantics of Arrow Diagrams

239

distinguished, because the same symbols, used in different slots, illustrate significantly
different semantics (Kurata and Egenhofer 2005).
An arrow diagram has three slots, where five types of components may be located.
The combination of the types of components in the three slots composes a certain
pattern that is specific to every arrow diagram. These patterns are described as

Tail slot

Body slot

Head slot

Fig. 5. Three component slots associated with an arrow symbol([M|E|L|O|N]*, [M|E|L|O|N]*, [M|E|L|O|N]*), where [x]* means empty or a sequenceof any number of x, x|y means x or y but not both, and the three elements in parentheses
indicate the types of components in tail, body, and head slot, respectively. For example,
the structures of arrow diagrams in Fig. 4a-c are described as (ON, MN, O), (E, -, E),
and (N, -, L), respectively. These patterns capture fundamental structures of arrow
diagrams, since they capture the alignment of components while abstracting theindividual difference and the absolute location of the components.

4 Structural Requirements of Arrow Diagrams
This section discusses the structures of arrow diagrams that are required for illustrating
certain semantics. The discussion follows the classification of the arrow-related
semantics in Section 2.
4.1 Structural Requirements for Illustrating a Property
When an arrow diagram illustrates a property, its arrow symbol is tied to only one
component. Consequently, all visual variables of the arrow symbol, such as length,
width, shape, color, orientation, and pattern (Bertin 1983), can be controlled by its
designer. Among these variables, length and orientation are predominant due to thelinearity and asymmetry of arrow symbols. Arrow symbols are, therefore,
appropriate for representing some feature that is related to a length, an orientation, or
both. A length is, however, illustrated more easily by a line or a bar. Consequently,
arrow symbols are exclusively used to illustrate (1) properties that are specified byan orientation (i.e., directions) or (2) properties that are specified by both anorientation and a length (i.e., vectors).
The component whose property is described by an arrow symbol is called asubject. The subject can be placed in any slot, since nothing conflicts with thesubject (Fig. 6a-c). The different positions of the subject, however, yield slightly
different semantics:

240

Y. Kurata and M.J. Egenhofer• if the subject is placed in the tail slot (Fig. 6a) the illustrated property may berelated to an outgoing action,• if the subject is placed in the body slot (Fig. 6b) the illustrated property may berelated to a passing-through action, and• if the subject is placed in the head slot (Fig. 6c) the illustrated property may berelated to an incoming action.
Thus, a moving direction of a car, a wind direction, and a direction of an external force
are distinctively illustrated by arrow diagrams with these different structures (Fig. 6a’-c’).
The arrow diagrams in Fig. 6a’-c’ indicate that an object, a location, and an event
may represent a subject of a property (i.e., they can have a direction or a vector). A
moment and a note cannot have these properties, since the moment is a
one-dimensional concept and the note is a subsidiary component.
S

S

S

(a)

(b)

(c)

(a’)

(b’)

(c’)

Fig. 6. (a-c) Basic structures of arrow diagrams for illustrating a property of a subject (S). (a’-c’)
Examples of the corresponding arrow diagrams, which illustrate: (a) a moving direction of a car,(b) a wind direction, and (c) a direction of an external force

4.2 Structural Requirements for Illustrating an Annotations
An arrow symbol may illustrate an annotation by connecting a component and its
description (Fig. 7). Annotation and properties are similar in the sense that both modify
a component. Thus, the annotated component is called a subject by analogy.
Mr. K

airporttravelergoing to Boston

9:00pmFig. 7. Examples of arrow diagrams illustrating annotations. Annotations describe various
features of a subject, such as name (Mr. K), category (traveler), status (going to Boston), spatial
position (airport), and temporal position (9:00am).

When illustrating an annotation, an arrow diagram takes only one type of structurewith regard to a description and a subject in order to specify that the description is
assigned to the subject (Fig. 8).

Structure and Semantics of Arrow Diagrams

D

241

S

Fig. 8. Basic structure of arrow diagrams for illustrating an annotation (D: description; S:
subject)

The subject in annotations is represented by any type of component except for notes,
since notes are subsidiary. The description is represented by a note, a location, or a
moment. A location and a moment specify the spatial and temporal position of thesubject, respectively (e.g., airport and 9:00am in Fig. 7), whereas a note describes otherfeature of the subject, such as name, category, and status (Mr. K, traveler, and going to
Boston in Fig. 7).
4.3 Structural Requirements for Illustrating an Action
In this section, we show how different types of actions can be modeled with arrow
diagrams eliciting different types of structures.
In a primitive sense, an arrow is a flying weapon that moves in space. Naturally, anarrow diagram is used to illustrate a spatial movement of an entity. In addition, an arrow
diagram is analogically used to illustrate a temporal continuity of an entity, because anentity travels in time, just like it travels in space.
The movement of an entity may accompany another action. If there is another entity
in the way of the moving entity, it implies that the moving entity gets into contact withthis entity. This type of semantics is called an encounter. An encounter is an action
where an entity (mover) physically or conceptually moves, and eventually has a contact
with another entity (receiver). Encounters are described by such verbs as approach,enter, join, conflict, receive, consume, mount, and import.
An encounter refers to two entities getting together. Conversely, a division occurs
when two entities become separated. It is an action where an entity (mover) moves
away from another entity (sender). Divisions are described by such verbs as exit,
withdraw from, branch off, leave, produce, uninstall, and export.
The third possibility is the combination of a division and an encounter, that is, anaction where an entity (mover) moves away from another entity (sender), and then gets
into contact with the third entity (receiver). This semantics is called a ditransitive
action, since it is analogous to a ditransitive verb in linguistics, such as send, give,
show, tell, explain, sell, and buy. Ditransitive verbs refer to two types of objects: (1)direct objects, which receive the subject’s action directly, and (2) indirect objects,
which receive the subject’s action indirectly. The direct objects intermediate the subject
and the indirect objects. If this intermediation accompanies physical or conceptual
movement, the semantics can be represented diagrammatically with an arrow diagram
as a ditransitive action.
Any of the above five types of actions requires a mover. In addition, an encounter
requires a receiver, a division requires a sender, and a ditransitive action requires both asender and a receiver. The sender and the receiver must be placed in the tail and the242

Y. Kurata and M.J. Egenhofer

head slot, respectively, since arrow’s tail and head imply the initial and final positionsof a motion. Meanwhile, the mover should be placed in any slot that is not occupied by
the sender or the receiver, so that the mover can be visually distinguished from them.
Thus, this classification of actions yields eight different structures of arrow diagramswith regard to a mover, a sender, and a receiver (Table 2).
A mover is represented by an object or an event, because objects and events are theonly components that may move in space or time. A sender is represented by an object,
an event, or a location. For example, an industrial plant (object), deforestation (event),
and a volcano (location) can send out air pollutants (mover). Similarly, a receiver isrepresented by an object, an event, or a location. For example, a famous statue (object),a festival (event), and a historic site (location) can receive a tourist (mover). Arrowdiagrams can be applied to illustrate all of these scenarios.
Table 2. Basic structures of arrow diagrams for illustrating actions with regard to a mover (Mv),a sender (Sd), and a receiver (Rc)
Semantics

Structural patterns

spatial movement /temporal continuity

Mv
Mv

Mv

Mv

Encounter

Rc

Mv

Rc

Sd

Mv

Mv

Division

Sd

Ditransitive relation

Mv
Rc

Sd

Spatial movement also needs at least one component in an arrow diagram thatspecifies its origin, route, or destination. Similarly, temporal continuity needs at least
one component that specifies its start-time or end-time. The origin, route, anddestination are represented by locations in the tail, the body, and the head slot,
respectively (Fig. 9a), while the start-time and end-time are represented by moments inthe tail and the head slot (Fig. 9 b). These components are referred to as adverbial
components (Section 5.2).
SeattleBostonAtlanta
(a)

8:30

11:30
(b)

Fig. 9. Arrow diagrams illustrating an action contains adverbial components, which specify (a)the origin, the route, and the destination, and (b) the start-time and the end-time of the actionStructure and Semantics of Arrow Diagrams243

4.4 Structural Requirements for Illustrating a Conjunction

An arrow diagram may illustrate a conjunction, where multiple components areassociated without referring to a motion. For example, LobsterÆMaine is aconjunction where lobster is associated with Maine. Every conjunction has a certain
theme that justifies the association (Table 3). In LobsterÆMaine, lobster and Maine areassociated, for instance, under the theme of local specialty. The theme may be specified
in a caption, a legend, or an adverbial component that modifies the arrow symbol(Section 5.2), or may be infered from the context.
Since an arrow symbol is oriented, the associated components are naturallyordered. Therefore, if a certain rationale is available, the associated components
should be aligned in a meaningful way. The underlying theme often provides such arationale as temporal order (e.g., from old to new), spatial order (e.g., from high tolow, from front to back, and from part to whole), logical order (e.g., frompresumption to conclusion), or thinking order (e.g., first comes into head, firstplaced) (Table 3).

Table 3. In conjunctions, components are associated under a certain theme and aligned under acertain rational

AssociatedComponents
Lobster, Maine
Plan, Do, See
Niagra Falls,
Lake Ontario
Maine,New England
Snow, Delay

Rationale of
Alignment
Thinking order

Theme
local specialty

Representation
LobsterÆMainePlanÆDoÆSee

geographic
attribution

temporal order
spatial order(high to low)
spatial order(part to whole)causal relation

logical orderSnowÆDelay

work processwater flow

Niagra FallsÆLake Ontario
MaineÆNew England

The associated components are placed in the tail and the head slot of an arrow
diagram, such that these components look equally associated, as well as the orderamong these components are highlighted (Fig. 10). Any type of component, except
notes, can be the associated components, as long as people identify the theme thatassociates these components.

Pr

Sc

Fig. 10. Basic structure of arrow diagrams for illustrating conjunctions (Pr, Sc: the associatedcomponent that proceeds and succeeds in an order, respectively)

244

Y. Kurata and M.J. Egenhofer

5 Optional Components of Arrow Diagrams
The previous section discussed the structural requirements for illustrating each class ofsemantics. In addition to the components requested by these requirements, arrow
diagrams may have the following two types of optional components.
5.1 Adjective Components

An adjective component of an arrow diagram modifies an individual component of thearrow diagram. It is analogous to adjectives in linguistics, which modify an individual
noun. The adjective component describes a feature of the component, such as its
category, name, scale, spatial position, and temporal position—just as descriptions inannotations do.
The component and its adjective component are placed adjacently to each other and,
therefore, they are always placed in the same slot (Fig. 11). An adjective component isrepresented by a location, a moment, or a note, each of which illustrates the place, time,and other features of the modified component.

traveler

Maine

Fig. 11. An arrow diagram that contains adjective components (traveler and Maine)

5.2 Adverbial Components

An adverbial component of an arrow diagram modifies the main semantics that thearrow diagram illustrates. It is analogous to adverbs and adverbial phrases inlinguistics, which modify a verb. Properties, actions, and conjunctions may haveadverbial components in arrow diagrams, whose functions are as follows:• An adverbial component of a property describes a feature of the property, such as
category, name, or scale (Fig. 12a-c).
• An adverbial component of an action describes a feature of the action, such as (1)origin, route, or destination (Fig. 9a), (2) start-time or end-time (Fig. 9b), or (3)category, measure, overall spatial position, overall temporal position, or scale(Fig. 12d-f).
• An adverbial component of a conjunction describes a feature of the conjunction,such as associating theme, sequential condition, sequential probability, overall
spatial position, or overall temporal position (Fig. 12g-i).

Adverbial components are usually optional, but spatial movement requires at least
one adverbial component that specifies the origin, the route, or the destination, andtemporal continuity requires at least one adverbial component that specifies thestart-time or the end-time (Section 4.3).

Structure and Semantics of Arrow Diagrams

245

An adverbial component is represented by a location, a moment, or a note,depending on the feature that it describes:• a location represents origin, route, destination, or overall spatial position,• a moment represents start-time, end-time, or overall temporal position, and• a note represents other features.

An adverbial component is usually placed in the body slot, especially around thecenterof an arrow symbol, so that it appears visually that the adverbial component isdevoted to not a part but the whole of the arrow symbol (Fig. 12). Exceptionally,

external force

50 kgm/s2

f1

(a)

(b)

send
by aircheck-incounter
8:20

(d)

(e)

(f)

cause

if warm

90%

BostonFeb. 28

(h)

(i)

(g)

(c)
600 mph3hBostonFig. 12. Arrow diagrams, illustrating (a-c) a property, (d-f) an action, and (g-i) a conjunction.
Each arrow diagram contains adverbial components which describe: (a) property’s category, (b)property’s name, (c) property’s scale, (d) action’s category and measure, (e) overall spatial andtemporal position of the action, (f) action’s scales, (g) underlying theme of the conjunction, (h)sequential condition and sequential probability of the conjunction, and (i) overall spatial andtemporal position of the conjunction.

locations representing an origin and a destination are placed in the tail and the head slot,
respectively, since arrow’s tail and head imply the initial and final positions of amotion. Similarly, moments representing a start-time and an end-time are placed in the
tail and the head slot, respectively. In any case, an adverbial component must be placedin an empty tail slot, an empty head slot, or an empty part of the body slot; otherwise,
the adverbial component is misinterpreted as an adjective component.

6 Deducing Possible Interpretations from Structures
semantics and the structural conditions for adding optional components, we canconsider the structures of arrow diagrams that possibly illustrate each class ofsemantics. One problem is that arrow diagrams take countless structures, since eachslot can contain an arbitrary slot Now that we have both the structural requirements forillustrating each class of number of components. For simplification, here we consider

246

Y. Kurata and M.J. Egenhofer

only simple arrow diagrams, which have at most one component per each. Since eachof the three slots has six possible patterns (an object, an event, a location, a moment, a
note, and an empty component) but an arrow diagram must have at least one
component, simple arrow diagrams may take only 23 − 1 = 215 different patterns ofstructures. Thus, we can exhaustively investigate all structures of arrow diagrams thatpossibly illustrate each class of semantics. For example, to illustrate a property, one of
the three slots must contain a subject, which is represented by an object, an event, or alocation. In addition, an optional component (i.e., an adverbial component), which isrepresented by a note, may be place in the body slot if it is empty. Accordingly, there
are 15 structures of simple arrow diagrams that possibly illustrate a property (Table 4).
Similarly, we can enumerate 12 structures for annotations, 98 structures for actions, and64 structures for conjunctions.
Table 4. All structural patterns of arrow diagrams illustrating a property
Adverbial component

Subject-

Note (N)Object (O)(O, -, -) (-, O, -) (-, -, O)(O, N, -) (-, N, O)

Event (E)(E, -, -) (-, E, -) (-, -, E)(E, N, -) (-, N, E)

Location (L)(L, -, -) (-, L, -) (-, -, L)(L, N, -) (-, N, L)

Based on this result, we can judge whether a given arrow diagram has a possibility ofillustrating each class of semantics. Among the 215 structures of simple arrow
diagrams, 82 structures have no corresponding class, 81 structures correspond toexactly one class, and 52 structures correspond to multiple classes (Fig. 13).
Property

Conjunction

12

15

4 4 4

Annotation

44
50

Action82

Fig. 13. The correspondence of 215 structures of simple arrow diagrams to the four classes ofsemantics

An arrow diagram with one of the 82 structures that has no corresponding class is
automatically judged as a meaningless diagram (Fig. 14a), and an arrow diagram with
one of the 81 structures that correspond to exactly one class leads to a unique class ofinterpretation (Fig. 14b). Fig. 13 highlights that an arrow diagram illustrating a property
is always interpreted uniquely, while an arrow diagram illustrating other semantics(especially an annotation or a conjunction) is often ambiguous.

Structure and Semantics of Arrow Diagrams

You arehere

Seattle(a)247

Boston(b)

Fig. 14. (a) An arrow diagram, whose structure (N, O, L) has no corresponding class ofsemantics, is judged as meaningless, and (b) an arrow diagram, whose structure (L, O, L)
corresponds to exactly one class of semantics (action), leads to a unique class of interpretation

Table 5 shows the structures of arrow diagrams that correspond to multiple classesof semantics. The structures S1 and S2 indicate that (1) an arrow diagram that annotates acomponent by a location or a moment (Fig. 15a1) and (2) an arrow diagram that
illustrates a conjunction whose proceeding component is a location or a moment (Fig.
15a2) cannot be distinguished by their structures alone. An arrow diagram is, however,uniquely interpreted as a conjunction if the head component cannot be located at the
spatial or temporal position that is specified by the tail component (for instance, Fig.
15a2 cannot be interpreted as an annotation because Lake Ontario is not located in
Niagara Falls). Otherwise, we need to judge whether the diagram has a certain theme
for associating these components.
Table 5. Structures of arrow diagrams corresponding to multiple classes of semantics

Structures
S1
S2
S3

(L|M, -, L|M)
(L|M, -, O|E)
(O|E, -|L|M|N, O|E|L|M),(L|M, L|M|N, O|E)

Number ofstructures4
4

annotation and conjunction
annotation, action, and conjunction

44

action and conjunction

San Jose

Paris

Costa Rica

(a1)
Niagra
Falls

(b1)
Lake
Ontario(a2)

Semantics

(c1)
Paris

(b2)

(c2)

Fig. 15. Three pair of arrow diagram whose semantic classes are different but whose structuresare same. The structures of arrow diagrams illustrating (a1) an annotation and (a2) a conjunction
are both (L, -, L), those illustrating (b1) an action and (b2) a conjunction are both (O, -, O), andthose illustrating (c1) an annotation and (c2) an action are both (L, -, O).

248

Y. Kurata and M.J. Egenhofer

Similarly, arrow diagrams illustrating an action or a conjunction, whose structures
are in S2 or S3, cannot be distinguished by their structures alone (Fig. 15b1 and 15b2).
The large number of these ambiguous structures shows the importance of their
distinction. An arrow diagram is uniquely interpreted as a conjunction if neither its tailcomponent nor its head component is supposed to move (for instance, Fig. 15b2 cannot
be interpreted as an action because both the house and the burning house are
immovable). Otherwise, we need to judge whether the diagram has a certain theme for
associating these components and whether the action possibly illustrated in the arrow
diagram is a typical scenario of actions.
We further need the distinction of arrow diagrams illustrating annotations andactions, whose structures are S2 (Fig. 15c1 and 15c2). An arrow diagram is uniquelyinterpreted as an annotation if the tail component is not supposed to move (for instance,
Fig. 15c1 does not illustrate an action because the Eiffel Tower is immovable).
Otherwise, their distinction may depend on the context.

7 Conclusions and Future Work
This paper presented the classification of arrow-related semantics, the structuralrequirements for illustrating each class by arrow diagrams, and the structural conditions
for adding optional components. Based on these settings, we demonstrate that 82
structures of simple arrow diagrams are automatically judged as meaningless, 81
structures leads to a unique class of semantics, and 52 structures lead to two or threepossible classes of semantics. This indicates that knowledge about the structure of anarrow diagram reduces the ambiguity of its possible interpretations.
The knowledge about the structure is still useful for deducing more detailed
interpretation of the arrow diagram. For example, Section 4.3 indicated that five typesof actions, each of which has different structural requirements. Thus, the structuraldifferences of arrow diagrams are probably useful for distinguishing these different
types of actions.
In addition to the structures, various clues lead people to a unique and more detailed
interpretation of an arrow diagram. For example, intrinsic mobility, movable space, andmovable direction of each component are critical clues for judging whether thecomponent is supposed to move (Fig. 16). This knowledge is, then, useful for judging
whether an arrow diagram may illustrate an action, and if so, which type of action it
may illustrate (i.e., encounter or division). Similarly, the caption or the adverbial
component of an arrow diagram may specify or imply a theme for association, which isuseful for judging whether an arrow diagram may illustrate a conjunction, and if so,which type of conjunction the arrow diagram may illustrate.

P
(a)

(b)

(c)

Fig. 16. Thanks to the knowledge about (a) intrinsic mobility, (b) movable space, and (c)movable direction of the car, arrow diagrams that are typically interpreted as a person leaves acar, not as a car approaches a person

Structure and Semantics of Arrow Diagrams

249

Making use of such available clues comprehensively, we are now challenging todevelop more sophisticated method for interpreting arrow diagrams. This method is
expected to enhance the usability of pen-based systems, such that its user cancommunicate with the systems more naturally by drawing an arrow-containing
diagram. In addition, since an arrow diagram is popular and often the simplest tool forthe representation of spatial and temporal knowledge, to reveal the mechanism of arrow
diagrams should lead to further understanding of people’s communication about space
and time.

Acknowledgments
This work was partially supported by the National Geospatial-Intelligence Agency
under grant number NMA201-01-1-2003. Yohei Kurata is further supported by a
University of Maine International Tuition Scholarship. Max Egenhofer’s work isfurther supported by the National Science Foundation under grant numbers
EPS-9983432 and IIS-9970123; the National Geospatial-Intelligence Agency under
grant numbers NMA201-00-1-2009, and NMA401-02-1-2009.

References
Alvarado, C. and Davis, R. (2001) Resolving Ambiguities to Create a Natural Sketch Based
Interface. 17th International Joint Conference on Artificial Intelligence (IJCAI-01), Seattle,
WA. pp.1365-1374.
Bailey, T. and Gatrell, A. (1995) Interactive Spatial Data Analysis. Essex, UK: Longman.
Bertin, J. (1983) Semiology of Graphics: Diagrams, Networks, Maps. Madison, WI: Universityof Wisconsin Press.
Davis, R. (2002) Sketch Understanding in Design: Overview of Work at the MIT AI Lab. AAAI
Spring Symposium on Sketch Understanding, Menlo Park, CA, AAAI Press. pp.24-31.
Egenhofer, M. (1997) Query Processing in Spatial-Query-by-Sketch. Journal of Visual
Languages and Computing. 8(4): 403-424.
Ferguson, R. and Forbus, K. (2002) A Cognitive Approach to Sketch Understanding. AAAI
Spring Symposium on Sketch Understanding, Menlo Park, CA, AAAI Press. pp.67-72.
Forbus, K. and Usher, J. (2002) Sketching for Knowledge Capture: A Progress Report. 7thInternational Conference on Intelligent User Interfaces, San Francisco, CA, ACM Press.
pp.71-77.
Gombrich, E. (1990). Pictorial Instructions. In Images and Understanding: Thoughts About
Images-Ideas About Understanding. Barlow, H., Blakemore, C. and Weston-Smith, M. (eds.),
Cambridge, UK: Cambridge University Press, pp.26-45.
Horn, R. (1998) Visual Language: Global Communication for the 21st Century. Bainbridge
Island, WA: MacroVu, Inc.
Hornsby, K. and Egenhofer, M. (2000) Identity-Based Change: A Foundation for
Spatio-Temporal Knowledge Representation. International Journal of Geographical
Information Science. 14(3): 207-224.
Kurata, Y. and Egenhofer, M. (2005) Semantics of Simple Arrow Diagrams. AAAI Spring
Symposium on Reasoning with Mental External Diagram: Computational Modeling andSpatial Assistance, Menlo Park, CA, AAAI Press.

250

Y. Kurata and M.J. Egenhofer

Kurtoglu, T. and Stahovich, T. (2002) Interpreting Schematic Sketches Using PhysicalReasoning. AAAI Spring Symposium on Sketch Understanding, Melon Park, CA, AAAI Press.
pp.78-85.
Lakoff, G. and Johnson, M. (1980) Metaphors We Live By. Chicago, IL: University of Chicago
Press.
Landay, J. and Myers, B. (2001) Sketching Interfaces: Toward More Human Interface Design.
IEEE Computer. 34(3): 56-64.
Lipschutz, S. and Lipson, M. L. (1997) Schaum's Outline of Theory and Problems of Discrete
Mathematics. New York: McGraw-Hill.
Monmonier, M. (1990) Strategies for the Visualization of Geographic Time-Series Data.
Cartographica. 27(1): 30-45.
Oviatt, S. (1996) Multimodal Interfaces for Dynamic Interactive Maps. Conference on Human
Factors in Computing Systems (CHI '96), New York, ACM Press. pp.95-102.
Robinson, A., Morrison, J., Muehrcke, P., Kimerling, A. and Guptill, S. (1995) Elements ofCartography. New York: John Wiley & Sons Inc.
Tobler, W. (1987) Experiments in Migration Mapping by Computer. The American
Cartographer. 14(2): 155-163.
Tversky, B. (2001). Spatial Schemas in Depictions. In Spatial Schemas and Abstract Thought.
Gattis, M. (ed.), Cambridge, MA: MIT Press, pp.79-111.
Tversky, B., Zacks, J., Lee, P. and Heiser, J. (2000) Lines, Blobs, Crosses and Arrows:
Diagrammatic Communication with Schematic Figures. Theory and Application of Diagrams(Diagram 2000), Edinburgh, UK, Anderson, M., Cheng, P. and Haarslev, V. (eds.), Lecture
Note in Artificial Intelligence. Berlin: Springer. pp.221-230.
Wildbur, P. and Burke, M. (1998) Information Graphics: Innovative Solutions in Contemporary
Design. New York: Thames & Hudson.
Worboys, M. and Duckham, M. (2004) GIS: A Computing Perspectinve. Boca Raton, FL: CRC
Press.