Technical Terms:
complete graph, connected, cycle, degree, digraph, homeomorphic, incident, mutually reachable, planar, strongly connected, subgraph, thickness.
Link to Chapter 5 Complement.
A Parisian model that is more familiar than the map of the Pneumatique is the map of the Paris Metro (Figure 5.1)—the subway system that, for the most part, runs under the streets of Paris, linking the classical City Gates (Portes) —to each other as the many routes crisscross the Seine in using its various bridges. Indeed, the mere designation of Paris as a city separated into "Left" and "Right" Banks by the Seine makes sense as a directed structural model. The skipper of a boat carried downstream by the east to west flow of the Seine sees the land to the south of the river as the Left Bank and the land to the north of the river as the Right Bank.
Figure 5.1. This figure shows the Paris Metro system, based on an older map (date unknown).
The Paris Metro map is a graph; the numerous nodes represent local stations along a single train route as well as larger stations at which one can transfer from one route to another. There are a few arcs, forming a cycle, in the southwest of the map near the end of Route 10, and in the northwest on one branch of Route 7. All other segments joining two consecutive stations are the edges of this graph: they represent two-way Metro linkages. The map is complicated in appearance; subway lines often follow surface traffic patterns. Pedestrians need access to subway routes from sidewalks. Indeed, the Paris Metro map reflects the surface pattern of the numerous rotary, star-shaped intersections and tortuous streets (rues) that add much to Parisian charm. The Metro graph is of course connected (and as a digraph it is strongly connected). Choose any two metro stops; they are mutually reachable within the entire system, although a transfer might be required. Any well-designed mass transit system must be connected. There are a number of nodes with degree greater than four. Anyone who has traversed the maze of possible transfers at such stops will be aware of how complicated a trip from "here" to "there" can be.
Subway lines do not intersect each other in the way that geometric lines do. They intersect (one hopes) only where they have a stop in common. Can the entire subway systems be embedded in the earth in a single layer? Or, will some of the lines be forced above or below some of the other lines? Considerations of this sort, when captured graph theoretically, are referred to as considerations involving planarity. A graph is planar if it can be embedded in the plane. Consider, for example, a simple graph drawn as a box with two diagonals joining a set of four nodes. An embedding of the graph in the plane would stretch one of the diagonals to the outside of the box so that it did not "cross" the other diagonal. Until Kuratowski's Theorem appeared, it was a tantalizing unsolved problem to characterize planar graphs (1930).
Theorem 5.1. Kuratowski's Theorem. A graph is planar if and only if it has no subgraph homeomorphic to K3,3 or K5.
In this theorem (click here to see proof), the term homeomorphic refers to a style of topological equivalence relation that preserves connection patterns among nodes of a graph. The complete graph on five nodes, K5, has the five nodes joined as a pentagon with star inside it. K3,3 has six nodes, labelled 1, 2, 3, 4, 5, 6; join each odd node to all even nodes to produce it (Figure 5.2 shows it represented both as a static graph and as a dynamic Grapphlet; the latter, when compared to the Grapphlet of Planarity (Chapter 4) illustrates visually that K3,3 is not planar).
|
Figure 5.2. Any graph that contains a subgraph homeomorphic to this one is a graph that fails to be planar (dotted colored lines represent edges joining black nodes with numeric labels). Kuratowski Grapphlet displays visually the lack of planarity; the edges in the plane cannot be disentangled from each other. The reader can drag nodes to look at connection pattern and to make the pattern in the Grapphlet correspond more closely to the pattern in the Kuratowski subgraph. Sun Microsystems, Java™. Source: Graph.java. Used with permission from Sun Microsystems, Inc. Copyright 1998-2001 Sun Microsystems, Inc. All rights reserved.
Because there are quite a few transfer nodes with a number of incident edges, it is natural to consider whether or not a K3,3 or a K5 might be contained as a subgraph of the Metro graph. David Singmaster has shown that the London Underground is non-planar. Now we ask, is the Metro graph planar?
Indeed, the Metro graph also is not planar. When the map is strictly considered as a digraph, it is an easy matter to choose six nodes and a set of edges to form a K3,3. If one wishes, however, to eliminate the possibility of a transfer from one train to the other, in order to have direct geo-graphical adjacency as well as graphical adjacency, it is also possible to find a K3,3 under these tighter constraints.
The Metro stops of 1, Etoile ("star"), and 3, Nation, are joined on the north by a single Metro route (route 2) arching across the northern part of the city. They are joined on the south by a single arch (route 6) paralleling the southern perimeter of Paris. They are joined across a diametral route, through 4, Châtelet, as a "center," by a single Metro route (route 1) passing under the Champs Elysées, Concorde, Palais Royal, Hôtel de Ville and the Bastille. When 2, Montparnasse-Bienvenue, and 6, Stalingrad, are also chosen as nodes intermediate on these southern and northern arches, along with 5, Gare de l'Est, as a final node, this set of nodes can be joined in a K3,3 with only direct geographic linkage (requiring no transfers) between pairs of nodes along distinct edges. The numbering of nodes, 1 through 6, in the K3,3 corresponds to the numbering of nodes and coloring of edges in Figure 5.2. In both figures node 1 has three red edges incident with it; node 3 has three green edges incident with it; and, node 5 has 3 blue edges incident with it. In both figures, each of nodes 2, 4, and 6 has three edges, one of each color, incident with it. Thus, the two graphs are structurally equivalent (homeomorphic). We show the route along which each of these colored edges travels to illustrate the stronger condition that each edge also runs along exactly one geographic (Metro) route, as well. By Kuratowski's Theorem the Paris Metro, viewed as a structural model, is therefore non-planar.
Figure 5.3. Non-planarity of the Paris Metro—a K3,3 in the system. Thus, Kuratowski’s Theorem ensures non-planarity of the entire Metro. The colors of the red, green, and blue lines correspond to the pattern in Figure 5.2 to reveal the Kuratowski subgraph.
Because the Metro graph is non-planar, there must be tunnels in different planes (otherwise there would be at least one that would run into some other one): as with the Grapphlet above, the Metro cannot be disentangled to lie flat, without edges crossing, in the plane. Indeed, passengers trying to switch from one Metro route to another at Montparnasse-Bienvenue may recall running up or down stairs and through connecting tunnels to execute a transfer. The Metro map shows Route 4 north of Montparnasse-Bienvenue to "cross" Routes 12 and 10 (Figure 5.4). If these crossings were "real," rather than over- or under-passes, there could be serious train collisions at them. Map evidence (Paris Eclair) suggests that Route 4 passes under Route 12 and over Route 10. Routes 10 and 12 intersect at nearby Sèvres Babylon station; from that location, Route 10 heads eastward to meet Route 4 at Odéon (Figure 5.4). A lack of planarity, once understood to exist, can be used to advantage by engineers to plan safely designed new stations or new routes, and by mapping agencies to ensure that map pattern mirrors actual pattern, in a tightly packed transport system. The multiple layers needed to separate the Metro into pieces represent the thickness of the underlying graph.
Figure 5.4. Overpasses and underpasses from map evidence.
One might imagine a subway system to exist in a plane parallel to the plane of surface traffic, some number of feet below the surface. Experience with simple subway systems defeats this notion; trains run on elevated tracks in regions with high water tables or on landfill. Elevation is altered to cross natural barriers such as rivers. There is considerable topographic relief in most subway systems. Natural difficulties often force a subway system out of this sort of idealized planar environment. Thus, collisions between trains on different routes may occur. As in the case of Paris, the separation of routes into different layers (planes) offers protection from collision—except where the planes intersect.
In the 1980s, a large group of scholars and researchers at The University of Michigan analyzed various aspects of the Detroit water and sewer infrastructure. One component of that study involved mapping the water distribution network and suggesting strategies for where to locate new redundant linkage in that network (Arlinghaus and Nystuen, 1988). The map of the network was abstracted as a graph with weights on its edges that were proportional to associated water main diameter. Population dot maps were overlain on the water graph to look at the clustering pattern of people served by the various water mains and pipes and to discover where there were critical choke points, vital to effective water transmission. The graph, as it existed, was planar. Redundant linkage offers extra security in the transmission of water. Kuratowski's Theorem was used to introduce redundant linkage in such as way as to make the existing planar graph become, deliberately, non-planar. Thus, a break in the planar water network would not disrupt service everywhere. Detroit municipal authorities responded to these recommendations and Detroit City Council voted to install redundant linkage where field examination suggested it would be appropriate and in such a pattern as to make the entire network non-planar. Kuratowski's Theorem lives on in the Detroit municipal water distribution network!