ensed 
oning 
that it 
ctions 
of the 
esses, 
ent 
rks 
91; 
ice 
on, 
the 
his 
dal 
1ly 
1ge 
nel 
ton 
9). 
am 
of 
Oy 
ely 
tial 
of 
nel 
al. 
gle 
ind 
and 
ion 
ule 
ids, 
82) 
ical 
sa 
and 
describes an ontology for reasoning about flow directions in 
river networks. The river network features will be formalized 
in terms of a graph data model. Such an approach is a 
prerequisite for developing robust methods to infer the flow 
direction of a (partial) river network. For example, it is 
necessary to identify islands in a river network, because for 
them the "most acute angle" rule infers contradicting 
directions for the "start" and the "end" of an island. 
The remainder of this paper is structured as follows: Section 2 
introduces some notions from graph theory. Section 3 
describes fundamental river patterns and shows their abstract 
representations as graphs. Section 4 analyzes these graphs and 
draws some conclusions about simplifications of river 
patterns, without losing information necessary for a formal 
reasoning process about flow directions. The conclusions in 
Section 5 discuss future work. 
2 Graphs 
The formal basis for modeling river networks is the 
mathematical structure of a graph. Graphs have been 
investigated extensively in computer science and applied 
mathematics. The following fundamental definitions are based 
on Knuth (1973) and Gill (1976). 
A directed graph, or di-graph, is a set of vertices and a set of 
arcs where each arc leads form a vertex V to a vertex V'. V and 
V' are also called respectively the initial and final vertex of an 
arc e. The orientation of an arc is an equivalence class, 
defined as a positive value from the initial vertex zo the final 
vertex, and negative in the reverse direction. The out-degree 
of a vertex V is the number of arcs leading out from it, i.e., the 
number of arcs e, whose initial vertex is V. Conversely, the in- 
degree of V is the number of arcs whose final vertex is V. The 
degree of a vertex V is then the sum of the in-degree and out- 
degree of V. 
A directed graph will be depicted as a sequence of nodes (for 
the vertices) and edges between the nodes (for the arcs). The 
orientation of each arc will be represented by an arrow 
pointing from the node for the initial vertex to the node for the 
final vertex (Figure 1). 
  
Figure 1: A directed graph. 
Given a set of arcs fe], e2, ..., eg, «e], e2, .., eg» is an 
oriented path of length n from V to V' if (1) V is the initial 
vertex of el, (2) V' is the final vertex of ej, and (3) the final 
vertex of any ek (1 € k « n) is equal to the initial vertex of ej's 
adjacent arc e(k+]). The length 1 of an oriented path is the 
number of arcs along the path. A path «e], e2, .., en» isa 
loop if the initial vertex of e] coincides with the final vertex 
of en.. A loop is called a cycle if the initial vertices of all arcs 
in the path are distinct. Based on the concept of a cycle, two 
specific kinds of graphs are defined: (1) A multi-graph is a 
319 
graph in which cycles of length 2 are permitted, i.e., two 
vertices can be linked by more than one edge, and (2) a di- 
graph without cycles is a directed acyclic graph or dag. 
An ordinary graph GQ abstracts from a directed graph G the 
orientations of the arcs. Thus, Go has an edge between V and 
V'if G has an arc either from V to V' or from V' to V. Two 
vertices, V and V' in an ordinary graph are connected if there 
exists a path between V and V". Reversely, two vertices, V and 
V' are disconnected if there exists no path that connects V with 
V. if V] *Gorand V2 Goj are disconnected, then the two 
graphs Go; and Goj are disconnected as well. 
3 River Junction Patterns 
The identification of possible node configurations in a river 
network is an important step in the chain of reasoning about 
the network's flow direction. An example of a drainage pattern 
is shown in Figure 2. 
  
Figure 2: A drainage pattern. 
Such channel patterns can be constructed from a small set of 
some basic river junction patterns. This paper focuses on the 
formalization of the most common river junction patterns as 
they are formed by channels, islands, and lakes. For the time 
being, we exclude such river features as waterfalls or dams, 
although their recognition and inclusion into out model may 
be an additional source of information for the inference of 
flow directions. 
3.1 Channels 
Channels are ways along which fluvial processes act to 
transport water and minerals out of a local region. In our 
model of river networks, a channel is a connected segment of 
a river between two distinct nodes. These nodes may be 
metrically significant points, such as sharp turns, or 
topologically significant landmarks, such as a source, a 
destination, or a junction. Each channel has a flow direction 
"upstream" or "downstream," which corresponds to the natural 
flow direction of the water. It is assumed that this flow 
direction is constant for each channel, i.e., that it does not 
change periodically. 
Each channel maps onto an arc of a di-graph, with the flow 
direction of the channel being represented by the orientation 
of the arc. This mapping abstracts quantitative differences in 
length and shape of a channel. On the other hand, it preserves 
such qualitative information as the connectivity and the flow