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

Abstract. Illustrating a dynamic process with an arrow-containing diagram is a
widespread convention in people’s daily communications. In order to build abasis for capturing the structure and semantics of such diagrams, this paper
formalizes the topological relations between two arrow symbols and discusses
the influence of these topological relations on the diagram’s semantics.
Topological relations of arrow symbols are established by two types of links,
intersections and common references, which are further categorized into nine
types based on the combination of the linked parts. The topological relations arecaptured by the existence/non-existence of these nine types of intersections andcommon references. Then, this paper demonstrates that arrow symbols withdifferent types of intersections typically illustrate two actions with different
interrelations, whereas the arrow symbols with common references illustrate apair of semantics that may be mutually exclusive or synchronized.

1

Introduction

Illustrating a dynamic process with an arrow-containing diagram is a widespread
convention in people’s daily communications. Fig. 1a-c illustrate examples ofdiagrams for such dynamic processes as a workflow, an assembling procedure, andgeographic propagations. If computers understand such arrow-containing diagrams,
people can interact with computers more intuitively, for instance, by sketching a
diagram on computer screens (Kurata and Egenhofer 2005a) to instruct the machines
about the dynamic processes they will manage, support, or simulate.
Communication through an arrow-containing diagram requires the diagram readers
to interpret the meaning of each arrow symbol in the diagram, because arrow symbols
have a large variety of meanings (Horn 1998) and are used multi-purposely even in asingle diagram without specification (Tversky, et al. in press). Such interpretations are
not easy for computers (Kurata and Egenhofer 2005a), and sometimes even difficultfor people without well-crafted context (Tversky, et al. in press). Kurata andEgenhofer (2005b) demonstrated that the interpretation of a diagram with a single
arrow symbol can be partly derived from its syntactic pattern. People, however, often

communicate using more complex diagrams with multiple arrow symbols (Figs. 1ac). It, therefore, remains a challenging problem to develop a formal method forinterpreting such complex arrow-containing diagrams. As a first step toward this goal,
this paper analyzes the spatial relations between arrow symbols in such complex
diagrams and observes the influence of the spatial relations on the diagram’s
semantics. Among several types of spatial relations, this paper focuses on topologicalrelations (i.e., spatial relations that are not affected by elastic deformations), because
topological information is highly influential in people’s conceptualizations of space(Egenhofer and Mark 1995).

(a)

(b)

(c)

Fig. 1. Examples of complex arrow-containing diagrams that illustrate such dynamic processes
as (a) a workflow (Horn 1998), (b) an assembling procedure (from a LEGO® manual), and (c)geographic propagation (Barraclough 2003).

In arrow-containing diagrams, arrow symbols are typically used together withother elements. A unit of an arrow symbol and the elements that the arrow symbolrefers to (i.e., originates from, points to, or traverses) is considered a syntactic unit,
called an arrow diagram (Kurata and Egenhofer 2005a). This paper extends thisdefinition such that an arrow diagram is composed of one or more arrow symbols andthe elements to which at least one of these arrow symbols refers. These arrow-related
elements are called the components of the arrow diagram. Arrow diagrams are asubset of arrow-containing diagrams, since diagrams composed of arrow symbols
alone are included in arrow-containing diagrams, but not in arrow diagrams.
An arrow diagram that contains n arrow symbols is called an n-arrow diagram. Ifn>1, the n-arrow diagram is also called a multi-arrow diagram (Fig. 2). The scope of
this paper is to capture the meaningful structures embedded in such multi-arrow
diagrams. Our premise is that such meaningful structures are sufficiently captured bya set of spatial relations between arrow symbol pairs. For simplifying the discussion,
this paper deals with arrow symbols that neither intersect with themselves nor refer tothe same component more than once.
The remainder of this paper is structured as follows: Section 2 reviews studies
about line-line relations. Based on the formalization of topological line-line relations,
Section 3 formalizes the topological relations between two arrow symbols,
introducing two types of links that connect the arrow symbols directly or indirectly.
Section 4 observes how such topological relations influence the semantics of multiarrow diagrams. Section 5 demonstrates how this approach captures the structures andsemantics of multi-arrow diagrams, using the example in Fig. 2. Section 6 concludes
the discussion, pointing out some items for future research.

milk

1 liter

Enjoy!

2 tablespoons
40°C - 8 hours

yogurtFig. 2. An example of a multi-arrow diagram (4-arrow diagram), which illustrates the recursive
process of producing yogurt from the mixture of milk and yogurt.

2

Models of Relations between Line Segments

