On \(k\)-planar crossing numbers (Q885282)

The \(k\)-planar crossing number of a graph \(G\), denoted by \(\text{cr}_k(G)\), is the minimum number of crossings of its edges over all possible drawings of the \(G\) in \(k\) planes. This parameter is related to the thickness parameter: \(\text{cr}_k(G)= 0\) if and only if \(G\) has thickness at most \(k\). Much of the present paper extends ideas of \textit{E. Czabarka, O. Sýkora, L. A. Székely}, and \textit{I. Vrt'o} [Györi, Katona, and Lováz (eds.), More sets, graphs and numbers, Bolyai Society of Mathematical Studies 15, 57--77 (2006; Zbl 1098.05023)], for the case \(k= 2\). The present authors propose algorithms and methods for \(k\)-planar drawings of general graphs, as well as lower bound techniques; they give exact results for \(\text{cr}_k(K_{2k+1,q})\), for \(k\geq 2\); they prove tight bounds for complete graphs; and they study the rectilinear crossing number. There appear to be some typographical difficulties; for example, Figure 1 shows that \(\text{cr}_3(K_{7,30})= 0\), whereas Theorem 3 as written gives the value as 30 (perhaps the final ``\(-1\)'' should be ``\(+1\)'') and on page 1107 the same formula is differently (and ambiguously) written (what role does the ``\(<\)'' play? The sign \textit{has} been changed for \(k(2k+1))\).