Midrange crossing constants for graphs classes
read the original abstract
For positive integers $n$ and $e$, let $\kappa(n,e)$ be the minimum crossing number (the standard planar crossing number) taken over all graphs with $n$ vertices and at least $e$ edges. Pach, Spencer and T\'oth [Discrete and Computational Geometry 24 623--644, (2000)] showed that $\kappa(n,e) n^2/e^3$ tends to a positive constant (called midrange crossing constant) as $n\to \infty$ and $n \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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Some remarks on the midrange crossing constant
Alternative verification confirms the 8/(9π²) upper bound on the midrange crossing constant via Moon's result and asks whether equality holds.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.