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

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.

ReplyDelete*M7 instead of M8.

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

ReplyDeleteHello 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.

ReplyDeleteI 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 ics.uci.edu.)

Sure, that works, you can just give a link to this post

ReplyDeleteBTW, my email is yaroslavvb@gmail.com

This comment has been removed by the author.

ReplyDeleteGood idea. Thank you for sharing with us.

ReplyDeleteMathematica