You are here

Topics in Topological Graph Theory

Lowell W. Beineke and Robin J. Wilson, editors
Cambridge University Press
Publication Date: 
Number of Pages: 
Encyclopedia of Mathematics and Its Applications 128
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Michael Berg
, on

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.

Preface; Foreword Jonathan L. Gross and Thomas W. Tucker; Introduction Lowell W. Beineke and Robin J. Wilson; 1. Embedding graphs on surfaces Jonathan L. Gross and Thomas W. Tucker; 2. Maximum genus Jianer Chen and Yuanqiu Huang; 3. Distributions of embeddings Jonathan L. Gross; 4. Algorithms and obstructions for embeddings Bojan Mohar; 5. Graph minors: generalizing Kuratowski's theorem R. Bruce Richter; 6. Colouring graphs on surfaces Joan P. Hutchinson; 7. Crossing numbers R. Bruce Richter and G. Salazar; 8. Representing graphs and maps Tomaž Pisanski and Arjana Žitnik; 9. Enumerating coverings Jin Ho Kwak and Jaeun Lee; 10. Symmetric maps Jozef Širáň and Thomas W. Tucker; 11. The genus of a group Thomas W. Tucker; 12. Embeddings and geometries Arthur T. White; 13. Embeddings and designs M. J. Grannell and T. S. Griggs; 14. Infinite graphs and planar maps Mark E. Watkins; 15. Open problems Dan Archdeacon; Notes on contributors; Index of definitions.