Chapter 7



Maps and the Four Color Theorem

Red sky at night,

Sailor's delight;

Red sky at morning,

Sailor take warning.

Anonymous



Technical Terms:

adjacency, chromatic number, color, color ramp, cycle, dual graph, geodesic, GIS, grayscale, hue, luminosity, Manhattan space, saturationstereographic, thematic map, torus, voxel, wheel.

Link to Chapter 7 Complement.


E-books, such as this one, make it possible to use color at the same cost as black and white: a luxury not afforded authors or publishers in the classical world of hardcopy-only printing. Using color just because one can use it, and not because one needs to use it, may produce visual clutter. Thus, we consider various aspects of color usage. The cartographer, Arthur Robinson noted (Robinson, 1960, p. 228),

Color is without a doubt the most complex single medium with which the cartographer works. The complications arise from a number of circumstances, the major one being that even yet we do not know precisely what color is. … The complexity is due to the fact that, so far as the use of color is concerned, it exists only in the eye of the observer.

Coloring Thematic Maps

Geographical Information System (GIS) software makes color easy to use on maps. Thematic mapping involves taking content (data) and splitting it into subsets concerned with the content. Each subset is assigned a separate color representing a particular range of the data. Readers are no doubt familiar with thematic maps that show, for example, percent by state of some variable: 0–25% the lightest shade, 25–50% the next lightest, 50–75% a bit darker, and 75–100% the darkest. A grayscale works well for a map of this sort; there is no need to introduce color to communicate the pattern. If, however, one does introduce color to represent such a numeric pattern, one must do so carefully. To choose yellow for the first subset, red for the next, green for the next, and blue for the highest does not present the visual continuity in the map that is present in the data. Instead, one might choose a red monochromatic scale, from light red to medium reds to a deep red, to create the needed visual continuity in color. Poor choice of color can make a map that fails to represent what might easily have been represented in black and white.

Continuity

Most GIS software offers the user a scheme for creating reasonable groupings of color. There are smoothing algorithms that let the user pick two colors and then hit a button to have the software produce a "smooth" color sequence from the first to the last color (Atlas GIS, ESRI). Others offer a variety of ramps from which the user may choose monochromatic color scales, or already-smoothed version of two and three color scales (ESRI ArcView GIS). Using color in this sort of black box mode has certain advantages: the beginner who uses these schemes is not likely to produce a map with a hideous color scheme. However, playing with the color, out of the black-box mode, has advantages: the user learns readily when the limits have been exceeded.

Color Characterization

Not all software has a nice color smoothing routine embedded in it. Readers interested in the variety of characterizations of color that are available are referred to the cartography books listed in the reference set at the end. We consider here, in the context of an e-book, one style of color characterization. Following Robinson's strategy, color choice and use are tailored to "standard" reactions, by a typical observer, to color. The effect of color on an observer is often captured using the following set of primitive terms: hue, saturation, and luminosity.

In the more contemporary environment of the desktop computer, users of various software packages in common use are exposed to the hue-saturation-luminosity set of primitive terms on a regular basis. In addition, they see the RGB (Red-Green-Blue) description also using three primitive terms and the printer's (photocopier's) environment of separations into layers based on CMYK (Cyan-Magenta-Yellow-Black). A color wheel can help the user to design strategies for color change: to decrease magenta, for example, subtract magenta, or add cyan and yellow (opposite from magenta). In Figure 7.1, magenta emanates from the center along the right half of a horizontal axis; the left half of the horizontal axis, opposite magenta, bisects the yellow and cyan axes.


Image

Figure 7.1. Color wheel.

Vectors in Color Space.

One conceptually natural way to look at color is as an ordered triple in Euclidean three-space. Indeed, that is how color charts are set up in a variety of contemporary desktop software such as Netscape, Microsoft Office, and so forth. Hue is measured across a horizontal x-axis. The animated color chart in Figure 7.2 shows the change in hue as one moves across the x-axis of a color chart of a style present in many contemporary desktop software packages (this one comes from Netscape). Notice the change in the small box, Color/Solid, as the cross-hair moves horizontally across the spectrum in the larger box (Arlinghaus, S. and Arlinghaus, W., 1998).

Image

Figure 7.2. Hue is measured horizontally in this style of color chart common in desktop software.

Saturation is measured along a vertical y-axis (Figure 7.3). The animated color chart in Figure 7.3 shows the change in saturation as one moves up or down the y-axis of a color chart of a style present in many contemporary desktop software packages. (This one comes from Netscape.) Notice the change in the small box, Color/Solid, as the cross-hair moves vertically across the spectrum in the larger box.