An arrow symbol is essentially a directed line segment. Thus, the relations between
arrow symbols are analogous to those between directed line segments, especiallythose embedded in a 2-dimensional space. Topological relations between two line
segments have been studied extensively by the AI and spatial database communities.
Allen (1983) distinguished 13 topological relations between two time intervals, which
are essentially uni-directional line segments embedded in a 1-dimensional space. The
4-intersection model (Egenhofer and Franzosa 1991) captured the topologicalrelations between two spatial objects based on the existence/non-existence ofgeometric intersections of the objects’ interiors and boundaries. The 9-intersection
model (Egenhofer and Herring 1991) extends the 4-intersection model by considering
the intersections with respect to the objects’ exteriors as well. In the 9-intersection
model, the intersections between two spatial objects A and B are concisely represented
by a 3×3 matrix (Eqn. 1), where A° , ∂A , and A− are A’s interior, boundary, andexterior, while B° , ∂B , B − are B’s interior, boundary, and exterior, respectively.
 A° ∩ B° A° ∩ ∂B A° ∩ B − 
M ( A, B ) =  ∂A ∩ B° ∂A ∩ ∂B ∂A ∩ B −  A− ∩ B° A− ∩ ∂B A− ∩ B − 



(1)

Topological relations between A and B are captured by the existence/non-existence of
these nine types of intersections. Thus, the matrices with different empty/non-empty
entries correspond to different topological relations. Although the matrix
distinguishes 29 = 512 configurations, the configurations with geometric realizations
are limited by some geometric constraints. Based on this model, Egenhofer (1994a)
identified 33 topological relations between non-directed line segments embedded in a2-dimensional space.
Another variation of the 4-intersection model distinguishes two boundaries (startand end points) of directed line segments (Hornsby, et al. 1999). In that model,
topological relations between two directed line segments A and B are represented by a
3×3 matrix (Eqn. 2), where ∂ s A , A° , and ∂ e A are A’s start point, interior, and end
point, while ∂ s B , B° , and ∂ e B are B’s start point, interior, and end point,respectively. Based on this model, Hornsby et al. (1999) identified 16 topologicalrelations between two time intervals in a cyclic time (essentially uni-directional line
segments embedded in a cyclic 1-dimensional space).
 ∂ s A ∩ ∂ s B ∂ s A ° ∩ B° ∂ s A ∩ ∂ e B 
M ( A, B ) =  A° ∩ ∂ s B
A° ∩ B°A° ∩ ∂ e B  ∂ A ∩ ∂ B ∂ A ∩ B° ∂ A ∩ ∂ B 
s
e
e
e 
 e

(2)

Clementini and di Felice (1998) introduced another model of topological relations
between two directed line segments embedded in a 2-dimensional space, calledclassifying invariants. Their model captures more detailed topological relations than
the 9-intersection model, yielding such distinctions as relations with different numberof interior-interior intersections.
Some researchers explored the relations between two line segments other than
topological relations. Schlieder (1995) defined point-set ordering in a 2-dimensional
space, with which he identified 63 order relations between two straight directed line
segments in a 2-dimensional space. Moraz et al. (2000), on the other hand, identified
14, 24, and 69 directional relations between two straight directed line segments in a 2dimensional space, based on a set of relative positions of one segment’s endpoints
seen from the other segment at three different granularities. Rentz (2001)
distinguished 26 order relations between two directed intervals (essentially two
directed line segments) in a 1-dimensional space. Nedas et al. (in press) incorporated
two metric measures, splitting ratios and closeness measures, into both the 9intersection matrix and the classifying invariants as their metric refinements,
following the premise “topology defines, metric refines” (Egenhofer and Mark 1995).

3

Topological Relations between Two Arrow Symbols

Topological relations between two arrow symbols are established by two types ofconnections between these arrow symbols. One is intersections. Two arrow symbols
may intersect with each other (Figs. 3a-b), as two line segments do. Thus, thetopological relations between two arrow symbols are partly modeled in the same way
as the relations between line segments are modeled based on their intersections.
Another type of links is common references. A common reference of two arrowsymbols is established when the arrow symbols refer to the same component(Figs. 3c-d). A common reference connects two arrow symbols indirectly through anintermediate component, while an intersection directly connects the arrow symbols.
This analogy motivates us to model the topological relations between arrow symbols
from a viewpoint of common references as well as that of intersections. In addition,
since two arrow symbols are sometimes connected by both intersections and common
references (Figs. 3e-f), the model for capturing both types of connections in a unified
way is potentially useful. Sections 3.1 and 3.2, therefore, partly model the topologicalrelations between arrow symbols based on intersections and common references,respectively, and Section 3.3 integrates the two models into a single hybrid model.

Main Gate
Temporary Gate

(a)
query
result(d)

Inspection

pass

fail

Shipping(b)

Disposal(c)
Inspection

pass

