Semantic word cloud representations: hardness and approximation algorithms

DOI10.1007/978-3-642-54423-1_45zbMATH Open1405.68236arXiv1311.4778OpenAlexW2153113544WikidataQ124084530 ScholiaQ124084530MaRDI QIDQ5405069FDOQ5405069

Authors: Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt, Alexander Wolff 

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1311.4778

Recommendations

• Improved approximation algorithms for box contact representations
• Improved approximation algorithms for box contact representations
• COWORDS: a probabilistic model for multiple word clouds
• Placing Text Boxes on Graphs
• Rectangular layouts and contact graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (6)

• On layered area-proportional rectangle contact representations
• Layered area-proportional rectangle contact representations
• COWORDS: a probabilistic model for multiple word clouds
• On layered area-proportional rectangle contact representations
• Improved approximation algorithms for box contact representations
• Improved approximation algorithms for box contact representations

This page was built for publication: Semantic word cloud representations: hardness and approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405069)