Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Basic graph theory
Rahman M., Springer International Publishing, New York, NY, 2017. 169 pp. Type: Book (978-3-319494-74-6)
Date Reviewed: Sep 29 2017

Graph theory is fundamental to many modern algorithms in computer science (CS). Basic graph theory provides an introduction to the concepts for undergraduates. Unfortunately, the book is flawed in several respects.

Rooted in mathematics long before computers existed, graph theory necessarily starts from definitions and advances through basic proofs of various lemmas and theorems. For an undergraduate text intended for computer scientists, it might be assumed that the student does not have a solid background in proving theorems. Basic graph theory is not necessarily a good standalone book for introducing these concepts. Proofs are sketches most of the time and often left to the reader, as if the reader were an advanced mathematics student.

The fundamentals of the book are also weak. There are many spelling errors and other typographical errors throughout. The words “plane” and “plain” are mixed up in an early example. The index is slim and does not include references to every instance of any given word. Key CS terms like algorithm, polynomial time, and NP-hard are used throughout the book, but not included in the index. They are not defined in the book, so the reader is assumed to be a fairly advanced CS student; however, the introduction does not list any prerequisites the reader might need. Finally, the examples given are sometimes unclear or incomplete to an undergraduate who is being exposed to this material for the first time. An early example of floorplanning refers to an operation on the graph, but it is unclear what the actual operation is.

For the most part, the introduction of the material is logical and well ordered. It begins with some applications of graph theory and then delves into the terminology. Paths, cycles, and connectivity are covered before trees are dealt with. Matching and covering algorithms are covered in depth, and then plane graphs are introduced. Naturally, coloring and then digraphs follow.

Finally, specialized graphs such as outerplanar graphs are introduced, including algorithms known to work on special graphs. The last chapter is on research topics, which are always good to introduce to advanced undergraduate CS students, particularly since graph theory contains many open problems for ongoing research.

With some attention to detail, the next edition of this book could be very useful. With its current flaws, the instructor will be relied upon heavily to clarify and correct certain concepts.

Reviewer:  William Fahle Review #: CR145569 (1712-0774)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Graph Theory (G.2.2 )
 
 
Reference (A.2 )
 
Would you recommend this review?
yes
no
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
more...

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