This is a huge book, almost 200 pages longer than the already massive first edition. One is tempted to call it "Everything You Wanted to Know about Graph Theory but Were Afraid to Ask". Nonetheless, Graph Theory and Its Applications is a very good textbook.
What makes it good is strong rapport with the reader, a coherent organization, and consistently clear exposition. The book is aimed at a diverse set of readers. Courses based on this book could be directed toward computer science (concentrating on data structures and algorithms), operations research (focusing on discrete optimization), or mathematics (emphasizing the algebraic and topological aspects). The text is most appropriate for advanced undergraduates or beginning graduate students. Since it is essentially self-contained, it could also be used profitably for self-study.
The basics of graph theory (structure and representation, trees, connectivity, optimal transversal of graphs) are covered well in the first six chapters. Planarity and Kuratowski's theorem are discussed in depth in Chapter 7 where the authors begin their treatment of topological graph theory. There is a strong chapter on network flows and applications, and another on digraph models. Later chapters take up more advanced topics (enumeration, voltage graphs, design of nonplanar layouts). New to this second edition of the text are treatments of Ramsey theory as well as random graphs, an especially hot topic now.
Notable attractive features of the text are breakout boxes with pseudo-code for all significant algorithms (as well as suggestions for specific software implementations), hundreds of examples of graphs carefully integrated with the text, a glossary of terms with each chapter (especially useful in this terminology-heavy field), and a ton of exercises — many with solutions or hints. My only real quibble is that the pages all seem too full. No doubt this was in effort to keep the number of pages down in an already large book. But one wishes for more white space.
Of course, there are practical applications too. If you are ever caught in a maze consisting of tunnels and rooms, use Tarry's algorithm (page 189) to escape, using a variation on depth-first search. Never backtrack through a tunnel unless there is no alternative, and never go through a tunnel a second time in the same direction.
Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.