On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs

A rectilinear drawing of a graph is a drawing of the graph in the plane in which the edges are drawn as straight-line segments. The rectilinear crossing number of a graph is the minimum number of pairs of edges that cross over all rectilinear drawings of the graph. Let n ≥ r be positive integers. The graph Kₙʳ, is the complete r-partite graph on n vertices, in which every set of the partition has at least n/r vertices. The layered graph, Lₙʳ, is an r-partite graph on n vertices, in which for every 1≤ i ≤ r-1, all the vertices in the i-th partition are adjacent to all the vertices in the $(i+1)$-th partition. In this paper, we give upper bounds on the rectilinear crossing numbers of Kₙʳ and~Lₙʳ.