Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The fascinating world of graph theory
Benjamin A., Chartrand G., Zhang P., Princeton University Press, Princeton, NJ, 2015. 344 pp. Type: Book (978-0-691163-81-9)
Date Reviewed: Jul 27 2015

What could be simpler than graph theory? While it may be just a bunch of dots connected by some lines, graph theory is also very general because it encompasses all two-place relations. Because of this simplicity and generality, graph theory is an ideal vehicle to expose people to real mathematics (beyond usual arithmetic) while appealing to their intuition and sense of fun.

The authors have produced a book that falls between a popularization and a text. They have concocted a nice mix of storied problems, historic vignettes, and theorems that make for long stretches of easy reading with occasional slow-downs to ponder proofs.

The book opens with a number of classic problems that are given as stories and then represented as graphs; the problems are then restated as graph theory problems.

The remaining 11 chapters, each of about 20 pages, cover portions of graph theory. For example, there are chapters on trees, distances, traversals, classification, encircling, factoring and matching, decomposition, orienting, drawing and planar graphs, coloring, and even Ramsey theory. The stories of the people who solved the problems are included along with the discussion of the problem. Solutions are given to many classical problems including what may be the oldest solution to the Knight’s tour. There are also some more modern problems including the solution to Instant Insanity via graph factoring.

The book contains many diagrams and is notably free from typographical errors. I caught a few: Erno Rubick is given as “Emo Rubick,” and Figure 9.8 is missing one arrowhead. The history seems to be correct and is more detailed than in other books, but the authors’ version of the Courant/Robbins story differs a little from the stories I’ve heard.

Computer science instructors may be disappointed to see so little discussion of algorithms. Complexity is hinted at, but NP-completeness is, wisely, not mentioned. Such instructors might prefer the classic books by Deo [1] and Even [2].

The main body of the book is about 250 pages, and this is followed by 50 pages of exercises. There is clearly enough here for a one-term undergraduate course. I enjoyed reading this book, and I believe that other teachers will similarly enjoy it and find some tidbits to use in their courses. Finally, this book is easy enough to read that bright high school students will also find it fascinating.

More reviews about this item: Amazon, Goodreads

Reviewer:  Paul Cull Review #: CR143655 (1510-0863)
1) Deo, N. Graph theory with applications to engineering and computer science. Prentice Hall, Englewood Cliffs, NJ, 1974.
2) Even, S. Graph algorithms. Computer Science Press, Potomac, MD, 1979.
Bookmark and Share
  Reviewer Selected
Editor Recommended
Graph Theory (G.2.2 )
Introductory And Survey (A.1 )
Would you recommend this review?
Other reviews under "Graph Theory": Date
Graphs and algorithms
Gondran M., Minoux M. (ed), Vajda S., John Wiley & Sons, Inc., New York, NY, 1984. Type: Book (9789780471103745)
Jan 1 1985
On graph rewritings
Raoult J. Theoretical Computer Science 32(1-2): 1-24, 1984. Type: Article
Sep 1 1985
Non-partitionable point sets
Avis D. Information Processing Letters 19(3): 125-129, 1984. Type: Article
Jul 1 1985

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy