2013/04/23 by Lukas Barth, Stephen Kobourov, Barth, Lukas +5 · 1 citation
Computer Science · #Computation and Language (cs.CL) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Natural Language Processing Techniques #Web Data Mining and Analysis #cs.CL #cs.DS
paper · pdf · doi:10.48550/arxiv.1304.8016
arxiv created 2013/04/23 · openalex publication_date 2013/04/23 · arxiv updated 2013/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of computing semantic-preserving word clouds in which semantically related words are close to each other. While several heuristic approaches have been described in the literature, we formalize the underlying geometric algorithm problem: Word Rectangle Adjacency Contact (WRAC). In this model each word is associated with rectangle with fixed dimensions, and the goal is to represent semantically related words by ensuring that the two corresponding rectangles touch. We design and analyze efficient polynomial-time algorithms for some variants of the WRAC problem, show that several general variants are NP-hard, and describe a number of approximation algorithms. Finally, we experimentally demonstrate that our theoretically-sound algorithms outperform the early heuristics.