A lower bound on the crossing number of graphs and its applications

By Géza Tóth
Courant Institute, NYU and Hungarian Academy of Sciences

Abstract. The crossing number cr(G) of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. Ajtai et al. and, independently, Leighton obtained a general lower bound for the crossing number of a graph in terms of its number of vertices and edges. This result found many applications in combinatorial geometry, graph layout problems, and in VLSI design.

We address the following question. What is the maximum number of edges that a simple graph of v vertices can have if it can be drawn in the plane so that every edge crosses at most k others? For k=0, i.e. for planar graphs, the well known answer is 3v-6. Our first theorem generalizes this result to .

Based on this result, we improve the bound of Ajtai et al. by a constant factor and show that our constant can not be further improved by more than a factor of 2. Using the ideas of Székely, we deduce some other consequences, for example we get a better constant in the Szemerédi-Trotter theorem about the maximum number of incidences among m points and n lines.

(Joint work with János Pach)