Coloring and Maximum Weight Independent Set of Rectangles

Parinya Chalermsook, Bartosz Walczak

In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O({\omega }^2)$-coloring, where $\omega$ is the maximum size of a clique.…