Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
interesting, thanks. I found Boedlander's website but this seems easier to use – Yaroslav Bulatov Nov 14 '10 at 20:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.