# River landscapes and optimal channel networks

^{a}Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152;^{b}Department of Mathematics, University of Illinois, Urbana, IL 61801;^{c}Dipartimento di Scienze Ambientali e Informatica, Università Cà Foscari Venezia, 30123 Venice, Italy;^{d}Trinity College, Cambridge CB2 1TQ, United Kingdom;^{e}London Institute for Mathematical Sciences, London W1K 2XF, United Kingdom;^{f}Networks Unit, IMT (Istituzioni, Mercati, Tecnologie) School for Advanced Studies Lucca, 55100 Lucca, Italy;^{g}Institute of Complex Systems, Consiglio Nazionale delle Ricerche, 00185 Rome, Italy;^{h}European Centre for Living Technology, Università Cà Foscari Venezia, 30124 Venice, Italy;^{i}Dipartimento di Fisica e Astronomia, University of Padua, 35122 Padua, Italy;^{j}Istituto Nazionale di Fisica Nucleare, University of Padua, 35122 Padua, Italy;^{k}Instituto de Matemática Pura e Aplicada, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil;^{l}Laboratory of Ecohydrology, École Polytechnique Fédérale de Lausanne, Lausanne CH-1015, Switzerland;^{m}Dipartimento di Ingegneria Civile, Edile e Ambientale, University of Padua, 35122 Padua, Italy

See allHide authors and affiliations

Contributed by Andrea Rinaldo, May 10, 2018 (sent for review March 14, 2018; reviewed by Armaghan Abed-Elmdoust, Angelika Steger, and Ramarathnam Venkatesan)

## Significance

Optimal channel networks (OCNs) are a well-studied static model of river network structures. We present exact results showing that every OCN is a natural river tree where a landscape exist such that the flow directions are always directed along its steepest descent. We characterize the family of natural river trees in terms of certain forbidden structures, called “k-path obstacles.” We thus determine conditions for river landscapes to imply a rooted tree as its network of topographic gradients. Our results are significant in particular for applications where OCNs may be used to produce statistically identical replicas of realistic matrices for ecological interactions.

## Abstract

We study tree structures termed optimal channel networks (OCNs) that minimize the total gravitational energy loss in the system, an exact property of steady-state landscape configurations that prove dynamically accessible and strikingly similar to natural forms. Here, we show that every OCN is a so-called natural river tree, in the sense that there exists a height function such that the flow directions are always directed along steepest descent. We also study the natural river trees in an arbitrary graph in terms of forbidden substructures, which we call k-path obstacles, and OCNs on a d-dimensional lattice, improving earlier results by determining the minimum energy up to a constant factor for every

River networks can be viewed as rooted trees that, when extracted from fluvial landscapes by topographic steepest descent directions, show deep similarities of their parts and the whole, often across several orders of magnitude, despite great diversities in their geology, exposed lithology, vegetation, and climate (1). The large related body of observational data provides quintessential examples of real physical phenomena that can be effectively modeled by using graph theory (2, 3). River networks are in fact the loopless patterns formed by fluvial erosion over a drainage basin. Such patterns, referred to as “spanning trees,” are such that a directed graph route exists for flows from every site of the catchment to an outlet and are strictly related to the topographical surface whose gradients determine the edges (the drainage directions). A specific class of spanning trees, called optimal channel networks (OCNs), was obtained by minimizing a specific functional (4, 5), later shown to be an exact property of the stationary solutions of the general equation describing landscape evolution (6, 7). The static properties and the dynamic origins of the scale-invariant structures of OCNs proved remarkable (1). OCNs are suboptimal (that is, dynamically accessible given initial conditions and quenched randomness frustrating the optimum search) configurations of a spanning network mimicking landscape evolution and network selection (*SI Appendix*). Empirical and theoretical works have generally focused on the two-dimensional (2D) case, although recently (inspired by vascular systems), three-dimensional (3D) settings have also been analyzed for an OCN embedded in a lattice (8). Several exact results have been derived for OCNs (6⇓⇓⇓⇓⇓⇓⇓⇓–15).

A model for a river network is obtained by taking a reasonably dense set of points on a terrain and then joining each point to a nearby point downhill. Experimental observations suggest that OCNs should satisfy the following properties: (*i*) each portion of the drainage basin has a single output; and (*ii*) a geomorphological stability condition holds. OCNs are defined on a finite graph G, consisting of a set

Here, we present analytical results about the properties of the structure that minimizes the total gravitational energy loss. In particular, we will give a theoretical characterization of river networks in terms of forbidden substructures, which provides a simple way of determining which of the spanning trees of a graph are natural river trees. We will also study OCNs embedded in a d-dimensional lattice, proving, for each dimension

For each constant **1** is called an OCN of G.