DB

fail

Shipping Disposal

(e)

(f)

Fig. 3. Examples of 2-arrow diagrams where arrow symbols are connected by (a) a head-headintersection, (b) a body-tail intersection, (c) a common reference to the label “Inspection”, (d)common references to the cell phone and database icons, (e) both a head-tail intersection and acommon reference to the landing strip icon, and (f) both a tail-tail intersection and a common
reference to the label “Inspection”.

3.1

Topological Relations Established by Intersections

An arrow symbol consists of three different parts: tail, body, and head. The tail, body,and head are the rearmost point, interior, and headmost point of the arrow symbol,
respectively. An arrow symbols corresponds to a time interval, since both are a kindof line segments with two qualitatively-different boundary points. Thus, following the
9-intersection model for time intervals (Hornsby, et al. 1999), this paper captures the
topological relations between two arrow symbols A and B based on 3×3 = 9 types of
their intersections: tail-tail, tail-body, tail-head, body-tail, body-body, body-head,
head-tail, head-body, and head-head intersections. These nine types of intersections
are concisely represented by a 3×3 matrix (Eqn. 3), where ∂ tail A , A° , and ∂ head A are
A’s tail, body, and head, while ∂ tail B , B° , and ∂ head B are B’s tail, body, and head,respectively.
 ∂ tail A ∩ ∂ tail B ∂ tail A° ∩ B° ∂ tail A ∩ ∂ head B 
M I ( A, B ) =  A° ∩ ∂ tail B
A° ∩ B°A° ∩ ∂ head B  ∂ A ∩ ∂ B ∂ A ∩ B° ∂ A ∩ ∂ B 
tail
head
head
head 
 head(3)This matrix is called the 9-intersection matrix for arrow symbols. The first, second,
and third row correspond to A’s tail, body, and head, while the first, second, and thirdcolumn correspond to B’s tail, body, and head, respectively. For example, since thetwo arrow symbols in Fig. 3b intersect only at one’s body and another’s tail, their 9intersection matrix has only one non-empty element at A° ∩ ∂ tail B .
We first capture the topological relations between two arrow symbols by theexistence/non-existence of these nine types of intersections alone. The existence/nonexistence of each type of intersections is characterized by respective empty/nonempty entries in the 9-intersection matrix (Fig. 4).

φ φ φ 
φ φ φ 
 φ φ ¬φ 

 φ φ φ ¬φ φ φ 
 φ φ φ

φ φ φ φ φ φ 
φ φ φ φ φ φ φ φ φ 
φ φ φ  φ φ ¬φ 
φ φ φ 
φ φ φ  ¬φ φ φ 
 φ φ φ
 φ φ φ



(a)

(b)

(c)

(d)

(e)

(f)

Fig. 4. The 9-intersection matrices that capture the topological relations between two arrowsymbols in Figs. 3a-f only in terms of intersections.

Although the 9-intersection matrix distinguishes 29 = 512 configurations withdifferent empty/non-empty entries, not all configurations have geometric realizations.
The head or tail of an arrow symbol is a point, which cannot intersect with more than
one part of another arrow symbol that does not intersect with itself. Since we assumed
that no arrow symbol intersect with itself, this condition leads to the following
constraint on the 9-intersection matrix for two arrow symbols:- The first column, third column, first row, and third row have at most one nonempty element.
On the other hand, the center cell (i.e., A° ∩ B° ) can freely be empty or non-empty.
Among the 512 potential configurations of matrices, only 68 configurations satisfy
this constraint (Table 1). Each of the 68 configurations corresponds to a different
topological relation between arrow symbols in terms of intersections, some of which
are shown in Fig. 5.
Table 1. Number of configurations of the 9-intersection matrices with geometric realizations.

A° ∩ B°

Empty
non-empty

Number of non-empty cells except A° ∩ B°
0
1
2
3
4
1
8
16
8
1
1
8
16
8
1
2
16
32
16
2

34
34
68

φ φ φ φ φ φ 
φ φ φ  ¬φ φ φ 
 φ φ φ
 φ φ φ



φ

φ
φ


¬φ φ 

φ φ
φ φ 

 φ φ

 φ φ
 ¬φ φ


¬φ 

φ 
φ 

 φ

 ¬φ
 φ


φ ¬φ 
φ
φ ¬φ φ 

φ

φ
φ


 ¬φ

 φ
 φ


φ

φ
φ


¬φ φ 
¬φ φ 
φ φ 

 φ

 φ
 ¬φ


¬φ 

φ 
φ 

 φ

 ¬φ
 φ


¬φ

φ φ

¬φ φ 
φ φ φ φ

¬φ φ 
φ φ 

φ
¬φ

φ

φ
¬φ

