Course:EOSC311/2026/Applications of Graph Theory in Geology

Overview

Graph theory is a foundational method of modeling mainly rooted in computer science. There are many real world applications of graph theory outside of computer science in modeling both man-made and natural systems, especially when there is importance on relating many quantifiable subjects. In particular, this page explores many of these applications in geoscience or those that have potential to be applied to geological subject matter. Graph theory can be dated to as far back as 1736, but as with many theories it is continuously evolving and its applications expand as increased computing power becomes more widely accessible. This is reflected in this wiki page as multiple applications have potential but are yet to be explored. Deeper exploration into these applications can increase efficiency in complex systems, help predict and mitigate natural disasters, and assist in analyzing the present to understand the past.

Statement of Connection

As students in computer science and electrical engineering, we decided to focus our attention on the applications of algorithms in the field of geoscience. Many modern day techniques in geology employ strategies like machine learning and data mining to tackle problems like earthquake forecasting. However, we wanted to explore the uses of traditional algorithms that may be more familiar to the average student in this field, especially since students in electrical engineering may have limited exposure to concepts in machine learning. Graphs are a core subject in the data structures and algorithms curriculum, and have extensive applications in route optimization and network analysis. They are also used in geosciences to model water flow, landscape evolution, and geomorphology. Overall, we wanted to get a better understanding of how techniques developed by computer scientists have been adopted by researchers in other fields and the kinds of problems that they can help solve.

What is graph theory?

Figure 1: Visualization of a graph with nodes (vertices) and edges (links) (Duane Q. Nykamp, 2013)

Graph theory defines the concept of a “graph” - but it’s not the type of graph that visualizes data on two axes that you might be thinking of. Graphs are one of the simplest ways to represent relationships between objects, typically networks. A classic example that is used to understand graph theory is a road network between cities. Graphs are made of two types of components - vertices/nodes and edges. In our example, each city is a vertex, and each road between a pair of cities is an edge. When a graph is drawn, vertices are typically represented as circle outlines and edges are represented by lines between vertices; the position of each vertex in the drawing does not matter and only affects how easy the graph is to interpret for the viewer.

The road network example uses the simplest type of graph, an undirected graph. In an undirected graph, all edges are bidirectional. This type of graph is suitable because a car can travel between a connected pair of cities in either direction. However, what if you wanted to model the water system of a continent with a graph, where bodies and sources of water are vertices and rivers are edges? Water always flows downward, so bidirectional edges will not do. Instead, we need a directed graph, which is one where each edge points towards one of the nodes in the pair. The same pair of nodes can have two edges pointing in opposite directions between them, so representing bidirectional relationships is still possible. In this example, each edge would point in the same direction that the river is flowing.

Besides directionality, edges can have another property - weight. This is simply a number assigned to each edge in the graph. In the road network scenario from earlier, it would be reasonable to set weights to the distance between cities, or the average amount of time it takes to get between them by car.

Now that we have a graph, what do we actually do with it? Even just displaying a graph can be a useful way to grasp a network as real-life networks can be very complex. Beyond that there are also many algorithms that can be applied to a graph to solve a problem. For example, Dijkstra's algorithm finds the shortest path between any two nodes in a graph with edge weights. If we apply it to our example road network graph, we can very quickly find the fastest way to get between two cities. If you’ve ever used Google Maps or Apple Maps to get directions, you’ve already seen graph theory and Dijkstra’s algorithm in action!

Graph Theory Applications in Hydraulics

As we have seen in class, the water cycle has a large effect on local geology, whether that be in depositing sediment, providing clean drinking water, generating power, or in maintaining glaciers. With a changing climate as well as constant modernization affecting stream flows, graph theory can be utilized to predict how these factors can influence the flow of water and help foresee unintentional consequences.

