We study the following geometric representation problem: Given a
graph whose vertices correspond to axis-aligned rectangles with
fixed dimensions, arrange the rectangles without overlaps in the
plane such that two rectangles touch if the graph
contains an edge between them. This problem is called
Contact Representation of Word Networks (Crown) since
it formalizes the geometric problem
behind drawing word clouds in which semantically related words are
close to each other. Crown is known to be
NP-hard, and there are approximation algorithms for certain graph
classes for the optimization version, Max-Crown, in which realizing
each desired adjacency yields a certain profit.
We present the first $O(1)$-approximation algorithm for the general
case, when the input is a complete weighted graph, and for the
bipartite case. Since the
subgraph of realized adjacencies is necessarily planar, we also consider
several planar graph classes (namely stars, trees, outerplanar, and
planar graphs), improving upon the known results.
For some graph classes, we also describe improvements
in the unweighted case, where each adjacency yields the same
profit. Finally, we show that the problem is APX-hard on
bipartite graphs of bounded maximum degree.
%0 Conference Paper
%1 bekos2014improved
%A Bekos, Michael A.
%A van Dijk, Thomas C.
%A Fink, Martin
%A Kindermann, Philipp
%A Kobourov, Stephen
%A Pupyrev, Sergey
%A Spoerhase, Joachim
%A Wolff, Alexander
%B Proceedings of the 22nd European Symposium on Algorithms (ESA '14)
%D 2014
%E Schulz, Andreas S.
%E Wagner, Dorothea
%I Springer-Verlag
%K algorithms approximation box contact myown
%P 87-99
%T Improved Approximation Algorithms for Box Contact Representations
%U http://dx.doi.org/10.1007/978-3-662-44777-2_8
%V 8737
%X We study the following geometric representation problem: Given a
graph whose vertices correspond to axis-aligned rectangles with
fixed dimensions, arrange the rectangles without overlaps in the
plane such that two rectangles touch if the graph
contains an edge between them. This problem is called
Contact Representation of Word Networks (Crown) since
it formalizes the geometric problem
behind drawing word clouds in which semantically related words are
close to each other. Crown is known to be
NP-hard, and there are approximation algorithms for certain graph
classes for the optimization version, Max-Crown, in which realizing
each desired adjacency yields a certain profit.
We present the first $O(1)$-approximation algorithm for the general
case, when the input is a complete weighted graph, and for the
bipartite case. Since the
subgraph of realized adjacencies is necessarily planar, we also consider
several planar graph classes (namely stars, trees, outerplanar, and
planar graphs), improving upon the known results.
For some graph classes, we also describe improvements
in the unweighted case, where each adjacency yields the same
profit. Finally, we show that the problem is APX-hard on
bipartite graphs of bounded maximum degree.
@inproceedings{bekos2014improved,
abstract = {We study the following geometric representation problem: Given a
graph whose vertices correspond to axis-aligned rectangles with
fixed dimensions, arrange the rectangles without overlaps in the
plane such that two rectangles touch if the graph
contains an edge between them. This problem is called
\textsc{Contact Representation of Word Networks} (\textsc{Crown}) since
it formalizes the geometric problem
behind drawing word clouds in which semantically related words are
close to each other. \textsc{Crown} is known to be
NP-hard, and there are approximation algorithms for certain graph
classes for the optimization version, \textsc{Max-Crown}, in which realizing
each desired adjacency yields a certain profit.
We present the first $O(1)$-approximation algorithm for the general
case, when the input is a complete weighted graph, and for the
bipartite case. Since the
subgraph of realized adjacencies is necessarily planar, we also consider
several planar graph classes (namely stars, trees, outerplanar, and
planar graphs), improving upon the known results.
For some graph classes, we also describe improvements
in the unweighted case, where each adjacency yields the same
profit. Finally, we show that the problem is APX-hard on
bipartite graphs of bounded maximum degree.},
added-at = {2014-07-23T01:15:33.000+0200},
author = {Bekos, Michael A. and van Dijk, Thomas C. and Fink, Martin and Kindermann, Philipp and Kobourov, Stephen and Pupyrev, Sergey and Spoerhase, Joachim and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/28c675d720aba9bb6590ecea6cb036311/fink},
booktitle = {Proceedings of the 22nd European Symposium on Algorithms (ESA '14)},
editor = {Schulz, Andreas S. and Wagner, Dorothea},
interhash = {bf1d9f52eaea38b3746294f2a8a5f573},
intrahash = {8c675d720aba9bb6590ecea6cb036311},
keywords = {algorithms approximation box contact myown},
pages = {87-99},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
timestamp = {2015-01-14T06:16:13.000+0100},
title = {Improved Approximation Algorithms for Box Contact Representations},
url = {http://dx.doi.org/10.1007/978-3-662-44777-2_8},
volume = 8737,
year = 2014
}