What is topological graph theory? Well, to a large extent it’s just what one would expect: it’s all about methods of topology applied to graph theory. In fact the consultants to the volume under review, Jonathan Gross and Thomas Tucker (who also appear as authors), start off their Foreword by identifying the subject’s roots as belonging to the 19th century with the four-color problem (that every nice-enough planar map can be four-colored). They quickly go on to state that in the next century, in the 1930s, topologists, specifically Kuratowski, MacLane, and Whitney, phrased the indicated assertion in the form of “a question about the structure of graphs that can be drawn without edge-crossings in the plane,” and we are all on familiar ground: nowadays this kind of thinking is part of every mathematician’s toolkit.
Most, if not all, of us find combinatorics memories stirred up by this sort of thing, and rightly so: the four color theorem is really only one of a trio of problems Gross and Tucker characterize as the fount for topological graph theory, the other two problems being the Haewood map problem and the generalized Kuratowski problem, and they characterize “[T]he Ringel-Youngs work [, on the Haewood map problem, as leading] to an alliance between combinatorics and the topology of branched coverings.”
And what then do the Haewood map problem and Kuratowski’s problem assert? Well, P. J. Haewood, it turns out, was the one to discover, in 1890, the error in Kempe’s alleged proof of the four-color theorem, and extend “the quest to finding the colouring numbers of all closed surfaces,” proving in that same year that “a graph embeddable on a surface of Euler characteristic e < 2 can be coloured with at most H(e) colours,” where H(e) is the greatest positive integer less than the value {7 + √(49 - 24e)}/2. “The question of determining the best possible colour bound for each surface became known as the Haewood map problem.” (Cf. pp. 23, 112 of the book under review.)
As for Kuratowski’s problem, or his theorem, well, it states that “[a] graph is planar if and only if it does not contain a subgraph homeomorphic to K5 or K3,3,” where K5 is the complete graph on 5 adjacent vertices and K3,3 is the simple 3x3 bipartite graph each of whose vertices is adjacent to every vertex of the other partite set (cf. loc. cit., p. 11.) More generally (loc. cit., p. 38), “a characterization of graph embeddability in terms of finite sets of graphs has been called a ‘Kuratowski-type’ result.”
Thus, the setting for Topics in Topological Graph Theory, edited by Lowell Beineke and Robin Wilson, is both lovely and familiar, even as it aims at bringing the reader pretty far along in the areas in question (the book being a collection of fifteen more or less autonomous articles, happily with “uniform terminology and notation throughout, in the belief that this will aid readers in going from one chapter to another”). Indeed, say Gross and Tucker: “the individual chapters cover their fields in great depth and detail, so that even specialists will find the book valuable, both as a reference and as a source of new insights and problems.”
Both the editors, Beineke and Wilson, and the “Academic Consultants,” Gross and Tucker, appear as authors of some of the aforementioned fifteen chapters, which deal with embeddings in many different contexts, graph minors (generalizing Kuratowski), colorings, crossings, enumerations, symmetric maps, group genera, and infinite graphs. The final chapter, by Dan Archdeacon, deals with open problems, so, to be sure, this book is one of the places to go for a researcher new to the field to get off the ground.
The editors note in their Preface that Topics in Topological Graph Theory is offered as a companion to their 2004 book on algebraic graph theory; it is evident, however, that these books (the present being the second of a projected three) are autonomous. It is certainly a marvelous book on an eminently seductive topic. It should make quite a good impact on its intended audience, old hands as well as neophytes.
Michael Berg is Professor of Mathematics at Loyola Marymount University in Los Angeles, CA.