For positive integers and , let be the minimum crossing number (the standard planar crossing number) taken over all graphs with vertices and at least edges. Pach, Spencer and T'oth [Discrete and Computational Geometry 24 623–644, (2000)] showed that tends to a positive constant (called midrange crossing constant) as $n\to \inftyn \ll e \ll n^2$, proving a conjecture of Erd\H{o}s and Guy. In this note, we extend their proof to show that the midrange crossing constant exists for graph classes that satisfy a certain set of graph properties. As a corollary, we show that the the midrange crossing constant exists for the family of bipartite graphs. All these results have their analogues for rectilinear crossing numbers.

生成讲解博客的中文版本

生成AI智能校验的中文版本