Some geometric applications of Dilworth's theorem
János Pach, Jenõ Törõcsik · 1993
A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no 3 vertices are collinear. We settle an old question of Avital, Hanani, Erdös, Kupitz and Perles by showing that every geometric graph with n vertices and m > k4n edges contains k+1 pairwise disjoint edges. We also prove that, given a set of points V and a set of axis-parallel rectangles in the plane, then either there are k+1 rectangles such that no point of V belongs to more than one of them, or we can find an at most 2˙105k8 element subset of V meeting all rectangles. This improves a result of Ding, Seymour and Winkler. Both proofs are based on Dilworth's theorem on partially ordered sets.