Currently, one of the leading methods of examining water resource management is with the use of hydraulic modeling. These systems include water parameters such as pressure and speed of a river, but alone it fails to capture the intricate relationships within larger water systems and it requires large amounts of data, computational power, and time. The usage of graph theory to amend this shortcoming is a relatively recent development, with studies comparing its usage to traditional hydraulic modeling only appearing in the past decade or so.

Figure 1. Classification of hydraulic objects used in the graph model, organized into natural resource entities, hydraulic facilities, and non-facility elements (Qiao et al., 2024).

Figure 2. The three-layer model structure showing inter- and intra-layer relationships between the natural resource layer, hydraulic facility layer, and service delivery layer across the Yangtze River Basin (Qiao et al., 2024).

Figure 3. Graph representation of the Yangtze River Basin water system, where nodes represent hydraulic objects and edges represent the relationships between them (Qiao et al., 2024).

While the methods can be used independently, they are most efficient when used in conjunction - traditional hydraulic modeling providing in-depth water analysis and graph theory applied to relate the connections of systems. An example of a model showing their combined use was created and demonstrated on the Yangtze River Basin by Jiabin Qiao et. al. The model relies on classifying traditional hydraulic modeling and their data which creates an integrated graph system using the hydraulic parameters. Figure 1 shows their classification of hydraulic objects. Figure 2 demonstrates how these nodes can be tied together in different systems to identify water flow for a city, a hydro plant, and a natural river ecosystem. Finally figure 3 shows a demonstration of what this would look like applied to the Yangtze River basin.

The paper concludes that their resulting model can be useful as a decision making tool for water resource allocation. Geological applications specifically could provide even greater detail to the existing hydraulic objects such as mineral content or potential changes due to erosion. The model could also be used to predict erosion in high flow basins or the rundown effects of a storm on water systems.

Figure 4: Waterfront accessibility ratio mapped across the Jialu River network, where warmer colors (orange to red) indicate river segments running through densely developed urban areas with high resident demand, and cooler colors (green) indicate more rural or suburban segments with lower accessibility scores. (Han et al., 2024)

There are other proof-of-concept examples utilizing graph theory, including a study by Yuping Han et al. that applies it to the Jialu River in Zhengzhou, China, to optimize river network connectivity while incorporating human land use. Their graph model represents river junctions as nodes and channel segments as edges, then iterates through different flow split ratios at five diversion nodes to find the combination that maximizes total wetted surface area across the network. The optimal scheme produced an ecological landscape area of 31.06 km², with split ratios ranging from 0.2 to 0.8 across the five nodes. Notably, the study also weighted results by "waterfront accessibility," measuring how much developed land sits within 500 meters of each river segment as a proxy for human demand. Figure 4 illustrates how waterfront accessibility varies across the Jialu River network, reflecting the uneven distribution of urban development throughout the basin. The geographic center of the optimal scheme shifted significantly once this human-use factor was included, illustrating that purely hydrological optimization and socially equitable water access can point to different priorities. From a geological perspective, this kind of model is particularly valuable because river networks are not static - erosion, sediment transport, and land use change constantly reshape channel geometry and flow behavior. Graph-based optimization tools like this one could help geologists anticipate how shifts in a watershed's physical structure, whether from natural processes or urban development, might ripple through the entire network and affect water distribution, ecological health, and even resource availability downstream.

Graph Theory in Geomorphology

The surface of the Earth is a system where landforms, sediment, and water are constantly moving and interacting. Graph theory gives us a way to formally represent relationships between these objects. Heckmann et al. describe how landscape units become nodes and the flows of water or sediment between them become edges. For example, a hillslope connected to a river channel by an active debris flow can be represented as two nodes joined by a directed, weighted edge, where the direction reflects downslope movement of material, and the weight might encode something like sediment transfer rate or transport resistance. The key idea is that the behaviour of a geomorphic system depends not just on its individual components, but on how those components are connected to each other as a network.