Image

Figure 7.3. Saturation is measured vertically in this style of color chart common in desktop software.

The resultant of these two color vectors is a square or rectangular color space with vertical strips of color corresponding in order to the pattern on the color wheel. A third axis of luminosity (a gray scale) is often seen as a strip to the right of this square (Figure 7.4). It matches the selected color from the two-dimensional color space, generated by hue and saturation vectors, against light/dark values.

Image

Figure 7.4. Luminosity is measured along a z-axis, to the side, in this style of color chart common in desktop software.

These animated color charts fix two dimensions and allow a third one to vary. That variation shows up in the small rectangle to the lower left of the color map and along the z-axis to the right of the plane region. The square, generated by the x and y, vectors contains 2562 pixels of possible color (note that the range of values available for each of hue, saturation, and luminosity is from 0 to 255). The z-axis introduces another 256 possibilities.

Thus, a natural alternative way to visualize this approach to color is to think of a cube (in 3-space) of 256 units on a side. Label the x-axis as hue, the y-axis as saturation, and the z-axis as luminosity. In this case, color space is formed from a set of volume pixels (voxels: a term heard at American Mathematical Society meetings in conversation) making up the cube. Since 256=28, there are therefore 28 · 28 · 28 = 224 = 16,777,216 voxels within the color cube (note the discrete structuring of a normally continuous object).

The notion of looking only at voxel subsets within a single plane parallel to a face of the cube, as is the case in Figures 7.2, 7.3, and 7.4, is limiting within this large, but finite, set of possibilities. In choosing sequences of color there may well be reason to follow a diagonal, to tip a plane, or to find various other ways of selecting subsets of color, as a smoothed color ramp, from this vast array. It is to these possibilities that we now turn.

Color Charts and Manhattan Space: Color Ramps and Alternate Metrics

The problem of finding color ramps linking one color to another can be captured simply as follows: To find a ramp joining two colors, A and B, first represent each of A and B as an ordered triple in color voxel space. Then, the problem becomes one of finding a path from A to B. Because one is limited to integer-only arithmetic in this discrete space, divisibility of distances often will not be precise; thus, one is thrown from the continuous realm of the Euclidean metric into considering the non-Euclidean realm of the Manhattan metric (of square pixel/cubic voxel space). Algorithms for finding shortest paths between two arbitrary points using integer-only arithmetic will therefore apply to colors mapped in color space as well as to physical locations mapped on city grids. To see how these ideas might play out with colors, we consider an example that will lead to an animated color ramp.

Find a path through color voxel space from (80, 100, 120), shown below as a medium green to (200, 160, 60), shown below as a deep purple. One set of points through which to pass, spaced evenly (not always possible), is given in Figure 7.5. The left-hand column shows values of hue, the left-middle column values of saturation, and the right-middle column values of luminosity. The right-hand column shows the associated color swatch.

80

100

120

Image

90

105

115

Image

100

110

110

Image

110

115

105

Image

120

120

100

Image

130

125

95

Image

140

130

90

Image

150

135

85

Image

160

140

80

Image

170

145

75

Image

180

150

70

Image

190

155

65

Image

200

160

60

Image

Figure 7.5. This figure displays a color ramp generated in color voxel space.

Figure 7.6 shows an animation to illustrate how the three-dimensional path is mapped into the commonly employed two-dimensional scheme. The crosshairs show the movement along the path while the flashing color in the rectangle below the color map shows the associated color ramp. Clearly, the choice of path is not unique: geodesics are not unique in Manhattan space. This vantage point on color suggests the following theorem:

Image

Figure 7.6. A color ramp mapped from 3D to a 2D viewpoint.

Theorem 7.1. Manhattan color ramp theorem. The determination of color ramps joining two colors (each represented as an ordered n-tuple) is abstractly equivalent to finding paths in Manhattan space between two arbitrary points (where geodesics are not unique).

Partition

