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

Roads are the arteries of societies. Landslides, flooding, and earthquakes may frequently damage roads, disrupt traffic flow and curtail the functioning of the road network. Where landslides damage roads, these may become impassable and drivers must detour these locations. The duration of blockage and the length of a detour route (extra time and fuel) determine largely the costs to get from one location to another. In the study by Meyer et al., we used existing data on road blocking debris flows, trigger probabilities and vehicle counts to investigate the impact of debris flows on traffic flow in Southern Norway. We used graph theory to emulate a traffic navigation system that finds the shortest detour route if a road section is blocked. This allowed us to determine road sections that are both susceptible to debris flows and that are central to the functioning of Norway’s road network. With only few roads connecting Norway’s capital Oslo and cities such as Bergen and Trondheim on the western coast, the sparse road network through the central highlands (e.g., Hardanger Vidda, Jotunheimen, Sogne Fjell) is particularly worth to look at. We find that detour routes connecting two adjacent junctions may be very long so that individual and local traffic costs can be high if eminent road sections are disrupted. Regional traffic may remain often largely unaffected by individual road blockages, as long as a good and timely information system exists that warns and reroutes travellers. Spatial clustering of debris flow events during extreme rainfalls with large spatial extent, however, may significantly increase detour routes even for regional traffic.

Meyer, N.K., Schwanghart, W., Korup, O., Nadim, F. (2014): Roads at risk – traffic detours from debris flows in southern Norway. Nat. Hazards Earth Syst. Sci. Discuss., 2, 6623-6651. [DOI: 10.5194/nhessd-2-6623-2014]