verse 
nd of 
>nded 
links 
nding 
» the 
nce 
lerive 
tional 
ler to 
ected 
nding 
if the 
ch 
an be 
lation 
). 
es. 
from 
g the 
vork 
)>2 
))), 
(c2). 
4.2 Elimination of Islands 
Islands are features that are irrelevant for the assessment of 
the flow direction of the river network and their existence 
would make the reasoning process more difficult. Since an 
island consists of an ordered sequence of a split and a 
junction, for a single island between two nodes V/ and V2, the 
two downstream channels from V1 to V2 can be replaced bya 
single channel from V1 to V2 (Figure 11). 
Figure 11: Simplification by eliminating islands. 
This assumes that auxiliary nodes between VI and V2 have 
been eliminated before. 
sort network (cont.) 
operation elimlIsland: network x vertex x vertex — network 
axioms — elimIsland (nl, v1, v2) == 
error if not island (nl, v1, v2) 
else remove (nl, downStreamChannell (n1, v1)) 
More complex is the issue if each channel along the island 
cannot be simplified, because both contain further junctions. 
In such cases, before eliminating a channel, its junctions have 
to be incorporated into the other branch. Since junctions on 
opposite sides of islands are partially ordered, it is impossible 
to decide which junction should come first and a random 
choice has to be made. For the inference of the flow 
directions, such simplifications should not matter. 
5 Conclusions 
This paper investigated the formalization of river networks. 
Such a formalization is necessary as a first step in the 
development of formal reasoning methods about river 
networks, e.g., to infer the flow direction. We have shown 
how the junction patterns in a river network can be mapped 
onto a directed acyclic graph. Irrelevant features, such as 
auxiliary nodes and islands, can be removed from the graph to 
make to simplify the inference process. 
While the classification of nodes based on their in-degrees and 
out-degrees is powerful, it may occasionally need user 
interaction. For example, channels may be hidden so that they 
do not appear in the data source. Such channels may be 
running naturally under ground, primarily in karst regions, or 
they may be hidden from the data collector by such obstacles 
as overhanging trees. Another possibility for channels being 
invisible is that the resolution of the data collector is too low 
to capture narrow waterways. In all cases, the natural flow of 
water continuos while the observed network is interrupted. 
323 
6 Acknowledgments 
Thanks to David Mark and Diógenes Alves for their valuable 
comments. 
7 References 
L. Band. 1986. Analysis and Representation of Drainage 
Basin Structure with Digital Elevation Data, in: D. Marble 
(ed.) Proceedings of the Second International Symposium on 
Spatial Data Handling, Seattle, WA, pp. 437-450. 
G. Birkhoff. 1967. Lattice Theory. American Mathematical 
Society, Providence, RI. 
W. Chase and M. Chi. 1981. Cognitive Skill: Implications for 
Spatial Skill in Large-Scale Environment. in: J. Harvey (ed), 
Cognition, Social Behavior, and the Environment. Lawrence 
Erlbaum Associates, Hillsdale, NJ, pp. 111-136. 
M. Egenhofer and J. Herring. 1991. High-Level Spatial Data 
Structures for GIS, in: D. Maguire, M. Goodchild, and D. 
Rhind (eds.), Geographical Information Systems: Principles 
and Applications, Volume 1, pp. 227-237, Longman, London. 
A. Frank and D. Mark. 1991. Language Issues for GIS, in: D. 
Maguire, M. Goodchild, and D. Rhind (eds.), Geographical 
Information Systems: Principles and Applications, Volume 1, 
pp. 147-163, Longman, London. 
A. Frank, B. Palmer, and V. Robinson. 1986. Formal Methods 
for the Accurate Definition of Some Fundamental Terms in 
Physical Geography, in: D. Marble (ed.) Proceedings of the 
Second International Symposium on Spatial Data Handling, 
Seattle, WA. pp. 583-599. 
A. Gill. 1976, Applied Algebra for the Computer Sciences. 
Prentice-Hall, Englewood Cliffs, NJ. 
R. Haralick, S. Wang, L. Shapiro, and J. Campbell. 1985. 
Extraction of Drainage Networks by Using the Consistent 
Labeling Technique. Remote Sensing and Environment, 
18:163-175. 
R. Horton. 1945. Erosional Development of Streams and their 
Drainage Basins: Hydrophysical Approach to Quantitative 
Morphology. Geological Society of America Bulletin, 56:275- 
370. 
D. Knuth, 1973, The Art of Computer Programming, Vol. 1 
Fundamental Algorithms, Addison-Wesley, Reading MA. 
R Larovere and S. Goodman. 1992. Computing in the 
Brazilian Amazon. Communications of the ACM, 35(4):21-24. 
D. Mark and M. Goodchild. 1982. Topologic Model for 
Drainage Networks with Lakes. Water Resources Research, 
18(2):275-280. 
M. Melton. 1959. A Derivation of Strahler's Channel-Ordering 
System. Journal of Geology, 67:345-346. 
NCGIA, 1992, NCGIA Update, 4(1):5-6, National Center for 
Geographic Information and Analysis, University of 
California, Santa Barbara.