Fun with Graph Theory

I asked a question in twitter about graph theory the other day. Unsurprisingly, it was tricky to convey what I wanted to know in such a short span. So this explains what i was wondering in more depth.

I’ve got a problem involving graph layouts (think dot and graphviz) I want to write a GUI program that lets the user draw directed graphs interactively. That is, they start with a single node. Then, to modify that graph, there are five basic operations:

• add a node above: that is, a node A becomes the graph B -> A
• add a graph below: A -> B
• add an edge between two nodes
• delete an edge
• delete a node, and all connecting edges

And what I’d like to know is; to keep the UI responsive, can I precalculate the positions of every possible graph ahead of time? When the user makes a change, I can refer to the precalculated positions and keep the UI experience really fast.

This depends on how many possible nodes there are. If I am only ever going to see, say, 500,000 possible layouts, it is possible to just spend a couple of days chugging through all the possible configurations and saving them in a database.

Without any more limits, this is impossible — there are an infinite number of graphs. But I think I can make reasonable guesses about the types of graph I’m likely to see in my app. For instance;

• the graph is always connected
• no two nodes have a duplicate edge
• the graph has no cycles
• Nodes generally won’t have more than about five incoming nodes and five outgoing nodes
• A graph probably won’t have more than about 100 nodes in it

So here’s how I formulated the problem;

Given a directed acyclic graph with N nodes, where no node has more than E total incoming and outgoing nodes, how many possible graphs are there?