pith. sign in

arxiv: 1811.08071 · v1 · pith:WMIODF3Inew · submitted 2018-11-20 · 🧮 math.CO

Midrange crossing constants for graphs classes

classification 🧮 math.CO
keywords crossingconstantmidrangegraphsclassesexistsgraphkappa
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Some remarks on the midrange crossing constant

    math.CO 2019-06 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.