¬φ 

φ 
φ 

Fig. 5. Examples of 9-intersection matrices that represent the topological relations between two
arrow symbols in terms of intersections. Components referred by arrow symbols are not shownin this diagram.

Among the 68 topological relations, 20 relations are symmetric, while 48 relations
have a converse relation. Depending on the existence/non-existence of a body-bodyintersection, these 68 relations are divided into two halves with one-to-one
correspondences between them. For example, in Fig. 5, the upper five relations, eachwithout a body-body intersection, have one-to-one correspondences to the lower five
relations, each with a body-body intersection.
3.2

Topological Relations Established by Common References

In a 1-arrow diagram, components are located in front of, behind, or along the arrowsymbol; therefore, an arrow symbol defines three different areas where its
components can be located, called the head slot, tail slot, and body slot of the arrow
diagram (Kurata and Egenhofer 2005a) (Fig. 6). This structure is extended for multiarrow diagrams, such that each arrow symbol in a multi-arrow diagram individually
defines its three slots. Consequently, an n-arrow diagram has 3n slots. Since weassumed that an arrow symbol does not refer to the same component more than once,
the three slots of one arrow symbol cannot overlap with each other, whereas the slotsof different arrow symbols may overlap and contain the same component.
Tail slot

Body slot

Head slot

Fig. 6. Three component slots associated with each arrow symbol.

A common reference is established when two arrow symbols refer to the same
component, called the common component. If two arrow symbols, A and B, have acommon reference, their common component is contained in A’s tail, body, or headslot, as well as in B’s tail, body, or head slot. Accordingly, based on the combinationsof the slots that contain the common component, common references are classfied
into 3 × 3 = 9 types: tail-tail, tail-body, tail-head, body-tail, body-body, body-head,
head-tail, head-body, and head-head common references. These nine types ofcommon references between A and B are concisely represented, just like theirintersections, by a 3× 3 matrix (Eqn. 4), where ctail ( A) , cbody ( A) , and chead ( A) are therespective components in A’s tail, body, and head slot, while ctail (B ) , cbody (B ) , andchead (B ) are the respective components in B’s tail, body, and head slot.

 ctail ( A) ∩ ctail (B ) ctail ( A) ∩ cbody (B ) ctail ( A) ∩ chead (B ) M C ( A, B ) =  cbody ( A) ∩ ctail (B ) cbody ( A) ∩ cbody (B ) cbody ( A) ∩ chead (B )  c ( A) ∩ c ( B ) c ( A) ∩ c ( B ) c ( A) ∩ c ( B ) 
tail
head
body
head
head
 head(4)This matrix is called the 9-CR matrix for arrow symbols. Each cell shows the set ofcommon components contained in each pair of slots. For instance, since both twoarrow symbols in Fig. 3c contain Inspection in their tail slots, its 9-CR matrix has a
non-empty element at ctail ( A) ∩ ctail (B ) .

Since common references connect two arrow symbols in the same way
intersections do, the topological relations between arrow symbols are captured in asimilar way by the existence/non-existence of the nine types of common references.
The existence/non-existence of the nine types of common references is characterized
by respective empty/non-empty entries in the 9-CR matrix (Fig. 7). Although the 9CR matrix distinguishes 29 = 512 configurations with different empty/non-empty
entries, not all these configurations have geometric realizations. The head or tail slotof an arrow symbol may contain more than one component (say, an icon and its
caption), but it is unrealistic that these components belong to the different slots ofanother arrow symbol, since these components are located at the same (orundistinguishable) position pointed by the arrow symbol’s head or tail. On the other
hand, the components in the body slot of one arrow symbol can be contained in two
different slots of another arrow symbol, since these components can be located at
different positions. Since we assumed that no arrow symbol refers to the same
component more than once, the following constraint on the 9-CR matrix is derived:- The first column, third column, first row, and third row have at most one nonempty element.
This constraint is identical to that of the 9-intersection matrix for arrow symbols.
Accordingly, among the 512 potential configurations of matrices, 68 configurations
satisfy this condition. Each of these 68 configurations corresponds to different
topological relation between arrow symbols in terms of common references.
φ φ φ φ φ φ 
φ φ φ φ φ φ φ φ φ 
φ φ φ  ¬φ φ φ 
 φ φ φ
 φ φ φ

 φ φ ¬φ 
 φ φ φ  ¬φ φ φ 

φ φ φ φ φ φ φ ¬φ φ  ¬φ φ φ 
 φ φ φ
 φ φ φ



(a)

(b)

(c)

(d)

(e)

(f)

Fig. 7. The 9-CR matrices that capture the topological relations between two arrow symbols in
Figs. 3a-f in terms of common references.

