Minimum Vertex Cover in Rectangle Graphs

Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz

We consider the Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle fa…