Topological graph theory. (English) Zbl 0621.05013

Gross, Jonathan L.; Tucker, Thomas W.

Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. New York etc.: John Wiley & Sons. XV, 351 p. £55.00 (1987).

During the last two decades, topological graph theory has become not only an integral part of graph theory, with close relations to group theory and surface topology, but also an interesting and important theory on itself. It comprises now all kinds of surface imbedding problems (including algorithms), covering space constructions (branched coverings, wrapped coverings, etc.), analysis of imbedding distribution, forbidden subgraph characterizations, genera of groups, map-theoretic connections, representation of higher-dimensional manifolds by graphs, and many others.
For some of these topics, the present monograph is the first complete treatment in book form. It provides a unified and systematic account of the foundations and basic techniques in topological graph theory, covering the development in the last twenty years which to some extent is due to the authors themselves. The form of the book is introductory, so besides the central concerns of topological graph theory the authors have made a special point of connecting the subject with frontier topics and other areas of mathematics.
The first chapter reviews some facts from graph theory that are of some importance from the topological point of view. Since the theory of voltage graphs and covering spaces is used throughout, Chapter 2 is devoted to a presentation of this theory for readers unfamiliar with it. Likewise, the next chapter dealing with surface classification and graph imbeddings has been included to make the book more self-contained. Chapter 4 presents a fairly detailed description of the principles and practice of imbedding constructions, with a particular emphasis on lifting techniques, group acting on surfaces, and the voltage-current duality. The foundations thus established are used in Chapter 5 for a comprehensive explanation of the very lengthy proof of the famous Ringel- Youngs theorem in a modern setting. In the final chapter, the authors examine main results on the genus of a group and introduce some of the adequate proof techniques.
Many of the topics listed here are presented in a novel way, supported by numerous well-chosen examples. Further examples, as well as new results, appear in the exercises at the end of each sub-chapter. The 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 numerous figures.
The exposition is self-contained, so that readers with a minimal background in undergraduate discrete mathematics should follow it easily. In particular, first year graduate students would benefit greatly from the way of presentation which is neither abstract nor highly theoretical. On the whole, the monograph provides both the advanced student and the specialist with a very good working text.
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 decompositions and graph imbeddings; The classification of surfaces; The imbedding distribution of a graph; Algorithms and formulas for minimum imbeddings. - 4. Imbedded voltage graphs 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. - Table of Notations. - Subject Index.

Reviewer: J.Śiráň

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

genus of graph; Cayley graph; topological graph theory; group theory; surface topology; surface imbedding problems; voltage graphs; covering spaces; Map colorings; genus of a group; symmetric genus