Chapter 2


The Berlin Rohrpost and Centrality


Technical Terms:

branch weight, center, centroid, eccentricity, edge, graph, node, path, root, subgraph, tree.

Link to Chapter 2 Complement.


A graph G consists of a set of nodes and a set of edges, each edge joining two nodes. When there is exactly one path between any pair of nodes, G is called a tree. Diagrammatically, graph-theoretic trees look like stick drawings of real-world trees. Because graph theoretic trees have only single edges joining pairs of nodes, there is no redundant linkage in them. Thus, they are not as common in the built, manufactured geographic landscape as one might otherwise suspect (as representing transportation systems, and so forth), although they do arise naturally in the world of the watershed (click here to see the clickable 'Atlantic drainage tree' with the ocean represented as the tree trunk and river basins as tree leaves). They tend to arise when linkage between locations is expensive or when the initial linkage is considered highly reliable. As times and technologies change, redundant linkage, which destroys tree structure by introducing extra edges, becomes a prized insurance policy.

Indeed, even in the purely abstract realm, the number of graphical trees is small in relation to the number of graphs possible. Consider the ratio of the number of n-node trees to the number of n-node graphs. This ratio reflects the density of trees within the set of all possible graphs for given n. The limit as n goes to infinity of this ratio is zero; the number of trees, from the set of all possible graphs, is negligible for large n (Harary and Palmer 1973; Blass and Harary 1979). Thus, structural models involving graphical trees are most reasonable to consider when n is not large. We present as a sample an historical study that is complete in time-span, that involves linkage that was expensive to install and was viewed as reliable, and that involves a small number of nodes (Arlinghaus 1985).

The Berlin Rohrpost: Background

Pneumatic mail delivery systems of the late nineteenth and early to mid-twentieth century offer an unusual environment in which to consider graph-theoretic and real-world infrastructure simultaneously. Beginning in 1853, a number of experiments with relatively expensive underground pneumatic communications systems were underway in Western Europe. After slowdowns caused by the Seven Weeks War (1866) and the Franco-Prussian War (1870), full-fledged pneumatic communications systems began to appear in major cities in Western Europe as a speedy alternative to mail delivery through congested surface streets.

By 1901, the "Rohrpost" carried messages under most of Berlin (Figure 2.1). The heart of the message system was in a central office on Unter den Linden, denoted as the largest circle in Figure 2.1 and the root of the graphical Rohrpost tree. Adjacent graphical nodes were linked as underground real-world nodes by "edges" of metal tubing. The real-world nodes had surface housing that could pump and compress air and thus receive and deliver messages.

The structural model of the Rohrpost (Figure 2.1) shows the linkage pattern of edges joining nodes and reflects an hierarchy in the procedure for message transmission. Certain pneumatic stations were designated as having functions of a higher level of service than were other locations.

Rohrpost pneumatic network, Berlin: a structural model.

Figure 2.1. The tree of the Berlin Rohrpost, 1901, rooted at the central office. Source: Beschreibung der Rohrpost, 1901.

Typically, message containers were pushed, using compressed air, from one higher order office to a hand-over position intermediate between higher order offices. From this hand-over position, suction drew the carrier toward the next higher order office. Hand-over nodes outline energy subgraphs and regions surrounding higher order offices (Figure 2.2). To move a message from A to B (Figure 2.2), use the following transmission sequence: compression from A to p, suction from p to B. The office p is a transfer point or a "gate", from compression to suction, as are all other offices that are in two subgraphs. This sort of partition offers a directed graphic code that can be used to track the progress of a message through the system and therefore helps to determine the location of collisions or blockages. Indeed, the Berlin Rohrpost of the early 20th century had many "Checkpoint Charlies," as at node p.

Energy regions within the Rohrpost, outlined in gray hachured markings.

Figure 2.2. Energy subgraphs and regions within the Rohrpost. The largest red dot represents the Central Office. The next largest red dots represent Head of Line Offices. The smallest red dots represent Local Offices. The fine lines represent pneumatic linkage. The heavy black lines (from A as far as p) represent the edges of pneumatic subgraph 1; the blue lines (from B as far as p) represent the edges of pneumatic subgraph 2. The black squares represent Energy Sources; the dashed black lines represent links from energy sources to the pneumatic network. The gray hachures outline energy regions. Source: Beschreibung der Rohrpost, 1901.

Transmission problems ranged from the esoteric to the expected. Even though the staggered use of compression and suction dried out the system, tubing placed at insufficient depth under streets and sidewalks occasionally froze in the winter. "[In Berlin] large quantities of liquid spirits of wine were introduced into the tubes for the purpose of detaching the ice from the walls of the tubes" (U.S. Postmaster General 1891, pp. 154, 152). It might be tempting to consider whether the French would have engaged in such a solution to ice detachment.