Spatially explicit network models make this concrete by tying graph nodes to real locations on the landscape. River networks are the most straightforward example: nodes represent sources, confluences, and outlets, while edges represent the channel reaches between them. Edge directions are constrained by gravity, and weights can encode flow capacity or resistance. This structure lets researchers ask questions like: if one reach is disrupted, how does that affect connectivity across the whole network? Sediment cascade networks work similarly but at a broader scale: landform units like talus slopes or river terraces become nodes, and edges represent sediment transfers between them. Analysing which nodes and edges carry the most material, or which are most critical to overall connectivity, can reveal bottlenecks in sediment routing that would be hard to spot from field observation alone.

A sandbar in a river channel. At higher flows, rising water levels may submerge the sandbar entirely, causing it to disappear from satellite imagery. At lower flows, it may appear connected to an adjacent one as a single continuous landform.

One limitation of these models is that they are typically built from static snapshots; a single survey or satellite image captures the landscape at one moment but says nothing about how individual landforms change over time. A common way to work with this kind of data is through software tools known as Geographic Information Systems (GIS). In a GIS, individual landforms like sandbars, lakes, or dunes are often represented as polygons: closed shapes drawn over satellite imagery that mark the boundaries of each feature. A collection of these polygon layers, each captured at a different time, is a typical starting point for studying how a landscape evolves. However, it can be difficult to compare these layers directly: a sandbar that looks like two separate polygons at high flow and one polygon at low flow may actually be the same landform. Koohafkan & Gibson address this with a graph-based method for tracking landform evolution across multiple snapshots. When polygons from two different GIS layers spatially overlap, an edge is drawn between them. Groups of polygons connected across snapshots are then interpreted as a single geomorphic unit: the same landform observed at different points in time. The method was demonstrated on sandbars in the Missouri River, and also handles missing data by constructing a geomorphic footprint for each unit - the combined spatial extent across all snapshots - which is used to flag observations obscured by cloud cover or cut off at image boundaries. The end product is a panel dataset that forms a record of each landform's individual history over time, which supports a stronger statistical analysis than simply comparing snapshots side by side.

These methods connect to broader ideas in network analysis that have been useful across many fields. In landscape ecology, for instance, Zetterberg et al. use a measure called betweenness centrality to identify habitat patches that are critical to species movement - patches that, if removed, would most severely fragment the network. The same concept applies in geomorphology: betweenness centrality can identify sediment relay points or channel junctions whose disruption would most strongly reduce connectivity across a catchment. More generally, tools offered by graph theory give geomorphologists a way to study landscape resilience: how much disruption a system can absorb before its routing behaviour changes. This helps inform decisions and support hazard assessment by identifying where the flow or sediment load is most concentrated. One thing worth keeping in mind is that applying graph theory always requires making explicit choices about what the nodes and edges represent, and those choices carry assumptions about how the system works. While that is a limitation, it also makes the approach useful since it forces those assumptions to be stated clearly rather than left implicit.

Conclusion / Your Evaluation of the Connections

Graph theory can both help geologists and utilize their knowledge in order to increase efficiency in complex systems, help predict and mitigate natural disasters, and assist in analyzing the present to understand the past. In hydrology it can be applied as a parameter to better understand both natural and man-made systems. Inversely, hydrological models utilizing graph theory can be applied in geological studies to predict downstream effects and theorize past waterflow. In geomorphology, graph theory provides a powerful framework for automatically tracking and analyzing how individual landforms like sandbars and dunes change over time across sequential spatial datasets, overcoming key limitations of traditional GIS comparison methods. These fields represent only a few of the potential applications that graph theory has in geology and the research is continuing to grow.

This project has given us insight on how research in one field (computer science) can directly translate to benefits in other fields (geology) in ways that we previously would not have thought of. Additionally, this page demonstrates how combining these fields of study ultimately benefits real world planning for safety and resource allocation and that an engineering or computer science degree has far broader applications than we initially assumed.

References

This Earth Science resource was created by Course:EOSC311.