2021/08/24 by Martin Nöllenburg, Nöllenburg, Martin, Anaïs Villedieu +3
Computer Science · #Computational Geometry (cs.CG) #Data Management and Algorithms #Data Visualization and Analytics #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2108.10711
openalex publication_date 2021/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate two optimization problems on area-proportional rectangle contact representations for layered, embedded planar graphs. The vertices are represented as interior-disjoint unit-height rectangles of prescribed widths, grouped in one row per layer, and each edge is ideally realized as a rectangle contact of positive length. Such rectangle contact representations find applications in semantic word or tag cloud visualizations, where a collection of words is displayed such that pairs of semantically related words are close to each other. In this paper, we want to maximize the number of realized rectangle contacts or minimize the overall area of the rectangle contact representation, while avoiding any false adjacencies. We present a network flow model for area minimization, a linear-time algorithm for contact maximization of two-layer graphs, and an ILP model for maximizing contacts of k-layer graphs.