APPLICATIONS OF THE CROSSING NUMBER

Let G be a graph of n vertices that can be drawn in the plane by strai ght-line segments so that no k + 1 of them are pairwise crossing. We s how that G has at most c(k) n log(2k-2) n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erd os, Kupitz, Perles, and others. We also construct two point sets {p(1) ,..., p(n)}, {q(1),..., q(n)} in the plane such that any piecewise lin ear one-to-one mapping f:R(2) --> R(2) with f(p(i)) = q(i) (1 less tha n or equal to i less than or equal to n) is composed of at least Omega (n(2)) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.