Email: jwo@soi.city.ac.uk

Key words: DEM, Surface Topology, Weighted Surface Network, Drainage Network, Graph Theory

This paper presents a new method for the identification of surface topology from Digital Elevation Models (DEMs), based on the graph-theoretic approaches originally suggested by Pfaltz (1976) and Wolf (1984). Surface topology is stored as a weighted graph consisting of vertices representing the so-called surface-specific points (peaks, passes, and pits; Fowler and Little, 1979), and edges representing connecting ridges and channels. This form of representation offers several improvements over other surface topological models, such as TINs and drainage networks. Surface networks are amenable to automated generalisation through a process known as homomorphic contraction. This allows a degree of importance to be attached to both point (peak, pit and pass) and line (ridge and channel) features on a surface. The removal of relatively unimportant parts of the network results in the automated readjustment of the remains of the network.

Although weighted surface networks were proposed as a way of storing and manipulating surface topology over two decades ago, to date there has never been a satisfactory method implemented for their automated construction. Previous papers such as those by Pfaltz (1976) and Wolf (1984) based discussion around networks manually-derived from contour representations of surfaces. This paper includes a discussion of some of the computational issues that have previously prevented automated construction of surface networks, and presents a new automated method that may be applied to DEMs. It is based on the use of quadratic models of conic sections to generate the morphometric information about a surface (Wood, 1998). This information is then used iteratively to build up a logically consistent surface network. The results of the process are visualised in two and three dimensions and the effects of different generalisation criteria on the network are compared. Initial results suggest that this method could provide a new and powerful way of generalising surface models while retaining their most important topological characteristics. Further work is needed in the automated embedding of surface topology back into geometrical representations of surfaces.

**References**

Fowler, R.J. and J.J. Little, 1979, Automatic extraction of irregular
network digital terrain models. *Computer Graphics ***13**, pp.199-207.

Pfaltz, J. L., 1976, Surface networks. *Geographical Analysis*
**8**(1), pp.77-93.

Wolf, G.W., 1984, A mathematical model of cartographic generalization.
*Geo-Processing* **2**, pp.271-286.

Wood, J.D., 1998, Modelling the continuity of surface form using Digital
Elevation Models. *Proceedings of the 8th International Symposium on
Spatial Data Handling,* pp.725-36.