# Application of graph theory in computer science

I am a CS student. We did graph theory in one course. I found it interesting.

What are the real applications of graph theory in the computer science field?

For example, I found that some concepts in graph theory can be used to design networks. What are other similar applications?

• this could be an awfully long list. I'm thinking CW ? Feb 14 '11 at 6:24
• This seems a little too general even for a CW. Graph theory is ubiquitous in TCS. Feb 14 '11 at 7:05
• Asking for topics in CS that do not use graphs might have yielded the shorter list. Feb 14 '11 at 7:14
• @peedarpk: If you're following a class on graph theory in a CS cursus, why don't you ask the professor? Feb 14 '11 at 9:03
• Really, can we close this now? The answer to this question is on wikipedia (en.wikipedia.org/wiki/Graph_theory#Applications) or in any introductory undergraduate textbook.
– RJK
Feb 16 '11 at 14:25

This is in no way a definitive answer, and I do not intend it as such.

Many problems of interest to computer scientists can be phrased as graph problems, and as a result graph theory shows up quite a lot in complexity theory. The computational effort required to determine where two graphs are isomorphic, for example, is currently a topic of much interest in complexity theory (it is neither known to be NP-complete nor contained in P, BPP or BQP, but is clearly in NP). Graph non-isomorphism, on the other hand, has a very nice zero-knowledge proof (another area of study in complexity theory). Many complexity classes have graph problems which are complete for that class (under some reduction).

However it is not just complexity theory that makes use of graph theory. As you can see from some of the other answers, there is quite an array of problems for which the language of graph theory is most appropriate. There are far to many applications to provide a diffinitive list, so instead I will leave you with an example of how graph theory plays a fundamental role in my own area of research.

Measurement-based quantum computation is a model of computation which does not have a counterpart in the classical world. In this model, the computation is driven by making measurements on a special class of quantum states. These states are known as graph states, because each state can be uniquely identified with an undirected graph with a number of vertices equal to the number of qubits in the graph state. This link with graph theory is more than coincidental, however. We know that an important class of measurements (Pauli-basis measurements in case you are interested) map the underlying graph state to a new graph state on one less qubit, and the rules by which this occurs are well understood. Further, properties of the underlying graph family (it's flow and g-flow) determined fully whether it supports universal computation. Lastly, for any graph G' which can be reached from another graph G by an arbitrary sequence of complementing the edges of the neighbourhood of a vertex can be reached by single-qubit operations alone, and so are equally powerful as a resource for computation. This is interesting because the number of edges, maximum of the vertex degrees, etc. can change drastically.

• Great answer to what the OP was unlikely to have been asking! But topically, why don't we forget the original (bad) version of the question and pretend we're playing Jeopardy: "What is the intuition behind the ubiquity of graphs in nearly all sub-disciplines of theoretical computer science?"
– RJK
Feb 16 '11 at 18:01
• @RJK: Perhaps I should have read the question more carefully, but I thought this might at least be interesting to the person asking the question. Feb 16 '11 at 18:06
• No no, this was a great answer. Sep 26 '16 at 13:57

Applications of graph theory are abundant within computer science and in every day life:

• Finding shortest routes in car navigation systems
• Search engines use ranking algorithms based on graph theory
• Optimizing time tables for schools or universities
• Analysis of social networks
• Optimizing utilization of railway systems
• Compilers use coloring algorithms to assign registers to variables
• Path planning in robotics

Graph Theory has a variety of applications. My favorite ones are the applications in:

• Large Scale Networks
• Social Computing
• Bio-informatics

Modelling networks are done using graphs. For example if you need to study broadcasting or multicasting in certain types of network topologies you would use graphs to model the networks. For example:

• hypergraphs
• complete graphs
• star graphs
• meshes

When you model networks using graphs you can use all the power of graph theory to analyse the network.

This is just one fo many applications of graph theory in computer science.

The directory structure is a tree structure(with root nodes and child nodes. In networks it's used to find the shortest route using the minimum spanning tree,Dijkstra's algorithm.

I once applied graph theory in a ladder diagram editor and compiler.