The Top 13 Resources for Understanding Graph Theory & Algorithms

Recently we announced the availability of some super efficient graph algorithms for Neo4j. In case you missed the announcement, we now have an easy-to-use library of graph algorithms that are tuned to make full use of compute resources. As part of assisting with this ongoing project, I needed to come up to speed as well as compile a list of graph algorithm and graph theory resources. Although this seemed like a short task, my list grew and continues to grow. So with that in mind, I wanted to share our list of graph theory and algorithms books, resources, and videos. Our team has reviewed many of these but many are still on our to-do list. I’ve noted the Top 13 based on reviews or personal recommendations but included other resources that might warrant a look. You’ll also notice this is broken into two sections: Basics for those getting up to speed on graph technology concepts and Getting Serious for those ready to dive in deep. I hope you have as much fun with these as I have. Please let me know if there are other notable resources I’ve missed or if my rating of the Top 13 is off.

The Basics

These graph theory resources are for those just getting started with graph concepts and business users that need the fundamentals. (Sometimes just certain chapters are even enough.)

• • Introduction to Graph Theory – Trudeau
    • Go from zero understanding to a solid grasp of the basics in just a few weeks.
    • Well written with context for non-mathematicians willing to do basic calculations for proofs.
    • I covered this in two weeks and have no advanced degree in mathematics.
  • First Course in Graph Theory – Chartrand and Zhang
    • Extremely well-recommended. Longer history of graph theory with stress on significance.
    • I was really smitten with this one! It’s a mix of history, context and explanation.
    • Don’t be intimidated by the length or put off by the mix. You don’t have to read every chapter and it really has something for everyone.
  • Graph Theory and Complex Networks: An Introduction – van Steen
    • Reported to be a great introduction with careful attention paid to make the mathematics less intimidating.
  • YouTube: Graph Theory + Series
    • Lots of content from graph theory to algorithms.
  • YouTube: Graph Algorithm Series
    • Good series that is snappy and easy to understand.
  • Free LEDA Chapter (5) on Graph Algorithms
    • Not as reader-friendly as the other items here, but it has sample code you can play with.

Getting Serious

These graph algorithm and theory resources are for those with more mathematics background or ready to spend more time going deep.

• • The Timeless Way of Building – Christopher Alexander
    • This covers classic design concepts for those building anything.
    • I included upon Michael Hunger’s declaration it was the best for learning good design approaches.
  • Network Science – Barabási
    • A good, multidisciplinary approach to networks and complex systems.
    • Many agree it’s extremely readable for a graduate level text with fantastic color graphics.
    • I added this to my queue after seeing the tie to complexity studies and after four chapters I can confirm this is a real gem.
  • The Algorithm Design Manual – Skiena
    • Less academic with good examples that relate to practical problems.
    • There are four chapters focused on graph algorithms as well as sprinkles throughout.
    • Not for the total beginner, but it’s reasonable for most and especially for those building solutions.
    • Although I have no coding background, I’m really enjoying this and find the explanations very understandable. I like the “war stories” sections in each chapter of how things can go wrong.
  • Algorithms – Sedgewick and Wayne
    • A good survey of data structure and algorithms used today with one chapter focused on graph algorithms.
    • I have not not read this but was impressed with all the online supporting material and related MOOC.
  • Introduction to Graph Theory – Douglas West
    • Introduction chapters are reported to be very good but you’ll need some mathematics background.
    • Reviews indicated that the variety of proofs were very helpful.
    • Ongoing updates are online.
  • Graph Theory and Its Applications – Gross and Yellon
    • Highly regarded as a great introduction with some complaints that it jumps around a bit and not as mathematically deep as it could be.
    • I really appreciated the long appendix of use cases and algorithms.
  • Modern Graph Theory – Bollobas
    • You’re going to need a knife and fork for this! But it seems like one of the few highly recommend texts dealing with more recent graph developments.
    • Highly rated for its comprehensive coverage of “every major theorem” and as an indispensable reference for research.
    • This is a mathematics course text with some noting a lack of application and context.

Honorable Mentions

I had to cut the list off somewhere, but I also wanted to you see the other possible resources and provide feedback if you have experience with any of them.

• • Graph Animations with Combinatorica
    • Easy-to-understand visuals, although the companion text didn’t have great feedback.
    • Nice to have a quick link for those that think in pictures.
  • Pearls in Graph Theory – Hartsfield
    • Recommended as an undergraduate-level introduction without a lot of technical detail.
    • This almost made my Top 13 list just because it was so often cited with great fondness. It seems to cover similar topics to the Trudeau work.
  • Introduction to Graph Theory – Wilson
    • Topics are similar to the Trudeau book with some interesting examples and visuals. However, it lacks context and some of the logical explanations of Trudeau.
    • It may be a nice supplement, but I wouldn’t recommend it completely on it’s own.
  • Graph Introduction – Brody
    • Classic course text with expanded and updated version of Brody’s previous work.
    • Reportedly very mathematically focused.
  • Graph Theory – Diestel
    • Online introduction for those with a really solid mathematics base.
  • Algorithms in C++ Part 5: Graph Algorithms – Sedgewick
    • Another Sedgewick with an entire part (series of books) on graphs. It seems to cover some of the same material as the previously listed Sedgewick but in much more detail.
  • A Walk through Combinatorics: An Introduction to Enumeration and Graph Theory – Bona
    • Interesting to look at graph from the combinatorial perspective.
    • The second half of the book is on graph theory and reminds me of the Trudeau book but with more technical explanations (e.g., you get into the matrix calculations).
    • Although interesting, it’s probably best suited for those that really want to dive into the math theory.
  • Network Flows – Ahuja, Magnanti and Orlin
    • Praised for its introduction and integrated network theory, algorithms and applications.
    • Some loved the detailed explanation of why certain algorithms work for network optimization and others felt it was too difficult to understand.
    • I’ve only skimmed this but it’s impressively comprehensive regarding network flows. I would recommend the previously mentioned Network Science for more general network understanding.
  • Analyzing Social Media Networks with NodeXL: Insights from a Connected World – Hansen, Shneiderman and Smith
    • Seems like a good introduction of social network analysis (SNA) but I haven’t read or skimmed it.
  • Networks: An Introduction – Newman
    • Reported to be a great introduction to network theory for anyone with some college level calculus and matrix algebra.
    • Explanations are reported to be clear and thorough.
  • The Fascinating World of Graph Theory – Benjamin
    • Reported to be an entertaining perusal of graph problems but others comment that it’s neither contextual enough for beginners nor detailed enough for those with more background.
  • MITOpenCourseware
    • Graph Theory ++ math for computer science, lectures 6-10
    • Algorithms for specific algorithms of interest

More on YouTube

I’m certain I missed a lot of good videos; there are just too many to review!

• • Very basic concepts clearly explained
  • Good introduction to terminology
  • Similar to some of the others but I like the comparison at the beginning
  • Nice intro with the matrix math relation introduced
  • Simple description of breadth- vs depth-first search
  • Introduction to more specific graph algorithm topics
  • Introduction to graph concepts with some code samples
  • If you have fun with the above, here’s another with Euler circuits and Paths