J. Geiger, S. Cornelsen, J. Haunert,P. Kindermann, T. Mchedlidze, M. Nöllenburg, Y. Okamoto, A. Wolff:

"ClusterSets: Optimizing Planar Clusters in Categorical Point Data";

Talk: EuroVis, Zürich, Schweiz; 2021-06-14 - 2021-06-18; in: "Proceedings of the EuroVIS 2021", 40/3 (2021), 471 - 481.

In geographic data analysis, one is often given point data of different categories (such as facilities of a university categorized

by department). Drawing upon recent research on set visualization, we want to visualize category membership by connecting

points of the same category with visual links. Existing approaches that follow this path usually insist on connecting all members

of a category, which may lead to many crossings and visual clutter. We propose an approach that avoids crossings between connections

of different categories completely. Instead of connecting all data points of the same category, we subdivide categories

into smaller, local clusters where needed. We do a case study comparing the legibility of drawings produced by our approach

and those by existing approaches.

In our problem formulation, we are additionally given a graph G on the data points whose edges express some sort of proximity.

Our aim is to find a subgraph G0 of G with the following properties: (i) edges connect only data points of the same

category, (ii) no two edges cross, and (iii) the number of connected components (clusters) is minimized. We then visualize the

clusters in G0. For arbitrary graphs, the resulting optimization problem, Cluster Minimization, is NP-hard (even to approximate).

Therefore, we introduce two heuristics. We do an extensive benchmark test on real-world data. Comparisons with exact

solutions indicate that our heuristics do astonishing well for certain relative-neighborhood graphs.

http://dx.doi.org/10.1111/cgf.14322

https://publik.tuwien.ac.at/files/publik_299987.pdf

Created from the Publication Database of the Vienna University of Technology.