On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs

The crossing number cr(G) of a graph G is the minimum number of crossings in a nondegenerate planar drawing of G. The rectilinear crossing number cr(G) of G is the minimum number of crossings in a rectilinear nondegenerate planar drawing (with edges as straight line segments) of G. Zarankiewicz proved in 1952 that cr(Kn1;n2 ) Z(n1;n2) := n1 2 n1 1 2 n2 2 n2 1 2 . We dene an analogous bound for the complete tripartite graph Kn1;n2;n3 ,