Algorithms for River Network Analysis

Braided rivers and estuaries are examples of river networks: systems consisting of intertwined channels and bars (islands), that can behave in complex and unpredictable ways. The study of river networks is important because they play a crucial part in many environments—for example, accurately predicting when an island will be flooded can help saving lives and property. River networks form one of the key research interests in geomorphology, but so far their analysis has been carried out mostly by hand (computer-assisted). Existing research in the algorithms community generally assumes that water always follows a path of steepest descent, which prevents river channels from splitting. However, channels in river networks do frequently split and hence this fundamental assumption does not hold in general.

In this thesis, we initiate the algorithmic study of river networks by employing the so-called Morse–Smale complex on a digital elevation model of the riverbed. This complex contains information about the topological features of the riverbed, and in particular about where bars are. We extend this complex with a certain ordering of bars from one riverbank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different, we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are δ-different from each other (as measured by the sand function) is NP-hard. However, using our ordering of bars between the river banks, we can compute a maximum δ-different network that respects this order in polynomial time.

River networks can evolve quickly, and it is useful to be able to track channels and bars, that is, to determine how they change over time as the terrain moves. As a first step towards this goal, we study volume-persistence, a variant of persistence which is based on the volume underneath the terrain (instead of the usual vertex heights). Specifically, we want to kinetically maintain a volume-simplified time-varying terrain. A major challenge is to detect those combinatorial events when a pruned part of the terrain attains a certain threshold volume. Already for 1D terrains we show that the complexity of the associated certificates is strongly influenced by the motion model, since the salient volumes can be determined by linearly many vertices. Furthermore, the pruned parts of the terrain can have high complexity and may cause many irrelevant (internal) events. We present a kinetic data structure (KDS) that maintains the split tree of a volume-persistent time-varying 1D terrain, as well as an extension, that does not explicitly maintain the split tree of the pruned parts of the terrain and generally processes fewer events.

As a generalization of the sand function described above, we explore the possibilities of volume-based distance measures for linear features on a terrain. Our measures construct suitable base surfaces between the linear features, which can slice through the input terrain and also hover above. The similarity between two linear features is then captured by the volume of ‘earth’ above the base surface and below the terrain, and possibly also by the volume of ‘air’ below the base surface and above the terrain. We suggest three ways of choosing a suitable base plane and three ways of choosing a suitable base surface. These choices give rise to different measured volumes and will be useful in different applications. We experimentally compare the choices on various artificial and real terrains.

Lastly, we concern ourselves with the visualization of networks that have a particular order defined on their vertices. This includes river networks, but is also more widely applicable to any sort of networks whose elements have a defined order. A simple and natural way to draw such a network is a linear layout: all vertices are placed on a line and edges are drawn as arcs between the vertices. A drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. We present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn effectively in a specified aspect ratio, while still clearly communicating the linearity of the layout. Our algorithm allows vertices to be drawn as rectangles of specified sizes. For reasonably-sized drawings the folded layout can be computed interactively. We demonstrate our algorithm on graphs that represent process trees, a type of process model. Our algorithm arguably produces much more readable layouts than existing methods.