What are some exceptional graph theory books geared explicitly towards real-world applications?

I would be interested in both general books on the subject (essentially surveys of applied graph theory as a discipline) as well as books about specific applications.

One may assume up to a year-ish of graph theoretic background. I am not looking for an introductory graph theory book, nor am I interested in pure graph theory books containing only a few canonical applications (e.g. Bondy & Murty's GTWA). The book should contain as much exposition connecting the mathematics to the real world as possible, as well as exercises and concrete examples related to applications themselves (e.g. "design a traffic network given the following constraints").

Please mention in your answer what the book does well which sets it apart from others, e.g. "Book X has a great section on graph theory in computational geometry."

  • 3
    $\begingroup$ This is a really good question. Maybe you could try the computer science sister sites/MO if you don't get an answer. $\endgroup$ – Paul Gustafson Apr 10 '13 at 1:23

I highly recommend: Graph Theory and Its Applications to Problems of Society by Fred S. Roberts, Series: CBMS-NSF Regional Conference Series in Applied Mathematics(No. 29),ISBN:9780898710267, 1987.

This book is extremely well written and despite the fact that it dates back over 20 years surveys applications of graph theory to assigning directions to streets, routing problems, scheduling questions, etc.

  • $\begingroup$ Thank you. I have just bought this book and intend to read and work through it this summer. $\endgroup$ – Alexander Gruber Apr 26 '13 at 23:34
  • $\begingroup$ Update: I have finished reading and liked the book quite a bit. Thanks. $\endgroup$ – Alexander Gruber Mar 16 '14 at 7:50

There is an area of very active research that has direct connections with the graph theory: I am talking about what is commonly called the network science. It usually includes statistical analysis of real world networks, random graph theory as a null model, dynamical processes on random graphs such as percolation or epidemic spread, and mathematical models of network formation.

Two recent books that both heavy on the theory and applications are

The first book is slightly more theoretical in nature and includes a lot of derivation of simple results. It also has quite a detailed discussion of real world networks. The second book is more oriented to the description of various social, economic, etc situations where network analysis allows to make some conclusions.


I would like to mention another nice book about the applications of graph theory, which though I don't think it has all of the virtues of Fred Roberts' book Graph Theory and its Applications to Society, already mentioned, is none-the-less worth a look. The book is: Applications of Graph Theory, editors, Robin Wilson and Lowell Beineke. The book was published by Academic Press in 1979. Its age makes it somewhat "dated" but it still has some rather nice things. Chapters include Graph Theory and Communications Networks (definitely dated), Graph Theory and Electrical Networks, Chemical Applications of Graph Theory, Graph Theory and Operations Research, Graph Theory and Geography, Graph Theory and the Social Sciences (written by Fred Roberts), Architectural Applications of Graph Theory, Graph Theory and Lingistics, etc. (There are total of 13 independent chapters.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.