Using block designs in crossing number bounds. Issue 10 (16th July 2019)

• Record Type: Journal Article
• Authors: Asplund, John; Clark, Gregory; Cochran, Garner; Czabarka, Éva; Hamm, Arran; Spencer, Gwen; Székely, László; Taylor, Libby; Wang, Zhiyu
• Is Part Of: Journal of combinatorial designs. Volume 27:Issue 10(2019:Oct.)
• Page Start: 586
• Page End: 597
• Publication Date: 2019-07-16
• Subjects: Kirkman triple system -- k‐planar crossing number -- resolvable balanced incomplete block design -- resolvable group divisible design; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21665
• Languages: English
• ISSNs: 1063-8539

Abstract

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, CR k ( G ), is defined as the minimum of CR ( G 1 ) + CR ( G 2 ) + ⋯ + CR ( G k ) over all graphs G 1, G 2, …, G k with ∪ i = 1 k G i = G . Pach et al [Comput. Geom.: Theory Appl. 68 (2018), pp. 2–6] showed that for every k ≥ 1, we have CR k ( G ) ≤ ( 2 / k 2 − 1 / k 3 ) CR ( G ) and that 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 . We improve the upper bound to ( 1 / k 2 ) ( 1 + o ( 1 ) ) as k → ∞ . For the class of bipartite graphs, we show that the best constant is exactly 1 / k 2 for every k . The results extend to the rectilinear variant of the k ‐planar crossing number.