2014 | OriginalPaper | Buchkapitel
Semantic Word Cloud Representations: Hardness and Approximation Algorithms
verfasst von : Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt, Alexander Wolff
Erschienen in: LATIN 2014: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study a geometric representation problem, where we are given a set
$\mathcal B$
of axis-aligned rectangles (boxes) with fixed dimensions and a graph with vertex set
$\mathcal B$
. The task is to place the rectangles without overlap such that two rectangles touch if the graph contains an edge between them. We call this problem
Contact Representation of Word Networks (Crown)
. It formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Here, we represent words by rectangles and semantic relationships by edges.
We show that
Crown
is strongly NP-hard even if restricted to trees and weakly NP-hard if restricted to stars. We also consider the optimization problem
Max-Crown
where each adjacency induces a certain profit and the task is to maximize the sum of the profits. For this problem, we present constant-factor approximations for several graph classes, namely stars, trees, planar graphs, and graphs of bounded degree. Finally, we evaluate the algorithms experimentally and show that our best method improves upon the best existing heuristic by 45%.