3.3

Integration of 9-Intersection Matrix and 9-CR Matrix

Intersections and common references are analogous in the sense that both associate
two arrow symbols by connecting the tail, body, or head of one arrow symbol to thetail, body, or head of another arrow symbol. Intersections and common references are,therefore, generically called links. Based on the combination of the connected parts of
two arrow symbols, links are classified into 3 × 3 = 9 types: tail-tail, tail-body, tailhead, body-tail, body-body, body-head, head-tail, head-body, and head-head links.
Each type of link is further categorized into direct links (= intersections) and indirect
links (= common references).
The intersections and common references of two arrow symbols A and B are
represented by two matrices M I ( A, B ) and M C ( A, B ) , respectively. These two
matrices are easily integrated into a single 3×3 matrix (Eqn. 5), where mI ij andmC ij are the respective elements of M I ( A, B ) and M C ( A, B ) at (i, j) ( i, j ∈ {1,2,3}).

[ ]M L ( A, B ) = mL ij
φI
mL ij = CIC

if mI ij = φ

and mC ij = φ

if mI ij = ¬φ and mC ij = φ(5)

if mI ij = φ
and mC ij = ¬φ
if mI ij = ¬φ and mC ij = ¬φ

M L ( A, B ) is called the 9-link matrix for arrow symbols, because each cell of thismatrix indicates the existence of links at each position pair and their types. For
instance, the arrow symbol pairs in Figs. 3a-f correspond to the 9-link matrices in
Figs. 8a-f. A merit of this hybrid matrix is that the topological relation between two
arrow symbols is described by a single matrix even when two arrow symbols haveboth intersections and common references (Figs. 3e-f).
φ φ φ 
φ φ φ φ φ I φ φ φ I φ φ
φ φ φ C φ φ 
φ φ φ φ φ φ 

φ φ C 
φ φ φ C φ φ 

φ φ I φ φ φ φ C φ  IC φ φ 
 φ φ φ φ φ φ 

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 8. The 9-link matrices that capture the topological relations between two arrow symbols in
Figs. 3a-f in terms of both intersections and common references.

Since each cell is four-valued (φ, I, C, or IC), the 9-link matrix distinguishes
49 = 262,144 configurations, although not all configurations have geometricrealizations. The tail or head of an arrow symbol is a point and, therefore, cannot belinked to two different parts of another arrow symbol that neither intersect with itself
nor refer to the same component more than once. The tail or head of an arrow symbol,
however, may have both an intersection and a common reference with the same partof another arrow symbol (Fig. 3f). Thus, the following constraint on the 9-link matrix
is derived:- The first column, third column, first row, and third row have at most one nonempty element.
This constraint is, again, identical to that of the 9-intersection matrix for arrowsymbols. Among the 262,144 potential configurations of matrices, 1,864
configurations satisfy this condition (Table 2), each of which corresponds to adifferent topological relation. Among the 1,864 topological relations, 184 relations are
symmetric, while 1,680 relations have a converse relation.
Table 2. Number of configurations of the 9-link matrices with geometric realizations.

Number of non-empty cells except mL 22
mL 22

empty
non-empty

0
1
1×31
4

1
8×31
8×32
96

2
16×32
16×33
576

3
8×33
8×34
864

4
1×34
1×35
324

466
1,374
1,864

In this way, we developed a model for capturing topological relations between
arrow symbols in a unified way. This model is called the 9-link model for arrowsymbols. The 9-link model deals with both direct links (intersections) and indirect
links (common references) between spatial objects, whereas the 9-intersection model
deals with the direct links.

4

Topological Relations and Semantics

The meaning of multi-arrow diagrams is influenced by the arrow symbols’ relations.
Our premise is that in a multi-arrow diagram each arrow symbol illustrates atomic
semantics together with its related components and links of the arrow symbols
indicates interrelation between these atomic semantics. This section discusses whatkinds of interrelations between atomic semantics are indicated by intersections,common references, and their combinations.
Before starting the discussion, we have to be careful about the nested structure in a
multi-arrow diagram. An arrow symbol in a multi-arrow diagram sometimes refers to
an inner arrow diagram instead of individual components, thereby forming a nested
structure. In Fig. 9a, for example, the arrow symbol departing from El Niño refers not
to Fish catch, but to the inner arrow diagram composed of Fish catch and a
downward arrow symbol, which illustrates the decrease of fish catch. Accordingly,
this diagram illustrates a dynamic process that El Niño triggers the decrease of fish
catch. The use of such nested structures enriches the representation ability of multiarrow diagrams. A problem is that the existence of a nested structure is not visually
distinctive—in multi-arrow diagrams with a nested structure, arrow symbols
apparently have a common reference (Fig. 9a) or an intersection (Fig. 9b). To focus
the study on the fundamental aspects of arrow diagrams, the following discussion
only deal with multi-arrow diagrams without nested structures.
El Niño
Fish catch(a)Industrial Revolution
Rural area

