Titel:  Improved Approximation Algorithms for Box Contact Representations 


AutorInnen: 
Michael A. Bekos
Thomas C. van Dijk Martin Fink Philipp Kindermann Stephen G. Kobourov Sergey Pupyrev Joachim Spoerhase Alexander Wolff 

Kategorie:  Konferenzbandbeiträge  
erschienen in:  Proceedings of the 22nd Annual European Symposium on Algorithms (ESA'14), pp. 8799  
Abstract: 


Download:  Proceeding Website 

BibTeXEintrag:  @InProceedings{bdfkkpswiaabcr14, Title = {Improved Approximation Algorithms for Box Contact Representations}, Author = {Michael A. Bekos and Thomas C. van Dijk and Martin Fink and Philipp Kindermann and Stephen G. Kobourov and Sergey Pupyrev and Joachim Spoerhase and Alexander Wolff}, Booktitle = {Proceedings of the 22th Annual European Symposium on Algorithms (ESA'14)}, Year = {2014}, Editor = {Andreas S. Schulz and Dorothea Wagner}, Pages = {8799}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {8737}, Abstract = {We study the following geometric representation problem: Given a graph whose vertices correspond to axisaligned 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 NPhard, and there are approximation algorithms for certain graph classes for the optimization version, \textsc{MaxCrown}, 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 APXhard on bipartite graphs of bounded maximum degree.}, Doi = {10.1007/9783662447772_8} } 