Improved approximation algorithms for box contact representations

DOI10.1007/S00453-016-0121-3zbMATH Open1364.68366arXiv1403.4861OpenAlexW94833765MaRDI QIDQ521820FDOQ521820

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

Publication date: 12 April 2017

Published in: Algorithmica (Search for Journal in Brave)

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 extsc{Contact Representation of Word Networks} ( extsc{Crown}) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. extsc{Crown} is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, extsc{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.

Full work available at URL: https://arxiv.org/abs/1403.4861

Recommendations

• Improved approximation algorithms for box contact representations
• Scalable algorithms for contact problems
• Scalable Algorithms for Contact Problems
• Sublinear approximation algorithms for boxicity and related problems
• Polynomial time and parameterized approximation algorithms for boxicity
• A contact searching algorithm for general contact problems
• Parameterized algorithms for boxicity
• Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
• scientific article; zbMATH DE number 1263202
• Linear-time algorithms for hole-free rectilinear proportional contact graph representations

zbMATH Keywords

approximation algorithmsbox contact representationsword clouds

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Tight approximation algorithms for maximum separable assignment problems
• An efficient approximation for the generalized assignment problem
• Title not available (Why is that?)
• Decomposition of Finite Graphs Into Forests
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Rectangle and Square Representations of Planar Graphs
• Area-universal and constrained rectangular layouts
• Approximation techniques for utilitarian mechanism design
• Rectangular layouts and contact graphs
• A note on 1-planar graphs
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• Title not available (Why is that?)
• Star arboricity of graphs
• Edge-weighted contact representations of planar graphs
• Efficient, proximity-preserving node overlap removal
• Semantic word cloud representations: hardness and approximation algorithms
• Graph Drawing

Cited In (5)

• On layered area-proportional rectangle contact representations
• Semantic word cloud representations: hardness and approximation algorithms
• Layered area-proportional rectangle contact representations
• On layered area-proportional rectangle contact representations
• Improved approximation algorithms for box contact representations

This page was built for publication: Improved approximation algorithms for box contact representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521820)