Graph Theory

When you work in fields that are concerned with revealing spatial patterns and problems, such as wayfinding, you come to realise how useful it is to understand the basics of some discrete mathematics, such as graph theory. For me, subjects like cartography that deal with a degree of abstraction, are fascinating. This is a basic introduction.

Essentially, graph theory is the study of topological relationships. From a given set of nodes (vertices) and connecting edges (segments), we can abstract a range of conditions, including city layouts. Studying systems in this more abstract way has numerous applications that are concerned with spatial arrangements (networks); physical, biological, data or social. For example, vehicle route planning, social networks, spatial connectivity and integration of urban spaces, and, as a topical example, the spread of COVID-19 through a community. Graph theory is core to the theory and techniques in fields of study and practice such as space syntax and urban morphology.

What defines a graph?

Most graphs are much more complex, but those below illustrate the common forms. The tree graph can only flow from the pareent (root) vertex to the child vertcies. No two-way or looped connections. It is possible for a single vertex (node) to have a circular edge (link), starting and finishing at the same node—a self-loop—in which case that is called a singleton graph. The edges on an undirected graph can travel both ways; they are all bidirectional (no fixed origin or destination). This is different to a directed graph [1][2], also called a digraph, as there is a direction of flow (from origin to destination), and only in that direction. However, a directed graph can have a mix of one- and two-way edges [2] due to having an origin and destination.

Example of undirected graphTree graph
Example of directed graph Undirected graph
Example of undirected graph Directed graph [1]
Example of undirected graph Directed graph [2]

The last form of directed graph [2] can be confusing as if edges go both ways to vertices, then isn"t that an undirected graph? Why not show it without arrows? There is a mathematical convention and argument in that a graph (G) is made up or object pairs, vertices (V) and edges (E), such that G = (V,E). These can be written as unordered or ordered pairs.

In the the undirected graph above, it doesn’t matter the order of the vertices as unordered pairs:

V = {A,B,C,D,E,F}
E = { {A,B}, {A,C}, {B,C}, {B,C}, {B,D}, {B,E}, {C,D} {D,E}, {E,B}, {E,F}, {F,B} }

In the directed graph [1], the order of vertices is significant in ordered pairs and the notation slightly different:

V = { A,B,C,D,E,F }
E = { (A,B), (A,C), (B,D), (C,B), (D,C), (D,E) (E,F), (F,B) }

For the sake of clarity, the directed graph [2] is written as:

V = { A,B,C,D,E,F }
E = { (A,B), (A,C), (B,E), (B,F), (C,A), (C,B), (C,D), (D,C), (D,E), (E,D), (E,F), (F,B) }

As further examples, Facebook may be considered an undirected graph as ‘friend’ invitations are mutual and two-way; bidirectional. On Instagram, however, if someone follows you, you have the option to not follow them back. As such, the relationship is directional and two edges are created [2]. Either party can change their decision at any time. The World Wide Web (WWW) is an example of a directed graph.

In summary

This basic introduction, to what is a very interesting field, has numerous applications in real world situations. Here agents, algorithms and weighting start to play a part in the analysis. Vehicle route planning adds weighting to road lengths and class (e.g. A-Road) to find the shortest and/or fastest route from A to B. However, the application that interests me most is space syntax.

“By studying buildings and cities as patterns of space, we can derive new insights into the relations between them and the individuals, communities and organisations that inhabit them.”

Space Syntax course literature, UCL

The science and methodology of space syntax provides for the analysis of spatial configurations of all kinds and at all scales, internal and external. It has been extensively applied in the fields of architecture, urban design and planning, transportation, building work and visitor spaces. The study of the impacts of spatial configuration and design on aspects of social, organisational and economic performance of buildings and urban areas is critical to their improvement.