Urban area

population(b)

Fig. 9. Multi-arrow diagrams with a nested structure, which apparently have (a) a common
reference to the label “Fish catch” or (b) an head-body intersection.

4.1

Semantic Roles of Intersections

If two arrow symbols have intersections but no common references, each arrowsymbol typically represents an action (i.e., movement of one component, sometimes
triggered by or/and triggering an interaction with another component), and eachintersection indicates an interrelation between such actions. In Fig. 3b, for example,
each arrow symbol represents the movement to the main gate or temporal gate. Then,the body-tail intersection between these arrow symbols indicates that the movement tothe temporal gate takes over a part of the mover to the main gate (i.e., a group ofpeople). Like this example, each type of intersection indicates the followinginterrelations:- A head-tail or tail-head intersection typically indicates that the tail-side arrowsymbol completely takes over the mover of the head-side arrow symbol (Fig. 3e).
- A body-tail or tail-body intersection typically indicates that the tail-side arrowsymbol partially takes over the mover of the body-side arrow symbol (Figs. 3b).
- A head-head intersection indicates that the movers of two arrow symbols meetand probably interact (Fig. 3a).
- A head-body or body-head intersection typically indicates that the mover of thehead-side arrow symbol may merge with or influence the mover of the body-sidearrow symbol.
- A tail-tail intersection typically indicates that the movers of two arrow symbols
move away from each other, probably as a result of a certain event.
- A body-body intersection may indicate the interaction between the movers of two
arrow symbols. Otherwise, the arrow symbols happened to cross at the bodybody intersection.
These correspondences between intersections and interrelations of actions are
summarized in a 3×3 matrix (Eqn. 9), following the structure of the 9-intersection
matrix for arrow symbols. This correspondence, however, does not mean that theexistence of each intersection always leads to the corresponding interpretation. For
instance, body-tail intersection is occasionally used to indicate alternative scenarios ofactions or events, without mentioning partial takeover.
separation partial takeover complete takeover

4.2

parital takeover
complete takeover (interaction)
merge or influence 
merge or influence meet ( +interaction) (6)Semantic Roles of Common References

If two arrow symbols have common references but no intersections, the atomic
semantics represented by these arrow symbols are inevitably interrelated in the sensethat both atomic semantics refer to the common component. For example, the two
atomic semantics of Fig. 10a—the label “Mr. K” is assigned to the traveler (which inturn is interpreted as the traveler is Mr. K) and the person goes to Hawaii (Fig. 10a’)—are interrelated in the sense that they refer to the same traveler.
In addition to such weak interrelations, the atomic semantics may be stronglyinterrelated through mutual interference. For example, Fig. 10b illustrates an exam
results in pass or fail, where its two atomic semantics, an exam results in pass and an
exam results in fail (Fig. 10b’), are mutually-exclusive (i.e., they cannot be true at thesame time). On the other hand, Fig. 10c illustrates a cell phone sends a query to a
database, which then returns a search result, where its two atomic semantics, a cell
phone sends a query to a database and a database sends a query to a cell phone(Fig. 10c’), are synchronized (i.e., whenever one is true, the other is also true). In thisway, if arrow symbols have a common reference, the atomic semantics may bemutually-exclusive or synchronized. Which type of interference actually holds cannot
be determined without background knowledge about, for example, whether theillustrated events may or must occur simultaneously. According to our observation,
however, atomic semantics tend to interfere with each other when arrow symbols are
symmetrically aligned (Figs. 10b-c). Consequently, symmetry of the 9-CR matrix
may be useful for judging the possibility of such semantic interferences.
Mr. K

Hawaii

Exam

Pass

query

Fail

resultφ φ φ 
φ φ φ C φ φ C φ φ 
φ φ φ φ φ φ 

(a)

(b)

Mr. K
Hawaii

(a’)

C
φ 
φ 

(c)

Exam

Pass

Exam

Fail

(b’)

φ φ
φ φ

C φ

DB

query

DB

DB

result(c’)

Fig. 10. (a-c) Examples of 2-arrow diagrams with common references and their 9-link matrices,and (a’-c’) inner arrow diagrams of Fig. 11a-c, which illustrate the atomic semantics of theoriginal 2-arrow diagrams.

4.3

Semantic Roles of Coexisting Intersections and Common References

