A benchmark for algorithms for Treewidth and
related graph problems
The notion of treewidth has played an important role in
research in algorithmic graph theory in the past years. More
recently, research has been done where the notion is also used
in practical and experimental settings to solve graph problems.
In many of these settings, algorithms are needed that generate
tree decompositions with sufficiently small width, and that are
sufficiently fast. In order to compare implementations of such
algorithms, it would be helpful to have a large enough set of
graphs for which computing their treewidth is relevant.
TreewidthLIB is aimed at providing such a set of graphs: i.e.,
a collection of graphs that can be used as benchmark for the
comparison of algorithms computing treewidth, tree
decompositions, but also for algorithms that solve problems
related to treewidth, like branchwidth or minimum fill-in.
These webpages will gradually grow. At the start, we have a few
graphs, and a few links to relevant webpages. For more information
on what we indend to add and have recently added,
see our todo list and version history.
Call for Graphs
If you have access to graphs that would fit in well in this
collection, then please email these to
- We look for graphs for which it is relevant to
compute the treewidth, e.g., because they are used in an
application. We will also feature a few `famous' or well
- Graphs may have different sizes.
- We must have permission to put the file on the website.
(Check copyright issues.)
- We prefer the graph to be in a standard format; if
necessary, we can try to convert the graph to that format.
We prefer the
Search the database
Unfortunately, the database currently does not work. We hope it will
be repaired soon. (November 2011.)
Some relevant links.
Some graph related tools.
Author and thanks
This website was created by
Jan-Willem van den Broek and
Hans Bodlaender. Thanks due to Arie Koster and several
other collegues for
suggestions, cooperation, graphs, and links.