Set Visualisation

Visualising sets and their elements is a recurring theme in information visualization. Recent approaches use very sparse enclosing shapes when depicting sets, such as LineSets, Kelp Diagrams, and KelpFusion. These methods attempt to reduce visual clutter by reducing the amount of “ink” necessary to connect all elements of a set. Although existing results are visually pleasing, they do not use the optimal amount of ink.

We explore the algorithmic questions that arise when computing spanning graphs for set visualization which are optimal with respect to ink usage. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected.

We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. We provide efficient algorithms to compute minimum RBP spanning graphs in a variety of settings.