Why learn Graph Theory? Here are some reasons ...

In either case, after a certain amount of analysis you'll end up with a set of nodes (typically basic blocks) which connect to each other, but they'll be what I call 'immature' nodes. You know they connect, but they all effectively end with gotos. To make any sense of them, you have to make them into mature nodes: if, if-else, while, do-while, for, etc. Via graph reduction this is possible.

For instance, a few years back I was reverse-engineering Apple's Fairplay DRM and ran into an odd obfuscation scheme. There were dozens of functions which had the same structure: a switch inside a while statement; a state machine. After some hand-analysis, I figured out that at the end of each state, it'd set the state variable to either a constant value (a jump) or one of two conditional values (a conditional branch). At this point, it became clear that they were simply taking basic blocks and turning them into a big obfuscated state machine.

To make this into something worthwhile, I wrote a script that would go through the function and 'execute' it, to determine the state connections automatically. Then from there, I wired them up into a big graph, with two types of nodes: Fallthrough (no conditional) and Branch (conditional). Now, that helps a lot in terms of showing you what's happening, but not nearly as much so as control flow structures do, so the battle was only half over.

Now, if you look at common control flow structures from a graph perspective, they all look pretty straightforward (using something like dot graph notation):

    A; if(X) {B} else {C} D  becomes A -> B, A -> C, B -> D, C -> D.
    A; if(X) {B} C  becomes A -> B, A -> C, B -> C
    A; while(X) {B} C  becomes A -> B, A -> C, B -> C

I found that a huge benefit of knowing some graph theory lies in being able to approach problems where this transformation is easy - neither trivial nor hard, but easy once you have some experience and intuition working with graphs. Every time you have a bunch of entities, and you can kinda think of their interdependencies as a binary relationship of some sort, there's a warning bulb going off in your brain - "is this a graph problem?". And if it is, then very possibly you immediately get lots of insight into your problem, basically for free.

This occurred to me a few weeks ago as I was thinking about this puzzle: design a circuit that inverts three inputs, but uses only two NOT gates (plus arbitrary amount of ORs and ANDs). It's an interesting puzzle to solve manually, but I also wanted to quickly write a program to find the solution. Circuits are trivially graphs, but there're too many of them (an infinity) to iterate over. Once you see the problem as a reachability problem in a certain fixed graph, however (easy, but not trivial), the code writes itself. Someone with no exposure to graph theory might easily just balk at this easy problem, not knowing how to proceed.

But you do get to use graphs to solve the component placement problem, in heuristics that try to minimize total wire length. That hopefully means that wiring delays are smaller, and routing more feasible. One of the classic heuristics involved successive bipartions on the min-cut of the graph.

Nitpicking aside, it's a good post, well argued. My intro book recommendation: http://www.reddit.com/r/mathbooks/comments/aho2h/graph_theor...

Apparently, the interference graphs that arise from SSA code are a well-behaved sort of graph, colorable in polynomial time.

http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/6532

Off topic, but: since so many things are well described as graphs, the GraphViz tool is great for communication: few lines of code to write your data to a 'dot' file, and a few seconds later you have a visual representation of your data.

I've run into a number of forest problems due to distributed systems.