pith. sign in

Midrange crossing constants for graphs classes

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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.

fields

math.CO 1

years

2019 1

verdicts

UNVERDICTED 1

representative citing papers

Some remarks on the midrange crossing constant

math.CO · 2019-06-30 · unverdicted · novelty 3.0

Alternative verification confirms the 8/(9π²) upper bound on the midrange crossing constant via Moon's result and asks whether equality holds.

citing papers explorer

Showing 1 of 1 citing paper.

  • Some remarks on the midrange crossing constant math.CO · 2019-06-30 · unverdicted · none · ref 6 · internal anchor

    Alternative verification confirms the 8/(9π²) upper bound on the midrange crossing constant via Moon's result and asks whether equality holds.