The 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 K 2k+1,q , for k > 2. We prove tight bounds for complete graphs.
['Farhad Shahrokhi', 'Ondrej Sykora', 'László A. Székely', 'Imrich Vrto']
Bounds and methods for k-planar crossing numbers