Graphs: theory and algorithms. (English) Zbl 0766.05001

Thulasiraman, K.; Swamy, M. N. S.

Wiley-Interscience Publication. New York: John Wiley & Sons. xv, 460 p. (1992).

This is essentially a revised version of the authors’ book ‘Graphs, networks, and algorithms’ (1981; Zbl 0528.94034). The main revision consists in omitting Part II of the earlier book, relating to Electrical Network Theory, apparently to bring down the volume. The opportunity of the revision has been utilized to revise and slightly enlarge Part III on Algorithmic Graph Theory.
The first ten chapters of the present book are almost a verbatim reproduction of Part I of the earlier book, except for an occasional inclusion of a few new problems and the addition of some new references at the end of almost every chapter. This part of the book is well suited for a course in basic graph theory for beginners in any scientific or engineering discipline, including mathematics. The treatment level is deeper than what can be found in similar algorithmically oriented books on graph theory and this is quite welcome, as engineering students, especially in the computer science and electrical engineering streams now-a-days need to know the basics of the subject rather thoroughly. The mathematicians will find almost all the standard topics and a few additional ones inspired by the electrical engineering background of the authors. Thus 2-isomorphism is discussed in Chapter 1, and \(k\)-trees in Chapter 2. Chapter 4 contains orthogonal subspaces and their nonempty intersection, an interesting phenomenon in a vector space over \(\mathbb{Z}_ 2\). The coverage of digraphs in Chapter 5 is more detailed than is usual in similar mathematics books. Chapter 6 contains a discussion of spanning 2-trees and Coates and Mason graphs. In Chapter 7, the mathematicians will miss a proof of Kuratowski’s theorem. This, however, is compensated by the introduction of the abstract dual and a proof of Whitney’s theorem. Chapter 8 gives a sumptuous discussion of matchings in bipartite graphs and even includes a proof of Tutte’s 1-factor theorem. In Chapter 9 Vizing’s and Brooks’s theorems and the 5-colour theorem are proved. The chromatic bounds are discussed in the exercises. Chapter 10 provides a good introduction to matroid theory including the greedoids, minors and a discussion of the greedy algorithm. This is a welcome addition not usually found in text books at this level.
Chapters 11 and 12 contain the algorithmic part. The corresponding Part III of the earlier book has been drastically revised and re-arranged. Significant omissions are the algorithms for transitive orientation and maximum matching in a general graph. Additions include algorithms for minimum spanning tree, the Chinese postman problem, \(st\)-numbering of a graph and planarity testing (Lempel, Even and Cederbaum’s algorithm). These and the earlier algorithms for DFS, bipartite matching, biconnected and strong components etc. form the present Chapter 11. The discussion of the flows in network problems has been enlarged to occupy Chapter 12. The treatment of this topic is singularly attractive and contains the pre- flow push algorithm of Goldberg and Tarjan. While the algorithms discussed in this part are certainly the most widely used in applications of graph theory, especially to computer science, the overall presentation is far from systematic and exhaustive to be useful as a complete course in algorithmic graph theory. But the treatment is very uptodate and selected topics can be used in addition to Part I to form a course in graph theory.
The algorithms have been presented in a descriptive step-by-step style, currently out of vogue, especially among computer scientists. This is rather surprising. However traditional teachers and students of mathematics may feel more at home with this transparent style rather than the fashionable pseudo-codes.
In all, the book is sure to be welcomed as a good text book for teaching graph theory with some algorithmic flavour.

Reviewer: K.R.Parthasarathy (Madras)

MSC:

05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05Cxx	Graph theory
05C85	Graph algorithms (graph-theoretic aspects)
68W10	Parallel algorithms in computer science
68R10	Graph theory (including graph drawing) in computer science
90C35	Programming involving graphs or networks

Keywords:

\(k\)-trees; numbering; coverage of digraphs; spanning 2-trees; Whitney’s theorem; matchings; Tutte’s 1-factor theorem; Vizing’s and Brooks’s theorems; 5-colour theorem; chromatic bounds; matroid theory; greedoids; minors; greedy algorithm; Chinese postman problem; planarity; flows in network; pre-flow push algorithm

Citations:

Zbl 0528.94034