Header

UZH-Logo

Maintenance Infos

Semantic word cloud representations: hardness and approximation algorithms


Barth, Lukas; Fabrikant, Sara I; Kobourov, Stephen; Lubiw, Anna; Nöllenburg, Martin; Okamoto, Yoshio; Pupyrev, Sergey; Squarcella, Claudio; Ueckerdt, Torsten; Wolff, Alexander (2013). Semantic word cloud representations: hardness and approximation algorithms. arXiv 1311.4778, University of Zurich.

Abstract

We study a geometric representation problem, where we are given a set R of axis-aligned rectangles with fixed dimensions and a graph with vertex set R. The task is to place the rectangles without overlap such that two rectangles touch if and only 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 restricted trees and weakly NP-hard if restricted stars. We 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%.

Abstract

We study a geometric representation problem, where we are given a set R of axis-aligned rectangles with fixed dimensions and a graph with vertex set R. The task is to place the rectangles without overlap such that two rectangles touch if and only 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 restricted trees and weakly NP-hard if restricted stars. We 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%.

Statistics

Citations

6 citations in Microsoft Academic

Downloads

246 downloads since deposited on 23 Jan 2014
35 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Working Paper
Communities & Collections:07 Faculty of Science > Institute of Geography
Dewey Decimal Classification:910 Geography & travel
Language:English
Date:November 2013
Deposited On:23 Jan 2014 10:35
Last Modified:16 Feb 2018 19:06
Series Name:arXiv
Number of Pages:14
OA Status:Green
Official URL:http://arxiv.org/abs/1311.4778
Related URLs:http://arxiv.org (Publisher)

Download

Download PDF  'Semantic word cloud representations: hardness and approximation algorithms'.
Preview
Filetype: PDF
Size: 1MB