Combinatorial Geometry

We give a survey of results on disjointness and intersection graphs of geometric objects. We start by proving Ramsey-type results for the intersection graphs of convex sets in the plane. We first show that every intersection graph of n convex sets in the plane has a clique or independent set of size n^{1/5} . After that we show that if G is the intersection graph of n convex sets in the plane, then G or Ḡ has a bi-clique of size cn for a universal constant c. We then show an upper bound for the number of edges in a geometric graph on n vertices with no k + 1 disjoint edges. Finally, we look at the colouring properties of disjointness graphs and prove that the family of disjointness graphs of segments in the plane is χ-bounded. We also show a generalization of this result to higher dimensions and discuss the χ-boundedness of related families of disjointness graphs.