Label placement by maximum independent set in rectangles
From MaRDI portal
Publication:1276946
DOI10.1016/S0925-7721(98)00028-5zbMath0921.68100WikidataQ29037138 ScholiaQ29037138MaRDI QIDQ1276946
Subhash Suri, Marc J. van Kreveld, Pankaj K. Agarwal
Publication date: 11 April 1999
Published in: Computational Geometry (Search for Journal in Brave)
Related Items (67)
A Lagrangean decomposition for the maximum independent set problem applied to map labeling ⋮ Improved algorithms for resource allocation under varying capacity ⋮ Minimum Point-Overlap Labeling ⋮ Balanced independent and dominating sets on colored interval graphs ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ On the Approximability of Orthogonal Order Preserving Layout Adjustment ⋮ Approximation algorithms on consistent dynamic map labeling ⋮ A randomized algorithm for online unit clustering ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Collision-free routing problem with restricted L-path ⋮ Faster approximation for maximum independent set on unit disk graph ⋮ Efficient independent set approximation in unit disk graphs ⋮ Mixed Map Labeling ⋮ Optimization problems in dotted interval graphs ⋮ Geometric Packing under Nonuniform Constraints ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ Cubicity and bandwidth ⋮ Keep your distance: land division with separation ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Polynomial time algorithms for three-label point labeling. ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ Unnamed Item ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ On streaming algorithms for geometric independent set and clique ⋮ Recognizing geometric intersection graphs stabbed by a line ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Trimming of graphs, with application to point labeling ⋮ Many disjoint edges in topological graphs ⋮ Hardness of approximation for non-overlapping local alignments. ⋮ Computationally-feasible truthful auctions for convex bundles ⋮ Approximation algorithms for maximum independent set of a unit disk graph ⋮ Coloring intersection graphs of \(x\)-monotone curves in the plane ⋮ Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking ⋮ Admission control with advance reservations in simple networks ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Matching colored points with rectangles ⋮ Many disjoint edges in topological graphs ⋮ Packing and covering with non-piercing regions ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ An algorithmic framework for labeling network maps ⋮ Anchored rectangle and square packings ⋮ On grids in topological graphs ⋮ Optimizing active ranges for consistent dynamic map labeling ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Unnamed Item ⋮ Minimum vertex cover in rectangle graphs ⋮ A new fast heuristic for labeling points ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ Disjoint edges in complete topological graphs ⋮ In-place algorithms for computing a largest clique in geometric intersection graphs ⋮ Coloring and Maximum Independent Set of Rectangles ⋮ An upper bound for cubicity in terms of boxicity ⋮ On Map Labeling with Leaders ⋮ A note on maximum independent sets in rectangle intersection graphs ⋮ Optimal algorithm for a special point-labeling problem ⋮ DETERMINING A SET OF MAXIMUM INSCRIBED RECTANGLES FOR LABEL PLACEMENT IN A REGION ⋮ Limit theory of combinatorial optimization for random geometric graphs ⋮ On the Cubicity of AT-Free Graphs and Circular-Arc Graphs ⋮ On the stab number of rectangle intersection graphs ⋮ Minimum point-overlap labelling* ⋮ Fast stabbing of boxes in high dimensions ⋮ Unnamed Item ⋮ Evaluation of Labeling Strategies for Rotating Maps
Cites Work
- Optimal packing and covering in the plane are NP-complete
- Improved non-approximability results
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Approximation schemes for covering and packing problems in image processing and VLSI
- Simple heuristics for unit disk graphs
- An efficient and effective approximation algorithm for the Map Labeling Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Label placement by maximum independent set in rectangles