Frozen tubes forced interruption in the service, as did other breakdowns resulting from damage to the tubing from street repair, from other underground urban systems, and from changes in grade level (Scientific American 1901, pp. 327, 328). To understand system failure, it becomes important to know which offices are dominant in terms of the connection pattern of the nodes. The introduction of redundant linkage, as a means of overcoming significant system failure, is usually an expensive procedure; good planning tactics involve optimizing its position in relation to central nodes, heavily used links, or similar considerations.

Generally, a message transmitted from origin to destination traverses a graph-theoretic path. The nodes and edges in the transmission path are necessarily distinct, given the mechanics of the transmission and the linkage pattern of the tubing of the actual postal system. Redundant linkage was not present in the Rohrpost of 1901. The evidence of maps and historical documents tells us the actual location of the central office. Would graph-theoretic analysis also have confirmed this position of dominance? To find out, we measure the Rohrpost tree to determine whether the centrality concepts of center (the node least distant from the perimeter of the graph) and centroid would have served as reasonable structural models. Would these measures have identified the designated central office as the center or centroid of the graphical Rohrpost tree?

Center of the Rohrpost Tree: An Application of Eccentricity

To identify the center of the Rohrpost, first calculate the eccentricity of each node. We illustrate the concept of eccentricity with an example. The stretched circular form of the ellipse has a constant eccentricity that captures the extent to which it is stretched. In a graphical context, eccentricity also measures extent of stretching. It is a value attached to a node that measures the longest path from that node. Thus, in Figure 2.3, the central office has a value of 8 as its eccentricity because the longest path from that node has eight edges in it (from P to Q) in Figure 2.3. It is from P to Q that the Rohrpost "stretches" the most, outward from P. Note that this relationship is not symmetric. The longest path from Q has 14 edges: from Q to R. The largest eccentricities in this case are along an east–west path, although one north–south axis has terminal nodes with eccentricities of 12 and 13.

Broadly viewed, the Rohrpost is essentially circular in transmission capabilities. The "center" of this circular structure is the node with lowest eccentricity: the node least distant from the perimeter. When each node in the graph is weighted with its eccentricity, it is usually an easy matter to select the node (or nodes) with lowest attached weights (Figure 2.3). The small node directly adjacent to P (a star-shaped symbol) has eccentricity 7: it is the graphical center of the graphical Rohrpost tree (Figure 2.3) and is located at the Brandenburg Gate.

Eccentricity: center is at the star. Longest path from center has 7 edges.

Figure 2.3. All nodes in the Rohrpost graph are labeled (using color) with eccentricities. Those of lowest value (in this case one node) serve as the center; here the center is a star-shaped symbol.

The locations adjacent to the Brandenburg Gate, at the Central Office (to the east), the Potsdam Gate (to the southwest), and one other location, all have eccentricity 8. They form a tight central core around this center. The fit between real-world and structural model is close, but not exact, using the concept of center.

Centroid of the Rohrpost Tree: An Application of Branch Weight

The concept of center measures, to some extent, how tight the pattern of connection is around a core of nodes. It measures whether or not there is central symmetry within the structural model: whether or not accessibility within the network is stretched in one direction or another. The notion of center does not take into account the idea of volume of traffic; to do so requires looking at more than direct adjacencies in calculating weights for nodes. What happens in a remote part of town may influence traffic patterns across town. The concept of centroid, a balancing point on which the entire weighted surface of the map rests, offers one way to do so. Centroids typically appear in mathematical applications with Cartesian coordinate systems, where the balance point is calculated in terms of that coordinate system. The graph theoretic characterization is, of course, free from coordinates. It rests on calculating, for each node, the number of edges for each branch attached to that node. The largest number is associated with the "heaviest" branch, and that number is called the branch weight of the node. The centroid of the graph is the set of nodes with the smallest branch weight value.

To calculate the centroid of the Rohrpost, calculate the branch weight for each node. The centroid(s) are the node (or nodes) with the lowest branch weight: it (they) is (are) the balance node(s) around which the tree’s heaviest branches are arranged. (A tree may have one or two nodes as its centroid—Jordan’s Centroid Theorem.) In Figure 2.4, the heaviest branch having the Central Office node as root is the branch that is heavily shaded. It has 19 edges in it, including the path used in the calculation of eccentricities, as well as the smaller sub-branches attached to that path—the twigs feeding into the main branch. Nodes on the periphery have longer heaviest branches and therefore greater branch weights than do nodes in the interior. Thus, it is reasonable numerically to view the most central, in this context, as the node(s) with the smallest branch weight.

Branch weights are more tiresome to calculate than are eccentricities, but as with eccentricities, once they have been determined and are attached to nodes in a graph, it is not usually difficult to visually determine which node (or nodes) have the minimum branch weight and serve as the centroid. Figure 2.4 displays the entire set of Rohrpost nodes and edges with branch weights attached to each node. In the case of the Rohrpost, the centroid is a single node (red diamond in Figure 2.4) that coincides with the actual Central Office: the fit is exact.

Branch weights and centroid.

Figure 2.4. The heaviest branch from the Central Office node in the Rohrpost has 19 edges, labeled in this figure. All nodes in the Rohrpost graph are labeled with branch weights. Those of lowest value (in this case one node) serve as the centroid: a red diamond shape.

