TreewidthLIB

A benchmark for algorithms for Treewidth and related graph problems

Introduction

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.

Building TreewidthLIB

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 Hans Bodlaender.

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 known graphs.
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 DIMACS format.

Search the database

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.