Note on k-planar crossing numbers

Publication date 19 February 2018

Abstract: The crossing number

c r (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 g e 1

, the

k

-planar crossing number of

G

,

c r_{k} (G)

, is defined as the minimum of

c r (G_{0}) + c r (G_{1}) + l d o t s + c r (G_{k - 1})

over all graphs

G_{0}, G_{1}, l d o t s, G_{k - 1}

with

c u p_{i = 0}^{k - 1} G_{i} = G

. It is shown that for every

k g e 1

, we have

c r_{k} (G) l e l e f t (f r a c 2 k^{2} - f r a c 1 k^{3} i g h t) c r (G)

. This bound does not remain true if we replace the constant

f r a c 2 k^{2} - f r a c 1 k^{3}

by any number smaller than

f r a c 1 k^{2}

. Some of the results extend to the rectilinear variants of the

k

-planar crossing number.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Note on \(k\)-planar crossing numbers