Visualizing Treewidth

Abstract

A witness drawing of a graph is a visualization that clearly shows a given property of a graph.
We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth.
Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with ``tracks'' for each vertex of the graph connecting its copies in multiple bags.
Within bags, we optimize the vertex layout to avoid crossings of edges and tracks.
We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width.
We explore the design space for width-witness drawings and investigate drawing styles that render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Finally, we report results from an expert evaluation assessing different witness drawing styles.