Friday, January 21, 2011

Tree decomposition package

A tree decomposition is a representation of a complete set of vertex separators of a graph. For instance, here's an Apollonian Network and its tree decomposition.

Decomposition above shows off 121 vertex separators of size 4, represented as non-leaf nodes, each separating graph into 3 parts, and 363 vertex separators of size 3, represented as edges, each separating the graph into 2 parts.

I put the tree decomposition code in a package. Unzip the file into any folder, and execute cells in treeDecomposition-usage.nb for the decomposition above. It takes 2 minutes for 367 vertex Apollonian network above. Graphs with around hundred vertices should take a few seconds.

Generally, to do a visualization like above, you'd do the following

<< Bulatov`treeDecomposition`;
g = GraphData[{"Apollonian", 5}];
{nodes, edges} = findTreeDecomposition[g];
GraphPlot[Rule @@@ edges]

Tree decomposition package


  1. This may be because I'm using M7 instead of M7, but the call to GraphData in the example gives me a Graphics expression, rather than a Graph, and findTreeDecomposition[g] doesn't evaluate.

  2. This package uses M8's graph theory stuff heavily, so you need M8 to run it

  3. Hello again, Yaroslav. I ended up implementing the necessary M8 graph theory stuff, so that your package would run in M7. After doing so, I was able to use your package as part of the software that makes up my PhD thesis.

    I am now getting ready to finish writing this up, and I have a few questions. One is, how would you like the software credited in my document? Secondly, do you mind if I include your software in the package I distribute (attributed by appearing as a subdirectory called 'Bulatov', and with appropriate comments linking here at the head of treeDecomposition.m). If this is not satisfactory, I will be happy to instead include instructions for how to download the package here.

    (I apologize for using this public forum for somewhat official business, but I didn't see an email address while poking around here for about ten minutes. If you would like, I can be contacted directly at johnsong at

  4. Sure, that works, you can just give a link to this post
    BTW, my email is

  5. This comment has been removed by the author.

  6. Good idea. Thank you for sharing with us.