Applications of the crossing number
János Pach, Farhad Shahrokhi, Márió Szegedy · 1994
We show that any graph of n vertices that can be drawn in the plane with no k+1 pairwise crossing edges has at most cknlog2k−2n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdős, Kupitz, Perles, and others. We also construct two point sets {p1,…,pn}, {q1,…,qn} in the plane such that any piecewise linear one-to-one mapping f:R2→R2 with f(pi)=qi (1≤i≤n) is composed of at least Ω(n2) 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.