Exact crossing numbers
April 28 to May 2, 2014
American Institute of Mathematics,
Palo Alto, California
and Gelasio Salazar
This workshop will be devoted
to tackling several long-standing open problems in the field of crossing
numbers. The crossing
number of a graph is the minimum number of crossings in a drawing of the graph
in the plane.
This field can be traced back to a question raised by Paul Turán in 1944, which
terminology asks for the crossing number of the complete bipartite graph. Since
of Turán's question (which remains open to this day), many fundamental crossing
questions have been tackled, both for their theoretical interest and for their
other branches of mathematics. Another tantalizingly open question asks for the
crossing number of
the complete graph. As Richter and Thomassen showed, this is closely related to
original question. Several variants of these two questions (including their
rectilinear versions, in
which edges are required to be drawn as straight line segments) are of great
interest of their own.
In particular, the rectilinear crossing number of the complete graph is of
fundamental importance, since settling this problem would solve the Four Point
Problem posed by J.J. Sylvester
The main topics for the workshop are:
- Zarankiewicz's Crossing Number Conjecture (Turán's Brickyard Problem), including
its weaker variants: rectilinear crossing number and 2-page crossing number.
- The Harary-Hill Conjecture on the crossing number of the complete graph.
- The rectilinear crossing number of the complete graph.
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.
Papers arising from the workshop:
Note on k-planar crossing numbers