TY - GEN
T1 - Improved approximation algorithms for box contact representations
AU - Bekos, Michael A.
AU - Van Dijk, Thomas C.
AU - Fink, Martin
AU - Kindermann, Philipp
AU - Kobourov, Stephen
AU - Pupyrev, Sergey
AU - Spoerhase, Joachim
AU - Wolff, Alexander
N1 - Funding Information:
The work of M. A. Bekos is implemented within the framework of the Action “Supporting Postdoctoral Researchers” of the Operational Program “Education and Lifelong Learning” (Action’s Beneficiary: General Secretariat for Research and Technology), and is co-financed by the European Social Fund (ESF) and the Greek State. Ph. Kindermann and A. Wolff acknowledge support by the ESF EuroGIGA project GraDR. S. Kobourov and S. Pupyrev are supported by NSF grants CCF-1115971 and DEB 1053573.
PY - 2014
Y1 - 2014
N2 - 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 show that the problem is APX-complete on bipartite graphs of bounded maximum degree. 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 consider several planar graph classes (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.
AB - 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 show that the problem is APX-complete on bipartite graphs of bounded maximum degree. 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 consider several planar graph classes (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.
UR - http://www.scopus.com/inward/record.url?scp=84958522604&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958522604&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-44777-2_8
DO - 10.1007/978-3-662-44777-2_8
M3 - Conference contribution
AN - SCOPUS:84958522604
SN - 9783662447765
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 87
EP - 99
BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PB - Springer-Verlag
T2 - 22nd Annual European Symposium on Algorithms, ESA 2014
Y2 - 8 September 2014 through 10 September 2014
ER -