GRAPHS DRAWN WITH FEW CROSSINGS PER EDGE

We show that if a graph of v vertices can be drawn in the plane so tha t every edge crosses at most k > 0 others, then its number of edges ca nnot exceed 4.108 root kv. For k less than or equal to 4, we establish a better bound, (k + 3)(v - 2), which is tight for k = 1 and 2. We ap ply these estimates to improve a result of Ajtai et al. and Leighton, providing a general lower bound for the crossing number of a graph in terms of its number of vertices and edges.