A Strategy for Drawing a Conceptual Neighborhood
Graph SchematicallyYohei Kurata
SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
ykurata@informatik.uni-bremen.de

Abstract. Conceptual neighborhood graph is a network diagram that
schematizes a set of spatial/temporal relations. This paper proposes a strategy
for arranging the relations in a diagrammatic space such that the graphhighlights the symmetric structure of the relation set.

1.

Introduction

Conceptual neighborhood graph (CNG) [1] is a diagram in which spatial/temporal
relations (or potentially any set of concepts in a certain domain) are networked basedon their similarity. A number of CNGs has been developed for various relation sets
(e.g., [1-6]) and its usefulness for schematizing relations has been reported repeatedly,
because well-designed CNGs highlight the symmetric structures of the relation sets.
However, how to design such schematic CNGs is not well discussed except thedefinitions of neighbors. Thus, this paper proposes a strategy for arranging therelations in a diagrammatic space such that the CNG becomes schematic.

2.

A Drawing Strategy

In a CNG, each node corresponds to a relation and each link indicates a pair ofconceptual neighbors. Typically, two relations are considered conceptual neighbors if
an instance of one relation can be transformed into an instance of another relation by acontinuous transformation (e.g., sliding a part of one object). The nodes (i.e.,relations) are arranged in a diagrammatic space under the following conventions:• the number of crossing links becomes as small as possible;• the nodes are arranged in a linear or reticular pattern as much as possible; and• the pairs of symmetric relations are located at symmetric locations.
As for the third convention, for instance, in the CNG for topological relations between
two simple regions embedded in a spherical surface C1 (Fig. 1d) [4], every pair ofsymmetric relations, derived from each other by exchanging the interior and exteriorof one region (e.g., Fig. 1a), is located symmetrically with respect to the horizontal
axis. Similarly, in the CNG for topological relations between a directed line (arrow)

2Yohei KurataBA'≡

A' BB’s interior
B’s boundary
B’s exterior

A B

B’s interior
B’s boundary
B’s exterior

and a region [6], every pair of relations, derived from each other by exchanging theline’s direction, is located symmetrically with respect to the middle-height plane. If
the relations are modeled by the 9-intersection [7] or its relative models (e.g., [3, 5,6]), such symmetric pairs of relations are represented by similar patterns of icons withtwo exchanged rows or columns (Fig. 1a) and thus the pairs are easily identified.
Based on this observation, we propose the following strategy for drawing a CNG:
Step 1: Determine neighbors among the given set of relations R (Fig. 1b). Under the9-intersection or its relative models, the candidates for such neighbors are determined
computationally based on the similarity of the relations’ iconic patterns [2, 5, 6].
Step 2: Determine one or two concepts of symmetry Ci (e.g., exchanging the interior
and exterior of one region, exchanging the line’s direction, etc.).
Step 3: For each Ci, identify R’s subset Ri that is self-symmetric with respect to Ci.
Then, among the relations in I Ri , identify the relation r* that has the largest numberof neighbors, and put r* at (0, 0, 0). In our example, r* is overlap relation (Fig. 1c),since this relation holds even if we exchange the interior and exterior of each region.
Step 4: Locate the relations in R1\{r*}, if they exist, on the x-axis at (a, 0, 0) (a∈Z),
such that the length of each link between the relations in R1 becomes two. Leave therelations without any link. In a similar way, locate the relations in R2\{r*} on the yaxis, if they exist. In our example, both R1\{r*} and R2\{r*} are empty.
Step 5: Locate all other relations at (a, b, 0) (a, b∈Z), such that:• each relation is located at equal distance from its neighbors, whenever possible;• the remaining relations in R1 and R2 are located on x- and y- axes, respectively;• symmetric relation pairs with respect to C1 and C2 are located symmetrically withrespect to x- and y-axes, respectively (e.g., meet and covers relations in Fig. 1c).

A'’s interior
A'’s boundary
A'’s exterior

A’s interior
A’s boundary
A’s exterior(a)(b)zyÅequalÅcoversÅoverlapxÅmeetattachesÆ

(c)

(d)

Fig. 1. (a) Icons of two symmetric relations, (b) neighboring pairs of relations, and (a-b) CNGs
for topological relations between two simple regions in C2 before and after Step 7.

A Strategy for Drawing a Conceptual Neighborhood Diagram Schematically3

Step 6: If two or more relations are located at the same point, then relocate them to(a, b, c) (c∈Z) such that the links do not intersect with each other and the links’ total
length becomes the smallest. In our example, equal and attaches relations, which areplaced originally at (0, 0, 0) in Step 5, are relocated to (0, 0, ±1) by this rule (Fig. 1c).
Step 7: If preferable, reduce the dimension of the CNG by continuous transformation
while avoiding the creation of intersecting links as much as possible. In our example,
we obtain the two-dimensional CNG in Fig. 1a from the CNG in Fig. 1b by rotating
its right half (x > 0) by 180 degree and its middle vertical plane (x = 0) by 90 degree.

3.

Conclusions

This paper proposed a strategy for arranging relations in a CNG by which symmetricproperties of the relation set are highlighted. We already confirmed the applicabilityof this strategy to various sets of topological relations, including 13 interval relations
in a linear time frame [8], 16 interval relations in a cyclic time frame [3], 8 regionregion relations in R2 [7], 11 region-region relations in C2 [4], 26 arrow-region
relations in R2 [6], and 80 arrow-arrow relations in R2 [5] (a slight techniquenecessary), as demonstrated in our poster. It is left for a future research to examine theapplicability of this strategy to other sets of relations, including more complicatedtopological relations (e.g., those between two regions with holes) and non-topologicalrelations (e.g., directional relations). In addition, given an arbitrary set of relations,
their neighborhood information, and all symmetric pairs among them, how to design aschematic CNG in a fully automated way is an interesting future challenge.
References
1. Freksa, C.: Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence 54, 199227 (1992)
2. Egenhofer, M., Al-Taha, K.: Reasoning about Gradual Changes of TopologicalRelationships. In: Frank, A., Campari, I., Formentini, U. (eds.): Theories and Methods ofSpatio-Temporal Reasoning in Geographic Space, LNCS, vol. 639, pp. 196-219. Springer(1992)
3. Hornsby, K., Egenhofer, M., Hayes, P.: Modeling Cyclic Change. In: Chen, P., Embley, D.,
Kouloumdjian, J., Liddle, S., Roddick, J. (eds.): Advances in Conceptual Modeling, LNCS,
vol. 1227, pp. 98-109. Springer (1999)
4. Egenhofer, M.: Spherical Topological Relations. Journal on Data Semantics III 25-49 (2005)
5. Kurata, Y., Egenhofer, M.: The Head-Body-Tail Intersection for Spatial Relations between
Directed Line Segments. In: Raubal, M., Miller, H., Frank, A., Goodchild, M. (eds.):
GIScience'06, LNCS, vol. 4197, pp. 269-286. Springer (2006)
6. Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a
Directed Line Segment and a Region. In: Gottfried, B. (ed.): 1st International Symposiumfor Behavioral Monitoring and Interpretation, pp. 62-76 (2007)
7. Egenhofer, M., Herring, J.: Categorizing Binary Topological Relationships between
Regions, Lines and Points in Geographic Databases. In: Egenhofer, M., Herring, J., Smith,T., Park, K. (eds.): NCGIA Technical Reports 91-7. NCGIA, Santa Barbara, USA (1991)
8. Allen, J.: Maintaining Knowledge about Temporal Intervals. Communications of the ACM
26, 832-843 (1983)