Improved approximation algorithms for box contact representations
From MaRDI portal
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 -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.
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
Cites work
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 1445306 (Why is no real title available?)
- A note on 1-planar graphs
- An efficient approximation for the generalized assignment problem
- Approximation techniques for utilitarian mechanism design
- Area-universal and constrained rectangular layouts
- Decomposition of Finite Graphs Into Forests
- Edge-weighted contact representations of planar graphs
- Efficient, proximity-preserving node overlap removal
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Graph Drawing
- Lower bounds on the cardinality of the maximum matchings of planar graphs
- Rectangle and Square Representations of Planar Graphs
- Rectangular layouts and contact graphs
- Semantic word cloud representations: hardness and approximation algorithms
- Star arboricity of graphs
- Tight approximation algorithms for maximum separable assignment problems
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)
