On k-planar crossing numbers

AbstractThe k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K2k+1,q, for k⩾2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number