Perhaps the next most common issue involved in considering color on maps also involves the use of color on thematic maps. GIS software permits the user to easily partition, in a number of different ways, the underlying data set that is being mapped. Two styles of partition that are commonly used are "quantile" and "equal interval". In the quantile approach, each subset contains the same number of entries from the database (within limits of divisibility); the size of the interval bounding the subsets may differ but the number of elements in each subset is constant. In the equal interval approach, the size of the interval containing each subset of data is constant; the number of entries from the database need not be (and are likely not to be). The maps below show very different results using those two methods of partitioning the same data set. When the underlying database variable measuring area of country was partitioned according to quantiles, the map on the left was the result (Figure 7.7a). When it was partitioned using equal intervals, the map on the right was the result (Figure 7.7b). When making your own map, consider a number of alternatives for partitioning the data and consider the general spread of the data: a data set that is linear in character is a better choice to map using equal intervals than is one that has most of the data clustered at one or more locations. When writing about your own thematic map, consider offering the reader several alternative maps and discuss them and your reasons for any decisions you might make about which one(s) to use. Also, when considering a thematic map made by someone else, ask how the underlying database might have been partitioned and what alternative results might be like based on various partitioning schemes. This particular issue involving the importance of selecting a method for partitioning of data and its implication for resulting thematic maps cannot be overemphasized. (For a fine discussion of this and related topics involving color and maps, see Monmonier, How to Lie with Maps). Each partitioning scheme has its own merits and drawbacks; each produces maps different from other data partitioning schemes.

Click to see larger image.

Figure 7.7a (left): map made by partitioning underlying data set using the quantile strategy.

Figure 7.7b (right): map made by partitioning same underlying data set as in Figure 7.7a using the equal interval strategy.

Adjacency and Coloring

When carefully used, color can be used to extract meaning from an environment. When is color necessary rather than merely decorative; and, when color is necessary, how many colors are required to make the desired distinctions? We consider questions of this sort below and tie them to graphical and to geographical evidence.

To color a map means to assign colors to its regions so that no two regions with a common boundary have the same color. The regions are regarded as non-overlapping; and boundaries between regions are curve segments. Two regions that touch only at a single point are not considered to have a boundary composed only of that single point (as at the four corners of Arizona, New Mexico, Colorado, and Utah in the United States). In the coloring scheme of the U.S. map below, red was generally used as first choice, green as second, yellow as third, and purple as fourth (Figure 7.8). The second, third, and fourth choices were used only when required.

Animap of the US states illustrating the Four Color Theorem.

Figure 7.8. This figure displays an animated map illustrating the use of four colors.

When the regions shrink to points, and the common boundaries are converted to edges, the geographic map becomes a graph (see also, dual graph). Thus, to color a graph means to assign colors to its nodes so that no two adjacent nodes have the same color (see Harary, 1969). The number of colors needed to color the nodes of a graph G is called the chromatic number χ(G).

The Mediterranean Basin: Countries Sharing a Common Resource

Often one sees maps that use many different colors or patterns to distinguish one region from another. But how many colors are required? Consider the Mediterranean Sea and the countries that have some coastline along it. This set is a natural environmental grouping: a set of countries sharing direct access to a common resource (the Sea).

The coloring scheme in the map of Figure 7.9a uses new colors only when forced to do so by adjacency; the Sea is colored blue. Portugal is colored green (an arbitrary non-blue choice). Spain, which is adjacent to Portugal, is colored red (an arbitrary non-blue and non-green choice); France can be colored green because it is not adjacent to Portugal. Italy can be colored red because it is not adjacent to Spain. Continue around the Sea in clockwise fashion. When the Golan Heights is not included as a part of Syria, Israel, or elsewhere, then Syria and Israel are separated by blank space and can be colored the same color. In that case, a fourth color (black) is not needed until the Gaza Strip, which has a common boundary with both Israel (red) and Egypt (green). However, when the Golan Heights are included as part of Syria (for example), a different coloring pattern emerges (Figure 7.9b). In that case, Israel requires a fourth color, as it is now adjacent to both Syria (red) and Lebanon (green) (and the Gaza Strip can now be colored red). The political boundary issues surrounding the Golan Heights are reflected in the seemingly simple task of coloring a set of nations. Continuing around the Sea, a fourth color is not needed again until Tunisia.

Click to see larger image.

Click to see larger image.

Click to see larger image.

Click to see larger image.

Click to see larger image.

Click to see larger image.

Figure 7.9a (left-hand column). These maps display a coloring of Mediterranean countries excluding the Golan Heights. Click on the maps to see a larger image.

Figure 7.9b (right-hand column). These maps display a coloring of Mediterranean countries including the Golan Heights. Click on the maps to see a larger image.

Possible political hot spots emerge as those nations requiring the fourth color--as regions in which relatively complex political boundary adjacency patterns offer the potential to fuel boundary conflict. Tools that can simplify structural complexity, such as coloring, can offer insight into other issues, as well.

