Premium
Using block designs in crossing number bounds
Author(s) -
Asplund John,
Clark Gregory,
Cochran Garner,
Czabarka Éva,
Hamm Arran,
Spencer Gwen,
Székely László,
Taylor Libby,
Wang Zhiyu
Publication year - 2019
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21665
Subject(s) - mathematics , crossing number (knot theory) , combinatorics , bipartite graph , upper and lower bounds , constant (computer programming) , planar graph , planar , discrete mathematics , plane (geometry) , block (permutation group theory) , graph , geometry , computer science , mathematical analysis , computer graphics (images) , intersection (aeronautics) , engineering , programming language , aerospace engineering
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 haveCR 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 3by 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 2for every k . The results extend to the rectilinear variant of the k ‐planar crossing number.