Graph Theory part 3 – Urban Planning

Graph theory plays an important role in mathematics, not only theoretically, but also realistically with its applications as well. One of those applications, and probably the most relatable one, is urban planning, where the most important thing is to find the most efficient pathing between two randomly given points. And if we consider the junctions as the vertices and the streets as the edges, we have ourselves a naturally-occurring giant graph that is the very city that we are living in. Last week, I wrote about the structural properties of graphs, including connectivity and several structure types (walks, trails, paths, cycles, and circuits). All of them are going to play in urban planning.

1. Connectivity and circuitry – From the Seven Bridges of Konigsberg to modern days:

To us now, the visualization of streets as grids, facilitated by maps, is pretty much the standard;  but for the people back in the 1700s, when the roads system had not been extensively developed and so were the maps, it is debatable whether such a visualization was commonplace. Regardless, it was certain that research on graph theory was lackluster, and it was Leonhard Euler, the Swiss mathematician, who laid foundation for this field with his negative solution for the problem of the Seven Bridges of Konigsberg.

Above is a map of the seven bridges of Konigsberg at that time, along with the visualization of it as a graph with 4 vertices A, B, C, D. The challenge was simple: to complete a trip through all seven bridges without crossing any bridge twice, or, speaking with terminologies, to complete a trail of all edges of the graph. Many people have tried the challenge, but none managed to accomplish it – yet until Euler nobody was able to give a reason for their inability to do so. Before stepping into Euler’s solution, we consider this lemma:

A graph which exists a trail passing through all of its edges must either have:

• Two odd-degree vertices, in which case the trail is open, or,
• All even-degree vertices, in which case the trail is closed, or is a circuit.

Proving the lemma above is rather easy. In such a trail, every edge can be considered either an entering edge (in which the trail comes to the vertice after having passed through the edge) or an exiting edge (in which the trail comes to the vertice before entering the edge). So for every intermediate vertex (i.e. one that is not the beginning or the end of the trail), there must be an exiting edge for every entering edge, which makes the degree of the vertice even. In closed trails the ending and beginning of the trail is the same, so the degree of the beginning vertice is also even. In open trails, the beginning vertex has one more exiting edge than entering edge, and the ending vertex has one more entering edge than exiting edge, which makes their degree odd.

Coming back to the proof, Euler realized that all the vertices of Konigsberg had odd degrees (3 for B, C, D and 5 for A), which led him to the conclusion that the challenge was unsolvable, since there were 4 vertices of odd degrees in total.

What is the importance of this besides, well, laying the foundation for the entirety of graph theory, if it was not enough.

Take a look at city tours then.

Above is a map of a Ho Chi Minh city tour in Vietnam. Notice how there are no repeated streets except for that single entrance into the port on the right? Yep, there you go. Since tourist companies want to maximize the experience of their clients, it is in their absolute interest to constantly show new things on the way, and therefore not repeating the route is a must. Quite an interesting application of the problem hey?

2. Minimizing the Distance:

There are multiple reasons why minimizing the distance is important. First, doing so has its economic benefits, including travelling time and fuel which can be converted into opportunity costs. Secondly, it also brings more comfort to the citizens, which would undoubtedly be irritated if forced to take a long runaround trip to get to their destination.

Regarding the best travelling route, it is common sense that the best route would always approach the destination either vertically or horizontally. For example, point B is on the top-right of point C, so a good route from B to D would always go up and right.

So why do we often see grid-like placement of the streets? Why not diagonal ones, which is always the best way of travelling?

The answer is: Using diagonal routes, while being an advantage to one, will be a disadvantage to another. In the example above, while CFEB is a good route to go from C to B, AEFB is a bad route to go from A to D, since the segment EF goes to the left instead of the right. In case of rectangular grids, everyone would be assured a good route.

Next week, I will probably write more on this fascinating topic – there is still so much to talk about. Math on!