The Top 13 Resources for Understanding Graph Theory & Algorithms

Recently we announced the availability of some opens in new tabsuper 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.)

• • opens in new tabIntroduction 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.
  • opens in new tabFirst 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.
  • opens in new tabGraph 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: opens in new tabGraph Theory + Series
    • Lots of content from graph theory to algorithms.
  • YouTube: opens in new tabGraph Algorithm Series
    • Good series that is snappy and easy to understand.
  • opens in new tabFree 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.

• • opens in new tabThe Timeless Way of Building – Christopher Alexander
    • This covers classic design concepts for those building anything.
    • I included upon opens in new tabMichael Hunger’s declaration it was the best for learning good design approaches.
  • opens in new tabNetwork 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.
  • opens in new tabThe 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.
  • opens in new tabAlgorithms – 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.
  • opens in new tabIntroduction 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.
    • opens in new tabOngoing updates are online.
  • opens in new tabGraph 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.
  • opens in new tabModern 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.

• • opens in new tabGraph 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.
  • opens in new tabPearls 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.
  • opens in new tabIntroduction 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.
  • opens in new tabGraph Theory – Diestel
    • Online introduction for those with a really solid mathematics base.
  • opens in new tabAlgorithms 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.
  • opens in new tabA 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.
  • opens in new tabNetwork 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.
  • opens in new tabAnalyzing Social Media Networks with NodeXL: Insights from a Connected World – Hansen, Shneiderman and Smith
    • Seems like a good introduction of opens in new tabsocial network analysis (SNA) but I haven’t read or skimmed it.
  • opens in new tabNetworks: 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.
  • opens in new tabThe 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
    • opens in new tabGraph Theory ++ math for computer science, lectures 6-10
    • opens in new tabAlgorithms 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!

• • opens in new tabVery basic concepts clearly explained
  • Good introduction to opens in new tabterminology
  • Similar to some of the others but I like the opens in new tabcomparison at the beginning
  • Nice intro with the opens in new tabmatrix math relation introduced
  • Simple description of opens in new tabbreadth- vs depth-first search
  • Introduction to opens in new tabmore specific graph algorithm topics
  • Introduction to opens in new tabgraph concepts with some code samples
  • If you have fun with the above, here’s another with opens in new tabEuler circuits and Paths