D.: Minimum Vertex Cover in Rectangle Graphs

We consider the Minimum 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 families, rectangle families R where R1 \ R2 is connected for every pair of rectangles R1, R2 ∈ R. This algorithm extends to intersection graphs of pseudo-disks. The second algo-rithm achieves a factor of (1.5 + ε) in general rectangle families, for any fixed ε> 0, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles