See by year See by month Jump to month

Éva Czabarka (University of South Carolina): Midrange crossing constants for graphs classes

Download as iCal file
Monday, 13. May 2019, 16:00 - 17:00

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óth [Discrete and Computational Geometry{\bf 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 << e << n^2$, proving a conjecture of Erdő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 is joint work with Josiah Reiswig, Lászlo Székely and Zhiyu Wang.
Location : Bolyai Intézet, I. emelet, Riesz terem, Aradi vértanúk tere 1., Szeged


JEvents v3.1.8 Stable   Copyright © 2006-2013