If two arrow symbols have both an intersection and a common reference, whichconnect exactly at the same positions of these arrow symbols, these two types of links
work essentially as a single common reference (Fig. 3f). This is because two arrowsymbols sometimes intersect unnecessarily when referring to a common component,
and accordingly it appears that both an intersection and a common reference connect
the same positions of two arrow symbols. Consequently, when the 9-link matrix
contains IC in any cell except the center, the symbol IC can be replaced by I withoutchanging the diagram’s semantics (Fig. 8f).
On the other hand, if different positions of two arrow symbols are connected by anintersection and a common reference (i.e., the 9-link matrix has I and C in different
cells, or possibly IC in the center), these two links should have individual semanticroles. Thus, the intersection of such arrow symbols implies that these arrow symbols
illustrate the interrelated actions. For example, Fig. 3e illustrates an airplane flies
over a landing strip and then lands on it, where its head-tail intersection indicates thatthe tail-side arrow symbol completely takes over the mover of the head-side arrowsymbol (i.e., an airplane). On the other hand, the common reference of the arrowsymbols always implies the synchronization of two actions, since the actions mustoccur simultaneously or continuously in order to have an interrelation. For example,

the atomic semantics of Fig. 3e, an airplane flies over a landing strip and somethinglands on a landing strip (Fig. 11), must be synchronized such that the latter action
takes over the mover of the former actions (i.e., the airplane). In this way, thecombination of an intersection and a common reference at different positions indicatethat the arrow diagram illustrates two interrelated and synchronized actions.

Fig. 11. Inner arrow diagrams of the 2-arrow diagram in Fig. 3e.

5

An Example

Let the four arrow symbols in Fig. 2 be called A, B, C, and D, as shown in Fig. 12a.
The topological relations between pairs of these arrow symbols are represented by six
9-link matrices (Fig. 12b). Since D intersects with A and C, it is automaticallydetermined that A, C, and D individually illustrate a certain action (i.e., movement of
one component sometimes accompanying an interaction). On the other hand, B
illustrates a change of ingredients, which is not an action. The body-head intersection
between A and D indicates that D’s mover (2 tablespoons of yogurt) merges with orinfluences A’s mover (milk). Since A and B have a head-tail common reference, theirsemantics are interrelated in the sense that they refer to the same container, althoughthese semantics are not mutually-exclusive or synchronized. Similarly, B and C havea head-tail common reference, which implies an interrelation between their semantics
in terms of subject-sharing. Finally, the body-tail intersection between C and D
indicates that D partially takes over C’s mover (yogurt). This interpretation is
supported by the label on D (2 tablespoons).

Enjoy!

milk

1 literA

2 tablespoons

D
40°C - 8 hours

B
(a)

C
yogurtφ
M L ( A, B ) =  φ
Cφ
M L ( A, D ) = φφφ
M L (B, D ) = φ
φ

φ
φ
φ
φ
φ
φ
φ
φ
φ

φ
φ 
φ 
φ
I 
φ 
φ
φ 
φ 

φ
M L ( A, C ) = φφφ
M L (B, C ) =  φ
Cφ
M L (C , D ) =  I
φ

φ
φ
φ
φ
φ
φ
φ
φ
φ

φ
φ 
φ 
φ
φ 
φ 
φ
φ 
φ 

(b)

Fig. 12. (a) The 4-arrow diagram in Fig. 2 with arrow symbol identifiers A-D and (b) the 9-link
matrices representing the topological relations between pairs of these arrow symbols.

6Conclusions

People often communicate dynamic information through multi-arrow diagrams. This
paper formalized the topological relations of arrow symbols embedded in such multiarrow diagrams from two viewpoints: intersections and common references. Then, we
observed how these topological relations influence the semantics of multi-arrow
diagrams. This work forms a basis for future research toward a computational model
for interpreting complex arrow-containing diagrams. In order to achieve this goal,
further extensions are needed to detect nested structures and to determine the type ofsemantic interference implied by common references. In addition, the correspondence
between topological relations and semantics should be carefully examined with more
examples of arrow diagrams and some systematic human subject experiments.
Another item for future research is constructing an interpretation framework that maybind the relation between arrow symbols, instead of assigning a fixed semantics toeach topological relation based on examples.
Since this paper limited the target to topological relations between arrow symbols,
it should be meaningful to study the influence of other spatial relations, such as metricor directional relations, to the semantics.
Our discussions implicitly assumed that an arrow symbol always refers to theentire component. Arrow diagrams, however, sometimes have a hierarchical common
reference, where one arrow symbol refers to a component while another arrowsymbol refers to a part of the same component (Fig. 13). This setting leads to thepossibility to extend our 9-link model, which will capture more detailed topologicalrelations between arrow symbols.

Carry-onluggageFig. 13. An arrow diagram with a hierarchical common reference. The thicker arrow symbolrefers to a person carrying a bag, while the narrower arrow symbol refers only to the bag.

