1
$\begingroup$

What are some families of graphs with known tree width k? For instance, for tree k=1, for cycle k=2, for series-parallel graph which is not a tree k=2, what are some other examples?

I'm looking for some easy to construct families (or famous graphs which I can find in Mathematica's GraphData or on the internet) for testing tree decomposition code.

1 Answers 1

2

Have you tried this website? They have a small collection of graphs and a library for computing their exact tree-width, which you can compare against your code.

You can also try constructing "random" graphs by following the definition, though in that case you only know an upper bound on the tree-width; probably every reasonable way of doing this will actually result in a graph of "most probably" the tree-width you're aiming at.

  • 0
    interesting, thanks. I found Boedlander's website but this seems easier to use2010-11-14