To focus purely on structural/adjacency concerns of this Mediterranean configuration it is an easy matter to convert the maps to graphs. Each region on the map, in the coloring universe, is represented as a node of the graph; an edge joins two nodes if the regions the nodes represent share a common boundary. The nodes are colored with the colors of the underlying countries. The basic graphical structure that emerges is suggestive of the rim of a graph theoretic wheel, with the hub at the Mediterranean (edges joining the rim to the hub are not shown): the shared common resource. Where there are boundary complexities, requiring the introduction of a fourth color, a graph-theoretic cycle appears on the rim of the wheel. Thus, the graphical structure alone also serves as a model suggesting where boundary complexities might emerge in a universe of countries sharing a common resource.

How Many Colors?

In both examples of coloring the Mediterranean map, four colors were required to color the map. They were also enough to color all the states of the United States. However, would four colors always be enough to color any map? The perhaps surprising answer is yes, as long as the map can be embedded in the plane.

It has long been known that there are maps that require four colors, and it had long been conjectured that indeed four colors suffice, as well. In 1941 Courant and Robbins summarized the history of this problem:

The problem of proving this theorem [Four Color Theorem] seems to have been first proposed by Moebius in 1840, later by DeMorgan in 1850, and again by Cayley in 1878. A `proof' was published by Kempe in 1879, but in 1890 Heawood found an error in Kempe's reasoning. By a revision of Kempe's proof, Heawood was able to show that five colors are always sufficient...Despite the efforts of many famous mathematicians, the matter essentially rests with this more modest result: It has been proved that five colors suffice for all maps and it is conjectured that four will likewise suffice. But, as in the case of the famous Fermat theorem..., neither a proof of this conjecture nor an example contradicting it has been produced, and it remains one of the great unsolved problems in mathematics. The four color theorem has indeed been proved for all maps containing less than thirty-eight regions. In view of this fact it appears that even if the general theorem is false it cannot be disproved by any very simple example.

For centuries, mathematicians had concerned themselves with how many colors are needed to color complicated maps of many regions. (Two regions are said to be adjacent, and therefore require different colors, if and only if they share a common edge; a common node, alone, is not enough to force a new color.) The answer depends on the topological structure of the surface onto which the map is projected. When the map is projected onto the surface of a torus (doughnut) seven colors are always enough. Surprisingly, perhaps, that result was known well in advance of the result for the plane (then again, the plane is unbounded and the torus is not). The same number of colors that work for the plane will also work for the sphere (refer to Figure 7.10 in the discussion below).

Consider any map on a sphere. Remove a point, N, in the interior of any region (bounded by a simple closed curve) of the map on the sphere and use N as the projection pole. Use stereographic projection to project the map on the sphere from N into the plane tangent to the sphere at the point antipodal to N. The arrows in Figure 7.10 suggest that the plane extends forever in all directions. Points close to N project to points extremely distant from the point of contact of sphere and plane. The map projected from the sphere into the plane can be colored using X colors. Project the plane map back to the sphere using the same configuration for stereographic projection. Thus, all points but one (N) on the sphere have been colored. Because the added point is a point that is interior to a region of the map, color that point the same color as that of the surrounding region. Hence, X colors also work for the sphere.

Image

Figure 7.10. This figure shows a surrealistic Stereographic projection of the sphere to the plane. Every point on the sphere, except N, projects to a point in the plane. The projection pole, N, maps to infinity under this transformation while the blue region surrounding N projects "close" to infinity at the outer reaches of the plane (as suggested by the arrows and transitional edging to the blue region).

However, it was not until the last half of the twentieth century, aided by the capability of contemporary computing equipment to examine large numbers of cases, that the age-old "four color problem" became the "four color theorem." Appel and Haken (1976) showed that four colors are always enough to color any map in the plane (hence the University of Illinois postage meter stamp of "four colors suffice" announcing this giant result).

Four colors are enough to color any geographic map in the plane in which adjacency of regions is as above. The wary mapmaker should therefore have a reason for using more than four colors: increased communication potential using a ramp with fine gradation or changes in meaning of adjacency might be two good reasons. There are many reasons possible; nonetheless, the careful map-reader when viewing a map of many colors should be able to see why many were used or perhaps question the need for so many colors.

If one thinks of regions as representing physical territory, it makes intuitive sense to consider adjacency as meaning only sharing a common edge (and not merely a common vertex). There are, however, real-world scenarios, such as tracking animal movement through natural habitats by superimposing grid cells in which to take counts, in which it may make sense also to count regions as adjacent that also touch only at a node. A challenge for the future may lie in understanding what the parallel set of theorems might be if "adjacency" also permits the idea of regions being considered geographically adjacent if they share either a common edge or a common node. Will extra colors become necessary?