Coloring and Maximum Weight Independent Set of Rectangles

2020/07/15 by Chalermsook, Parinya, Walczak, Bartosz · 2 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2007.07880

Abstract

In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an O(ω²)-coloring, where ω is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is O(ωlogω)-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time O(loglog n)-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of O((log n)/(loglog n)).

Cited by

• String Graphs: Product Structure and Localised Representations
• Counterexamples to Wegner's Conjecture for Rectangles

Related

• Approximating Maximum Independent Set for Rectangles in the Plane
• On Approximating Maximum Independent Set of Rectangles
• Approximation Schemes for Maximum Weight Independent Set of Rectangles
• Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line : Algorithms and Complexity
• Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments