Midrange crossing constants for graphs classes

MaRDI QIDQ6309972zbMATH OpenFDO

Authors Éva Czabarka, Josiah Reiswig, László A. Székely, Zhiyu Wang

Publication date 19 November 2018

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 $noinfty$ and $nllell{n}^2$, proving a conjecture of ErdH{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 page was built for publication: Midrange crossing constants for graphs classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309972)