Another challenging problem is to analyze the conceptual neighborhoods of the
topological relations between arrow symbols that we identified and to develop theircomposition table on these relations as a basis for qualitative spatial reasoning. Suchproblems are well-studied for regions (Egenhofer 1994b, 2005), but not yet for arrowsymbols and even for directed line segments, which are often represented by arrowsymbols. The study of these problems would probably leads to the findings ofinteresting properties of the topological relations between arrow symbols.

Acknowledgments
This work was partially supported by the National Geospatial-Intelligence Agency
under grant number NMA201-01-1-2003. Max Egenhofer’s research is further
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, and the National Institute ofEnvironmental Health Sciences, NIH, under grant number 1 R 01 ES09816-01.

References
Allen, J. (1983) Maintaining Knowledge about Temporal Intervals. Communications of theACM. 26(11):832-843.
Barraclough, G. (ed.) (2003) Collins Atlas of World History. 2nd revised edition. Borders Press:
Ann Arbor, MI.
Clementini, E. and Di Felice, P. (1998) Topological Invariants for Lines. IEEE Transactions on
Knowledge and Data Engineering. 10(1):38-54.
Egenhofer, M. (1994a) Definitions of Line-Line Relations for Geographic Databases. IEEE
Data Engineering Bulletin. 16(3):40-45.
Egenhofer, M. (1994b) Deriving the Composition of Binary Topological Relations. Journal of
Visual Languages and Computing. 5(2):133-149.
Egenhofer, M. (2005) Spherical Topological Relations. Journal on Data Semantics III. 25-49.
Egenhofer, M. and Franzosa, R. (1991) Point-Set Topological Spatial Relations. International
Journal of Geographical Information Systems. 5(2):161-174.
Egenhofer, M. and Herring, J. (1991) Categorizing Binary Topological Relationships between
Regions, Lines and Points in Geographic Databases. in: Egenhofer, M., Herring, J., Smith,
T. and Park, K. (eds.) A Framework for the Definitions of Topological Relationships and an
Algebraic Approach to Spatial Reasoning within This Framework, NCGIA Technical
Reports 91-7. National Center for Geographic Information and Analysis: Santa Barbara, CA.
Egenhofer, M. and Mark, D. (1995) Naive Geography. in: Frank, A. and Kuhn, W. (eds.)
COSIT '95, Semmering, Austria, Lecture Notes in Computer Science, 988, 1-15.
Horn, R. (1998) Visual Language: Global Communication for the 21st Century. MacroVu, Inc.:
Bainbridge Island, WA.
Hornsby, K., Egenhofer, M. and Hayes, P. (1999) Modeling Cyclic Change. in: Chen, P.,
Embley, D., Kouloumdjian, J., Liddle, S. and Roddick, J. (eds.) Advances in Conceptual
Modeling, Paris, France, Lecture Notes in Computer Science, 1227, 98-109.
Kurata, Y. and Egenhofer, M. (2005a) Semantics of Simple Arrow Diagrams. in: Barkowsky,
T., Freksa, C., Hegarty, M. and Lowe, R. (eds.) AAAI Spring Symposium on Reasoning with
Mental and External Diagram: Computational Modeling and Spatial Assistance, Menlo
Park, CA, 101-104.
Kurata, Y. and Egenhofer, M. (2005b) Structure and Semantics of Arrow Diagrams. in: Cohn,
A. and Mark, D. (eds.) COSIT '05, Ellicottville, NY, Lecture Notes in Computer Science,
3693, 232-250.
Moratz, R., Renz, J. and Wolter, D. (2000) Qualitative Spatial Reasoning about Line Segments.
in: Horn, W. (ed.) 14th European Conference on Artificial Intelligence, Berlin, 234-238.
Nedas, K., Egenhofer, M. and Wilmsen, D. (in press) Metric Details of Topological Line-Line
Relations.
International
JournalofGeographical
Information
Science.
http://www.spatial.maine.edu/~max/RJ53.html.
Renz, J. (2001) A Spatial Odyssey of the Interval Algebra: 1. Directed Intervals. in: Nebel, B.
(ed.) International Joint Conference on Artificial Intelligence 2001, Seattle, WA, 51-56.
Schlieder, C. (1995) Reasoning about Ordering. in: Frank, A. and Kuhn, W. (eds.) COSIT'95,
Lecture Notes in Computer Science, 341-349.
Tversky, B., Heiser, J., Lozano, S., MacKenzie, R. and Morrison, J. (in press) Enriching
Animations. in: Lowe, R. and Schnotz, W. (eds.) Learning with animation: Research andapplication. New York: Cambridge University Press.