SOME GEOMETRIC APPLICATIONS OF DILWORTH THEOREM

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no three vertices are collinear. We settle an old question of Avital, Hanani, Erdos, 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 Y and a set of axis-parallel rectangles in the plane, then either there are k + 1 rectangles such that no point of Y belongs to more than one of them, or we can find an at most 2 . 10(5)k8 element subset of Y meeting all rectangles. This improves a result of Ding, Seymour, and Winkler. Both proofs are based on Dilworth's theorem on partially ordered sets.