Using block designs in crossing number bounds

Abstract: The crossing number

m b o x 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

,

{m b o x c r}_{k} (G)

, is defined as the minimum of

m b o x c r (G_{1}) + m b o x c r (G_{2}) + l d o t s + m b o x c r (G_{k})

over all graphs

G_{1}, G_{2}, l d o t s, G_{k}

with

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

. Pach et al. [emph{Computational Geometry: Theory and Applications} {�f 68} 2--6, (2018)] showed that for every

k g e 1

, we have

{m b o x 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) m b o x c r (G)

and that 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}

. We improve the upper bound to

f r a c 1 k^{2} (1 + o (1))

as

k i g h t a r r o w i n f t y

. For the class of bipartite graphs, we show that the best constant is exactly

f r a c 1 k^{2}

for every

k

. The results extend to the rectilinear variant of the

k

-planar crossing number.

Recommendations

Cited In (4)

This page was built for publication: Using block designs in crossing number bounds