Topological graph theory. (Q2732568)

From the authors' preface to the Dover edition: ``When the original edition of this book went to press in 1985, research activity in topological graph theory was still dominated by group-theoretic structures with close connections to classical, low-dimensional algebraic topology: Cayley graphs, regular branched coverings, and group actions on graphs and surfaces. These structures had enabled us to present a unified context for the study of graphs and surfaces. Within that context, we were able to describe not only the Ringel-Youngs solution to the Heawood map-coloring problem and the principal results on the genus of a group, but also the incipient programmatic themes of genus distribution and enumeration. Another emerging theme at that time, not fully launched, was algorithmics. At the time of publication of this Dover reprint, the field is most heavily influenced by the methods developed within a series of more than several dozen papers by Robertson and Seymour, all published since 1983, whose outcome included solution of the Kuratowski problem for general surfaces. Whereas the classical Kuratowski theorem is that there are exactly two obstructions to imbedding a graph in the sphere, namely \(K_5\) and \(K_{3,3}\), the general Kuratowski problem is to decide whether the set of obstructions is finite, which Robertson and Seymour settled affirmatively. Since the Kuratowski problem does not come with any symmetry, this achievement, no less notable than that of Ringel and Youngs, is accomplished with purely combinatorial methods, involving no group-theoretic structure at all. The monograph \textit{Graphs on Surfaces} by Mohar and Thomassen, whose publication is expected to be contemporaneous with that of this new edition of \textit{Topological Graph Theory}, provides the definitive account of developments in this branch of topological graph theory, sometimes called ``structural graph theory'' by its practitioners, who are referring largely to matroidal structure, not to group theory. Indeed, it is particularly felicitous that this reprint of \textit{Topological Graph Theory} coincides with the publication of \textit{Graphs on Surfaces}, since the two books complement each other so well and overlap so little. A third monograph of interest, \textit{Graphs, Groups and Surfaces: Interactions and Models} by Arthur White, is also close to completion. It further updates the 1984 edition of the classic text with new material on enumerative and random topological graph theory, as well as graph imbedding models for finite fields and geometries. The algebraic branch of topological graph theory has flourished in many ways since 1985. It includes substantial work on regular and edge-transitive maps, Cayley maps, enumeration of regular coverings, groups of low symmetric genus, exploration of the non-uniqueness of triangular imbeddings of complete graphs, and lifting of morphisms. The enumeration and structure of the collection of all imbeddings of a given graph is clearly algebraic, as is much of the work on random graph imbeddings. In structural graph theory, there has been extensive work on edge/face width and its connections to planarity, tree width, the existence and structure of noncontractible cycles in imbedded graphs, algorithms and their complexity for various graph imbedding problems, and the flexibility of imbeddings of a graph in a given surface.'' NEWLINENEWLINENEWLINEFifteen years after its first appearance, \textit{Topological Graph Theory} still serves as a valuable textbook and research resource. In the first chapter, graph-theoretical facts that are important for the study of imbeddings are reviewed. Voltage graphs and graph coverings are introduced in Chapter 2. The next chapter deals with basic results in imbedding graphs on surfaces and includes an outline of classification of compact surfaces. Chapter 4 brings a detailed presentation of principles and practice of constructions of imbeddings based on lifting techniques by means of voltage and current graphs. The use of these is also illustrated in Chapter 5 in a comprehensive explanation of the proof of the famous map color theorem. In the final chapter, the authors concentrate on group actions on surfaces and present various techniques and results related to computing the genus of a group. For the Dover reprint, the authors have made no changes in the text. However, they have included a supplement to the original bibliography, covering the areas related to groups acting on surfaces and to symmetries of imbeddings. Throughout, the exposition of material is complemented by numerous well-chosen examples. Further examples and results appear in exercises at the end of each sub-chapter. Exercises are often provided with helpful hints and, in some cases, with outlined solutions. An attractive characteristic of the book is that it appeals systematically to the reader's intuition and vision by a large amount of figures. Especially graduate students (but also researchers that are not specialists in the field) will appreciate the presentation that is neither abstract nor highly theoretical. Besides central concerns of imbeddings and their symmetries the authors have made a special point of linking the subject with frontier topics and with other parts of mathematics. On the whole, \textit{Topological Graph Theory} is an excellent monograph, and I would recommend it highly as both graduate textbook as well as reference. Contents: 1. Introduction: Representation of graphs; Some important classes of graphs; New graphs from old; Surfaces and imbeddings; More graph-theoretic background; Planarity. 2. Voltage graphs and covering spaces: Ordinary voltages; Which graphs are derivable with ordinary voltages?; Irregular covering graphs; Permutation voltage graphs; Subgroups of the voltage group. 3. Surfaces and graph imbeddings: Surfaces and simplicial complexes; Band decomposition and imbeddings; The classification of surfaces; The imbedding distribution of a graph; Algorithms and formulas for minimum imbeddings. 4. Imbedded voltage and current graphs: The derived imbedding; Branched coverings of surfaces; Regular branched coverings and group actions; Current graphs; Voltage-current duality. 5. Map colorings: The Heawood upper bound; Quotients of complete-graph imbeddings and some variations; The regular nonorientable cases; Additional adjacencies for irregular cases. 6. The genus of a group: The genus of abelian groups; The symmetric genus; Groups of small symmetric genus; Groups of small genus. References. Bibliography. Supplementary bibliography. Table of notations. Subject index.