Crossing numbers: connections and some open problems
Laszlo A. Szekely
University of South Carolina
I'll discuss connections of crossing numbers to other extremal problems
and some issues that come up even in different models for crossing
numbers but still not sufficiently understood.
Some of the connections: Ringel observed an inequality between crossing numbers
of complete graphs and some Turan numbers; a lower bound for the crossing number
of graphs with large girth from Pach, Spencer and Toth immediately sets an upper
bound for the number of edges of such graphs; the crossing number method gives a
tool to handle many incidence problems. The crossing number method did not give
any improvement on the upper bound for the number of unit distances problem ---
what do we need to know about unit distances for an improvement?
Some of the not sufficiently understood phenomena:
Sum of degree squares come up as error term in lower bounds (a) for crossing numbers
in the bisection width method (Pach-Shahrokhi-Szegedy, Sykora-Vrto)
(b) for crossing numbers in the embedding method (Shahrokhi-Sykora-Szekely-Vrto)
(c) for convex crossing numbers (Czabarka-Sykora-Szekely-Vrto). Why?
Linear arrangement is related to the biplanar crossing number in a certain range
(Shahrokhi-Sykora-Szekely-Vrto), circular arrangement seems to be related
to the convex crossing number (Czabarka-Sykora-Szekely-Vrto). Is there anything
to discover here?