About This Project
Treewidth is a well-established concept in graph theory that (
informally speaking) measures how "close" a graph is to being a tree.
A tree decomposition of a graph G is a tree T in which each node, also called a "bag", contains
a subset of G's vertices, such that
- every vertex of G appears in at least one bag,
- for every edge of G, both endpoints appear together in at least one bag, and
- for every vertex v of G, all bags containing v form a connected subtree of T.
The width of the decomposition is the size of its largest bag minus one, and the treewidth of G is
the
smallest possible width over all tree decompositions of G.
For more information, we refer to this
textbook.
We are interested in computing witness drawings to certify that a graph G has bounded
treewidth.
We study how to compute witness drawings with few crossings.
This website showcases the prototype application accomopanying the results presented at GD
2025.
Using This Application
To begin, load a visualization via the header bar.
You have the option to
- compute a witness drawing for a given decomposition,
- load a pre-computed visualization, and
- load one of the sample witness drawings from our paper.
We also provide small example files illustrating the file format, and refer to our paper for details
on the implemented algorithms.
There is also an option to clear the current drawing.
Once a drawing is loaded, you can find a drawing of the graph and its decomposition side by
side.
Hovering over a vertex or edge in the highlights the corresponding elements in the
drawing by enlarging them.
The same holds true if you click inside the disk of some bag.
You can reposition vertices in the drawing of the graph by dragging them.
In the header bar, you can find information on the loaded instance and the number of crossings
in the currently shown witness drawing.
Moreover, you can
- export the drawing as an SVG or PNG file and
- download its file representation.
More Information
Feel free to check out
our
paper at GD 2025 or
the
source code on OSF.
For further questions about this application, feel free to contact Thomas
Depian.
Acknowledgements
This work received funding from the Vienna Science and Technology Fund (WWTF); project nr.
10.47379/ICT22029 and NSF grant 2212129.
This prototype was built using