Abstract

The crossing number CR(G) of a graph G = (V, E) is the smallest number of edge crossings over all drawings of G in the plane. For any k >= 1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G(0)) + CR(G(1)) + ... + CR(G(k-i)) over all graphs G(0), G(1), ... , G(k-i) with boolean OR(k-1)(i=0) G(i) = G. It is shown that for every k >= 1, we have CRk(G) <= (2/k(2) - 1/k(3)) CR(G). This bound does not remain true if we replace the constant 2/k(2) - 1/k(3) by any number smaller than 1/k(2) Some of the results extend to the rectilinear variants of the k-planar crossing number. (C) 2017 Elsevier B.V. All rights reserved.

Details

Actions