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-complete on bipartite
graphs of bounded maximum degree.
%0 Journal Article
%1 bdfkkpsw-iaabc-Algorithmica17
%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
%D 2017
%J Algorithmica
%K Approximation_algorithms Box_contact_representations Word_clouds myown
%N 3
%P 902--920
%R 10.1007/s00453-016-0121-3
%T Improved Approximation Algorithms for Box Contact
Representations
%V 77
%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-complete on bipartite
graphs of bounded maximum degree.
@article{bdfkkpsw-iaabc-Algorithmica17,
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 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-complete on bipartite
graphs of bounded maximum degree.},
added-at = {2024-07-14T10:03:47.000+0200},
arxiv = {http://arxiv.org/abs/1311.4778},
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/25e4a874d4ae3cf49bbe89ef3825098b3/awolff},
doi = {10.1007/s00453-016-0121-3},
interhash = {b208b27cc3c2a604bcec5950012e5930},
intrahash = {5e4a874d4ae3cf49bbe89ef3825098b3},
journal = {Algorithmica},
keywords = {Approximation_algorithms Box_contact_representations Word_clouds myown},
number = 3,
pages = {902--920},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/bdfkkpsw-iaabc-Algorithmica16.pdf},
slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/bdfkkpsw-iaabc-ESA14-slides.pdf},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Improved Approximation Algorithms for Box Contact
Representations},
volume = 77,
year = 2017
}