
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))\).
Lower bound, Complete graph, Crossing number, Applied Mathematics, complete bipartite graph, k-planar Crossing number, rectilinear \(k\)-planar crossing number, Rectilinear k-planar crossing number, Planar graphs; geometric and topological aspects of graph theory, Complete bipartite graph, Discrete Mathematics and Combinatorics, crossing number, \(k\)-planar crossing number, lower bound, complete graph
Lower bound, Complete graph, Crossing number, Applied Mathematics, complete bipartite graph, k-planar Crossing number, rectilinear \(k\)-planar crossing number, Rectilinear k-planar crossing number, Planar graphs; geometric and topological aspects of graph theory, Complete bipartite graph, Discrete Mathematics and Combinatorics, crossing number, \(k\)-planar crossing number, lower bound, complete graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
