Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102297
Title: Improved approximation algorithms for box contact representations
Authors: Bekos, M. A.
Van, Dijk, T. C.
Fink, M.
Kindermann, P.
Kobourov, S.
Pupyrev, S.
Spoerhase, J.
Wolff, A.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Improved approximation algorithms for box contact representations / M. A. Bekos, T. C. Van Dijk, M. Fink, et al. — DOI 10.1007/978-3-662-44777-2_8 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8737 LNCS. — P. 87-99.
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 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. © 2014 Springer-Verlag Berlin Heidelberg.
Keywords: APPROXIMATION ALGORITHMS
GEOMETRY
GRAPHIC METHODS
PROFITABILITY
APX-COMPLETE
BIPARTITE GRAPHS
GEOMETRIC PROBLEMS
GEOMETRIC REPRESENTATION
MAXIMUM DEGREE
SEMANTICALLY-RELATED WORDS
WEIGHTED GRAPH
WORD NETWORKS
GRAPH THEORY
URI: http://hdl.handle.net/10995/102297
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84958522604
PURE ID: 1596577
7b85c76d-3523-4777-870c-713742c8de09
ISSN: 3029743
ISBN: 9783662447765
DOI: 10.1007/978-3-662-44777-2_8
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84958522604.pdf810,52 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.