In the case of river networks, if we imagine an open system where injection occurs at each site (vertex) at rate 1, and flowing along the edges of T until it reaches the root, then **1** has its origins in the exact result that steady-state configurations of river networks minimize the total loss of gravitational energy. This corresponds to:**1**. When **1** is replaced by a more general one where T is substituted with the graph G itself, including all edges. For such functional, every tree is a local minimum (7), and minimization is carried out under the constraint that locally (for each node) and globally a conservation law holds matching injection rates and inflows/outflows (6, 7, 16).

Given a rooted graph G (with one or more roots), we say that T is a “rooted spanning forest” of G if T is an acyclic subgraph of G, with one root of G in each component of T, and all edges oriented toward the corresponding root. The following natural definition will play an important role in our investigation of the OCN(s) of a graph.

### Definition.

Let G be a rooted graph, and T be a rooted spanning forest of G. We say that T is a “natural river spanning forest” of G if there is a height function

We will assume throughout that the values of f are distinct, and hence that the minimum in Eq. **4** occurs at a unique vertex x. We remark that we will usually be interested in the case when G has exactly one root, in which case we say that T is a “natural river spanning tree” of G.

Note that (*i*) every nonroot vertex of T has out-degree exactly 1, (*ii*) *iii*) the function f attains its minimum at one of the roots. In *Theorem 1*, we will provide a simple characterization of the natural river spanning trees of a graph in terms of forbidden substructures. We will also show (*Theorem 3*) that every OCN in a graph is also a natural river spanning tree of that graph. As a consequence, to study (either analytically or numerically) the tree structures that minimize the energy function **1**, it suffices to consider natural river trees.

### Which Networks Are River Trees?

The definition of a natural river spanning tree creates various constraints on its possible shape and structure; in this section we shall consider these constraints.

### Definition.

Let G be a rooted graph, and let T a spanning tree of G. A k-path obstacle for T consists of a sequence of directed paths

In other words, if

It is not difficult to show that a natural river tree cannot contain a k-path obstacle for any

### Theorem 1.

*Let* G *be a finite graph with a single root. A spanning tree* T *of* G *is a natural river spanning tree of* G *if, and only if, it has no path obstacle.*

Looking at Fig. 1, it may be deduced that a natural river tree by definition cannot contain any three-path obstacle (i.e., cannot contain the red dashed edges). The same reasoning can be extended to any natural river tree and value of k. We will give here only a formal proof of the necessary and sufficient conditions for T to be a natural river network.

### Proof.

We will show first that, for each

We now turn to our main task: showing that if T has no path obstacle, then it is a natural river tree. Given such a rooted spanning tree T in G, we introduce a directed graph D with vertex set

### Claim.

*The directed graph* D *is acyclic.*

### Proof.

Suppose that D contains a directed cycle with exactly k edges that are not edges of T, and note that

It follows from the claim that the directed graph D can be extended to a linear ordering < on

Indeed, let *Theorem 1*.□

Recall that an OCN (with parameter γ) in a graph G is a spanning tree of G that minimizes the energy

### Theorem 2.

*Let* G *be a finite graph with a single root, let* T *be a spanning tree of* G*, and let* *and* *. If* T *is an OCN in* G *with parameter* γ*, then* T *does not contain a* k*-path obstacle.*

The proof of this theorem is presented in *Materials and Methods*. *Theorems 1* and *2* immediately imply the following fundamental fact.

### Theorem 3.

*Every OCN is a natural river spanning tree.*

In other words, if G is a finite graph with a single root, and T is an OCN in G with parameter *Theorem 2*, and hence, by *Theorem 1*, is a natural river spanning tree of G.

### Energy of OCNs in d-Dimensional Grids.

Here, we will study in more detail the energy of an OCN in a d-dimensional lattice. In particular, we will focus on the case of the d-dimensional grid

### Theorem 4.

*For every integer* *, we have**as*

### Proof.

Let us first prove the upper bounds, which follow from a straightforward recursive construction. We may assume for simplicity that

We claim that the subtree **8** is an increasing geometric series, so

We next turn to the lower bounds. Observe first that the lower bound

For the other lower bounds, we will find it useful to work in a more general setting, assuming for simplicity that

To prove Eq. **9**, we partition **9** (Fig. 3).

Setting

An interesting (and likely difficult) challenge would be to decrease the implicit constant factors between the upper and lower bounds in *Theorem 4* to factors of

## Discussion

When one considers only the structure of the network (without imposing a height function on the vertices), the requirement that a river network at stationarity minimizes total energy dissipation takes a simple and elegant form: We need to minimize the function

