Someone today asked me: why graphs? “Why are graphs so widely used in computer science, and in related fields such as software engineering?” Here's my glib response:

The short answer is that graphs can be used to reason symbolically about any kind of pairwise relationship between any kind of entity, and that we like to think about pairwise relationships because unary relationships aren't powerful enough and \( k \)-way relationships for \( k\gt 2 \) add extra complication without adding any real power.

So already in 1736 Euler was using graphs to model transportation connections between pairs of places (the bridges of Königsberg; more modernly this idea shows up in airline ticket planning, where the vertices represent airports and the edges represent flights, or in mapquest-like route planning, where the vertices represent road intersections and the edges represent intersection-free segments of roads). We have graphs representing people and social networks connecting them (online friendships, sexual contacts, parenthood, coauthorship, etc). We have graphs representing subroutines in a computer program and caller-callee relations between them. We have graphs representing web pages and html links between them. We have graphs representing proteins in your body and the chemical interactions they participate in. Etc etc.

Graphs are powerful because the same kinds of problems and algorithms turn out to be important in many of these different applications. So by taking away the application-specific features of all of those different problems and turning them into something as abstract as a graph, we only have to solve these problems once instead of repeatedly solving the same problems in different disguises.




Comments:

None:
2009-02-12T08:18:53Z
that's the explanation I give as well. Very well written.
11011110:
2009-02-12T15:11:43Z
Thanks!
None: k-relationships
2009-02-12T08:33:46Z
\( k \)-way relationships for \( k\gt 2 \) add extra complication without adding any real power
Is there any way of understanding why this is the case, and in what way? What would be the formally equivalent statement?
11011110: Re: k-relationships
2009-02-12T15:10:39Z
I meant something mildly technical by this: one can define k-ary hypergraphs for any k, of course, but they're just the same things as bipartite graphs. So the hypergraph point of view doesn't really get you away from graphs.
None: Re: k-relationships
2009-02-13T00:43:05Z
Yes, but the language of hypergraphs can be very convenient. Just as an example (but many others could be provided) see Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes JACM 1983, and G. Gallo et al. Directed hypergraphs and applications Discrete Applied Mathematics 1993
leonardo_m:
2009-02-12T11:21:22Z
It looks fit for the Wikipedia page about graphs.
11011110:
2009-02-12T15:17:44Z
Yeah, I see that it has only a brief and easily missed line about this before going into the more dry technical material. I'll have to see what I can dig up in the way of reliable sources that would let me add it there; I don't think it should be too difficult.
None: Agreed!
2009-02-12T14:36:32Z

Wow, I just did my first graph lecture for Algs and Data Structures Tuesday, and you said very nicely what I HOPE the students took away from the first part of the lecture -- where I ask them to think of examples of data that can be modelled as graphs. But you said it very clearly.

Michael Mitzenmacher

11011110: Re: Agreed!
2009-02-12T15:18:34Z
Thanks! That's where I usually put it in my algorithms classes, too.
None: Great Comments!
2009-02-12T22:48:50Z

This is great! I hope Graph theory community also sees this comment (and perhaps it helps for grant proposal as well)..

Also, I hope TCS realizes how important Graph Theory is. (Seriously! Graph Theory creates a lot of "exciting" and "deep" theories in the last two decades or so! If one only knows Graph Theory 30 years, he or she may object this point, though..)

Thanks.

Ken-ichi Kawarabayashi

None: Energy Landscape?
2009-02-13T07:25:00Z

Hi,

I am a biologist, and I encounter the following graph-theoretic(I think) problem:

We have a big graph with billions of of nodes, and for each node we can assign a real value-"height" to it. Then we want to obtain a global view of this landscape and try to study some property of this graph.

Does this kind of situation sounds familiar to you?

Thank a lot!!!