In the case of the Rohrpost, plans that evolved over time in response to engineering constraints, human needs, and governmental policy were ones whose spatial components could also be captured and analyzed readily as a structural model. Historical evidence is critical in testing technique. When abstract analytic technique fits plans based solely on real-world considerations (such as the Rohrpost), then that fit suggests merit in considering similar custom tailoring of these and other abstract models to real-world scenarios.

Indeed, it is the notion of "custom" fit that is critical. If, for example, one takes the set of three hierarchical levels of Rohrpost stations, local, head, and central, and places them in a GIS (Geographical Information System) as three different layers, it is a simple matter to get the software to draw a network that in some manner is optimal. It takes less than a minute to create a map that links the central office to each head of line office (Figure 2.5a) and also each head of line office to nearby local offices (Figure 2.5b). The composite of the two produces a fine system (Figure 2.5c), perhaps well suited to the transmission of pneumatic messages. The speed and freedom with which such maps can be created is truly astounding when compared with the pen-and-ink environment of only a few years ago. With such cartographic freedom, however, comes a daunting responsibility of attempting to ensure that those who learn to use it also learn to understand it. The system of Figure 2.5c reflects none of the human and policy concerns surrounding development of the entire system; it is simply a fine example of technological manipulation. In today's software environment, there are many statistical procedures linked with GIS software (ESRI; Hooge and Eichenlaub, 1997). We look forward to the time when graph-theoretic procedures, as well as statistical and other mathematical procedures, also are routinely embedded in software.

Spider diagram representing global linkage pattern within the Rohrpost.

Figure 2.5a. Central office joined to each of Head-of-line offices in a "spider diagram".

Spider diagram representing local linkage patterns within the Rohrpost.

Figure 2.5b. Head-of-line offices joined local centers in a regionalized "spider diagram".

Spider diagram overlay.

Figure 2.5c. Overlay of maps in 1.5a and 1.5b; all three mapped in ArcView 3.0a (ESRI) with Spatial Analyst Extension (ESRI) and Animal Movement Analysis Extension for ArcView, Hooge and Eichenlaub, Alaska Biological Science Center.

It was not obvious at the outset, even with only two measures in hand, whether the centroid or the eccentricity measures of centrality would better describe this system. It is important to consider carefully which tool is best suited to the application at hand.

Spatial Synthesis

The three hierarchical levels (Figures 2.5a, b, c) near the end of the previous section suggest one way to analyze an existing real-world network. There are many others, as well. One might focus on the center and pick off the actual branches and rearrange them, stretch them, or reorient them (Figures 2.6a, b). The structure of the model is not changed by such activity: the connection pattern remains the same.

Image

Figure 2.6a. The Berlin Rohrpost graph is shown here. The node x is distinguished as the root with branches a, b, c, d, e, f, g, and h emanating from that root. The branches are arranged in clockwise fashion around the root, beginning with the branch a at the 9:00 position.

Central office, x, and adjacent offices labeled with Branch letters and the numeral 1:

Image

Branch a:

Image

Branch b:

Image

Branch c:

Image

Branch d:

Image

Branch e:

Image

Branch f:

Image

Branch g:

Image

Branch h:

Image

Figure 2.6b. Branches of the Berlin Rohrpost are shown in this figure. Branch labels, letters of the alphabet, correspond to the letters of nodes adjacent to the center in the upper left cell of this display. The node x is the root of these graphs.

To visualize such an action, that of synthesizing or integrating branches (as in arranging flowers in a vase), one might use current technology that permits a sort of visualization not previously readily available. Indeed, much as fractal geometry permitted (previously unavailable) visualization of continuous curves that are nowhere differentiable, object-oriented geometry at the base of programs such as Java™ (Sun Microsystems) permits a similar style of visualization of discrete structures with fixed connection patterns (Figure 2.7). It offers exciting possibilities to those engaged in abstract network studies and a substantial challenge to municipal planners involved in traffic monitoring and related transportation planning.

This OEB reading system does not support Java.

Figure 2.7. This Mapplet on One Center offers a dynamic arrangement scheme for branches of the Rohrpost. The reader can drag the center and other nodes to look at connection pattern and to make the pattern in the Mapplet correspond more closely to the pattern in the map. The labeling in this figure corresponds to the labeling scheme in Figure 2.6. (The single center in the mapplet is identified by the word "Center"; in Figure 2.6 it is represented as a large circle containing "X".)   Sun Microsystems, Java™. Source:  Graph.java. Used with permission from Sun Microsystems, Inc. Copyright 1998-2001 Sun Microsystems, Inc. All rights reserved.

The exciting possibilities offered by remarkable applications of mathematics in a computing environment carry substantial cautions with them. Good choices, in analysis or synthesis, can be made only when a body of theory, not biased by choices made by other practitioners in different applications, is available to the researcher. Further, to avoid repeating previous errors, good choices in application can be made only when historical evidence is coupled with the theoretical, structural concerns.