We have studied the energy and the structure of the OCN (the tree that minimizes Eq. **10**), first on a general graph and then (in more detail) for the particular case of a discrete lattice (Fig. 4 and *SI Appendix*). Every OCN is a natural river tree, meaning that there exists a height function which determines the tree, and we characterized the natural river trees of a graph in terms of forbidden substructures. In the case of a d-dimensional lattice, we determined the energy of the OCN up to a constant factor for every

We have also verified that, while it is natural to expect that any OCN on a discrete lattice should take the highly symmetric form of a Peano structure (1, 21), this is in fact not the case: For example, on the square lattice, several suboptimal minimum energy structures are obtained by breaking the Peano structure symmetry (1) (*SI Appendix*). Much effort has been devoted to reconciling the features of the ground state (known exactly since ref. 10) with those of feasible configurations. The resulting exponents associated with the global minimum did not match either the observational data or the numerical simulations (1). Because every local minimum of the OCN functional is a stationary solution of the general landscape evolution equation, any self-organization of the fluvial landscape corresponds to the dynamical settling of optimal structures into suboptimal niches of their fitness landscape. Thus, feasible optimality (i.e., the search for optima that are accessible to the dynamics given the initial conditions and path obstacles) is the rule in the fluvial landscape, and this might apply to a broad spectrum of interfaces in nature (16). Different network shapes give different values of

As stated previously, great interest is placed in OCN on general graphs. In a first application of the theorems presented here, we have addressed the constructability of elevation fields and topographies compatible with the planar imprinting of OCNs (Fig. 4 and *SI Appendix*). Such results imply the possibility of building replicas of statistically identical matrices for ecological interactions. This is due to the flexibility of random search algorithms in a “greedy” mode (*SI Appendix*), that cannot access the absolute minimum but rather suboptimal configurations that are known to reproduce accurately, differently from the ground state, those of natural fluvial landforms forms (16). Interestingly, an application of limit scaling properties as a test of optimality has been proposed for foodwebs (22) and a direct use of OCN landscapes has been made to explain elevational gradients of biodiversity (17).

## Materials and Methods

### Proof of *Theorem 2*.

Let T be an OCN in G with parameter γ, and suppose (for a contradiction) that T contains a path obstacle. Let k be minimal such that there is a k-path obstacle in T, so there exist paths

Now, for each

To show that

We next bound **1**. Moreover, we have **11** that**12**, and the fact that **14**, we obtain

## Acknowledgments

P.B. and B.B. are partly supported by NSF Grant DMS 1600742. J.B. is partly supported by NSF Grant DMS-1500121 and an Arnold O. Beckman Research Award (University of Illinois Urbana–Champaign Campus Research Board 15006). B.B. and G.C. are partially supported by MULTIPLEX Grant 317532. R. Morris is partially supported by Brazilian National Council for Scientific and Technological Development Grant 303275/2013-8, Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro Grant 201.598/2014, and European Research Council (ERC) Starting Grant 680275 MALIG. A.R. and E.B. have been supported by ERC Advanced Grant RINEC 22761. Part of the research in this paper was carried out while J.B. was a Visiting Fellow Commoner at Trinity College, Cambridge.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. Email: andrea.rinaldo{at}epfl.ch.

Author contributions: P.B., J.B., B.B., and R. Morris obtained the mathematical proofs; and P.B., J.B., E.B., B.B., G.C., A.M., R. Mastrandrea, R. Morris, and A.R. determined the problem, discussed the results, and wrote the paper.

Reviewers: A.A.-E., University of Texas at Austin; A.S., ETH Zurich; and R.V., Microsoft Research Redmond.

The authors declare no conflict of interest.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1804484115/-/DCSupplemental.

- Copyright © 2018 the Author(s). Published by PNAS.

This open access article is distributed under Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND).

## References

- ↵
- Rodríguez-Iturbe I,
- Rinaldo A

- ↵
- Bollobás B

- ↵
- Bollobás B

- ↵
- ↵
- Rinaldo A, et al.

- ↵
- ↵
- ↵
- Briggs LA,
- Krishnamoorthy M

- ↵
- ↵
- ↵
- ↵
- Colaiori F,
- Flammini A,
- Maritan A,
- Banavar JR

- ↵
- ↵
- Santambrogio F

- ↵
- Abed-Elmdoust A,
- Singh A,
- Yang Z

- ↵
- Rinaldo A,
- Rigon R,
- Banavar JR,
- Maritan A,
- Rodriguez-Iturbe I

- ↵
- Bertuzzo E, et al.

- ↵
- Abed-Elmdoust A,
- Miri M,
- Singh A

- ↵
- ↵
- Dhar D,
- Majumdar S

- ↵
- Flammini A,
- Colaiori F

- ↵

## Citation Manager Formats

## Article Classifications

- Physical Sciences
- Applied Mathematics