Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 1 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|improve this answer
    
interesting, thanks. I found Boedlander's website but this seems easier to use –  Yaroslav Bulatov Nov 14 '10 at 20:38
add comment

Your Answer

 
discard

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.