# Graph theory

### Stream networks and graph theory

Posted on Updated on

Rivers are organized as networks. They start out as small rills and rivulets and grow downstream to become large streams unless water extraction, transmission losses or evaporation dominate. In terms of graph theory, you can think of stream networks as directed acyclic graphs (DAG). The stream network of one drainage basin is a tree routed at the outlet. To be more precise, this kind of tree is an anti-arborescence or in-tree, i.e. all directions in the directed graph lead to the outlet. Usually, stream networks are binary trees, i.e. there is a maximum of two branches or parents entering each node. However, nodes may sometimes have more than two branches at confluences where three and more rivers meet. All drainage basins form a forest of trees and each tree is a so-called strongly-connected component.

Why bother with the terms of graph theory? Because it will make a couple of TopoToolbox functions much more accessible. The function klargestconncomps, for example, has an awkward name that I adopted from graph theory. What does it do? It extracts the k largest trees from a stream network. The function STREAMobj2cell takes all trees and puts each into a single element of a cell array. FLOWobj2cell does the same for an entire flow network. The computational basis of STREAMobj and FLOWobj relies on topological sorting of directed graphs. Thanks to graph theory, this trick makes flow-related computations in TopoToolbox much faster than in most common GI-systems.

Graph theory has a lot to offer for geomorphometry and I think that this potential has not yet fully been explored.

### Graph theory in the Geosciences

Posted on Updated on

In a recent paper, Tobias Heckmann, I and Jonathan Phillips reviewed applications of graph theory in geomorphology. In a now published paper in Earth-Science Reviews, we take an even broader view by looking at graph theoretical applications in the geosciences in general. Specifically, we reviewed three areas of application: spatially explicit modelling, small-world networks, and structural models of Earth surface systems. We identify several factors that make graph theory especially well suited to the geosciences: inherent complexity of Earth surface systems, the increasing demand for exploration of very large data sets, focus on spatial fluxes and interactions, and the increasing attention to system state transitions.

Phillips, J.D., Schwanghart, W., Heckmann, T. (2014): Graph theory in the geosciences. Earth Science Reviews, 143, 147–160. [DOI: 10.1016/j.earscirev.2015.02.002]

### New paper out in Geomorphology

Posted on Updated on

The mathematical branch that deals with networks is called graph theory. No wonder, that TopoToolbox that deals with river and flow networks has strong relations to graph theory. Indeed, many computational tricks adopted in TopoToolbox to increase the speed of deriving flow related terrain attributes (e.g. flow accumulation) are rooted in graph theoretic algorithms such as topological sorting. Yet, there is much more to learn from graph theory for diverse applications in geomorphology. Tobias Heckmann, me and Jonathan D. Phillips have written a review paper about these applications, and the manuscript has just now been accepted by the journal Geomorphology. The manuscript reviews all sorts of graph theory applications in geomorphology including the analysis of system structures and the analysis of spatially explicit networks. Have fun reading. If you don’t have access to the journal, I am happy to send you a pdf-copy.

Heckmann, T., Schwanghart, W., Phillips, J.D. (2014): Graph theory – recent developments of its application in geomorphology. Geomorphology, accepted. [DOI: 10.1016/j.geomorph.2014.12.024]

### New paper out in Natural Hazards and Earth System Sciences Discussions

Posted on Updated on