Header

UZH-Logo

Maintenance Infos

Semantic word cloud representations: hardness and approximation algorithms


Barth, Lukas; Fabrikant, Sara I; Kobourov, Stephen G; Lubiw, Anna; Nöllenburg, Martin; Okamoto, Yoshio; Pupyrev, Sergey; Squarcella, Claudio; Ueckerdt, Torsten; Wolff, Alexander (2014). Semantic word cloud representations: hardness and approximation algorithms. In: LATIN 2014 Latin American Theoretical INformatics Symposium, Montevideo, Urugay, 31 March 2014 - 4 April 2014, 514-525.

Abstract

We study a geometric representation problem, where we are given a set B of axis-aligned rectangles (boxes) with fixed dimensions and a graph with vertex set 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%.

Abstract

We study a geometric representation problem, where we are given a set B of axis-aligned rectangles (boxes) with fixed dimensions and a graph with vertex set 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%.

Statistics

Citations

5 citations in Web of Science®
5 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

2 downloads since deposited on 18 Feb 2015
0 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), not refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Geography
Dewey Decimal Classification:910 Geography & travel
Language:English
Event End Date:4 April 2014
Deposited On:18 Feb 2015 15:58
Last Modified:16 Aug 2017 01:46
Publisher:Springer
ISBN:978-3-642-54423-1
Official URL:http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-54422-4

Download

Preview Icon on Download
Content: Published Version
Language: English
Filetype: PDF - Registered users only
Size: 296kB

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations