Twenty years ago, Ajtai, Chvatal, Newborn, Szemeredi, and, independently, Leighton discovered that the crossing number of any graph with v vertices and e>4v edgesis at least ce3/v2, where c>0 is an absolute constant. This result, known as the 'Crossing Lemma,' has found many important applications in discrete and computational geometry. It is tightup to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c>1024/31827>0.032. The proof has two new ingredients, interesting on their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most 3 others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least 73e - 253(v-2). Both bounds are tight up to anadditive constant (the latter one in the range 4v ≤ e ≤ 5v).

Let P be a set of n points in general position in the plane. Let Xk(P) denote the number of empty convex κ-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities involving the quantities Xk(P) and several related quantities. Most of these equalities and inequalities are new, except for a couple that have been proved earlier using a considerablymore complex machinery from matroid and polytope theory,algebraic topology and commutative algebra. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.

Let G be a topological graph on n vertices in the plane, i.e., a graph drawn in the plane with its vertices represented as points and its edges represented as Jordan arcs connecting pairs of points. It is shown that if no two edges of any cycle of length 4 in G cross an odd number of times, then |E(G)|=O(n8/5).

We show that for any $n$ there is an arrangement of $n$ lines which co ntain an $x$-monotone path of length $\Omega(n^{7/4})$.