About networks and graphs


This document was published with and applies to ArcGIS 9.3.
A 9.2 version also exists.

In this topic


Defining networks and graphs

Networks are simple and composed of two fundamental components: edges and junctions. Examples of edges are streets, transmission lines, pipes, and stream reaches. Examples of junctions are street intersections, fuses, switches, service taps, and the confluence of stream reaches. See the following illustration:
 
 
Edges connect at junctions, and the flow from one edge—automobiles, electrons, water—is transferred to another edge.
 
To analyze networks, geographers use a branch of mathematics called graph theory. Graph theory is interesting because it provides rigorous theorems concerning properties of networks and algorithms to solve network traversing problems. For example, one set of related algorithms for solving a problem in graph theory, known as the Chinese Postman Problem, provides optimized solutions for many applications such as postal delivery, street sweeping, bus passenger pickup and drop-off, and garbage collection.
 
Graph theory is the foundation for understanding networks and topology. A geographic information system (GIS) modeler should be familiar with the concepts and terminology of graph theory because it helps to classify and model connectivity and adjacency relationships among geographic features.

The first graph

The modern study of networks began in 1736 with an important mathematical result published by the Swiss mathematician Leonhard Euler. Euler considered a problem that was a local curiosity among the citizens of Königsberg in former East Prussia. The riddle was this—given seven bridges that cross a river and two islands, was it possible to take a walking tour across each bridge exactly once?
 
Euler solved the problem by thinking about the bridges and land masses as parts of a graph, an abstract set of junction objects (for land masses) and edge objects (for bridges). From this, he devised an easily understandable theorem that starts with an observation that the junction (or land mass) where you start a tour must be connected to an odd number of edges (bridges).
 
This must be so because otherwise, you must cross the same bridge twice to walk farther. Likewise, the junction where a tour ends must also have an odd number of edges. Because you cannot have more than one start and one end to a tour, his theorem proved that any graph with more than two junctions connected to an odd number of edges cannot be traversed by travelling through each edge exactly once.
 
See the following illustration that shows Euler's model of seven bridges of Königsberg with four junctions for the land masses and seven edges for the bridges. This started the mathematical study of networks. GIS software uses results from graph theory to implement solutions to many practical routing problems.
 
 
Why is this piece of mathematical history interesting? Not because it is a clever solution to a curious problem, but because Euler's insight illustrates that when you abstract a geographic system to its underlying graph, you have a useful model for understanding the connectivity of that system.
 
Today, you do the same sort of abstraction when modeling networks. Or rather, the core network models in GIS software do much of this abstraction for you, leaving modelers with a set of network properties for fine-tuning exactly how a graph is derived from geographic features. This underlying graph enables you to perform network analysis such as finding the shortest route. Network trace solvers in GIS software implement many algorithms from graph theory.
 
Whenever you do something interesting with a network in GIS software, you are interacting with its underlying graph. GIS software manages bidirectional links between network features and elements in a graph so that you can naturally interact with network features to solve useful problems.
 

Graphs and their elements

Graph theory applies to a range of phenomena, far beyond geographic applications. This is a brief, nonrigorous description of graph concepts. Understanding graphs and their properties will help you make network modeling decisions.
 
A surface can be considered an infinite set of points on which you can sample continuous varying phenomena, such as elevation, precipitation, temperature, soil moisture, and spectral reflectance at many wavelengths.
 
Other phenomena are not continuous across a surface. People, manufactured goods, water, energy, communications, and commodities are transported in a constrained way, channelized by streets, railroads, pipes, fiber optic lines, and shipping routes. The set of paths and where they join is a network, a subset of the infinite points on a surface.
 
Graphs can represent systems that move along natural or man-made linear networks. For example, the interstate highway system can be abstracted to a set of edges representing sections of the interstate highway between interchanges and junctions representing the interchanges at cities.
 
A graph is the set of edges that connect at junctions. Two junctions span an edge. A junction can connect to one or many edges.
Unfortunately, terminology is not consistently applied in the literature for graph theory. You will find the terms vertex or node variously used for intersections in a graph and arcs, chains, or links for the paths in a graph. Use the corresponding terms "junction" and "edge" for both the geographic network feature and its graph elements.

Properties of a graph

A graph can be directed or undirected. (A directed graph is also called a digraph.) Directed graphs model systems where each edge has a fixed direction of flow, such as a river network flowing downstream inside hydrologic channels. Undirected graphs model systems with no preferred direction of flow, such as street networks that predominantly allow travel in both directions.
 
A graph can be planar or nonplanar. Planar graphs connect on a two-dimensional plane at junctions, without any crossing edges. Nonplanar graphs have edges that cross. On a street network, nonplanar graphs can model a bridge over a road. Geographic data commonly comes in planar and nonplanar form. Planar data allows you to use elevation level information to model crossing streets. For more information, see Elevation fields for planar lines.
 
A graph can be cyclic or acyclic. A cycle (or circuit) is a set of connected edges that eventually returns to a junction (in the case of directed graphs, a further condition is that the edges line up in flow order to close a cycle). A graph without cycles is a tree graph (or acyclic graph) in graph theory. Examples are local area communications networks and river systems. A graph with cycles is a cyclic graph. Application examples are streets and water utilities.
 
Three important qualities of a graph pertinent to geographic networks are whether the network has directed flow, whether edges can cross on a plane or not, and whether junctions and edges form cycles inside a graph. See the following illustration:
 
 
 
Knowing whether a graph is directed or undirected is the most important graph property when considering GIS network models. These two types of graphs are optimally stored with different internal data structures and have separate classes of algorithms for network analysis. Consequently, the geodatabase model has two fundamental representations for a network. For more information, see Two core network models.


See Also:

About network applications
How to draw networks on a map
Two core network models
Elevation fields for planar lines