Exact crossing numbers

April 28 to May 2, 2014

at the

American Institute of Mathematics, San Jose, California

organized by

Jozsef Balogh, Silvia Fernandez, and Gelasio Salazar

Original Announcement

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 in modern terminology asks for the crossing number of the complete bipartite graph. Since the appearence of Turán's question (which remains open to this day), many fundamental crossing number questions have been tackled, both for their theoretical interest and for their applications to 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 Turán's 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 in 1864.

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:

Bishellable drawings of $K_n$

by Bernardo M. Abrego, Oswin Aichholzer, Silvia Fernandez-Merchant, Dan McQuillan, Bojan Mohar, Petra Mutzel, Pedro Ramos, R. Bruce Richter and Birgit Vogtenhuber

Note on k-planar crossing numbers

by J. Pach, L.A. Szekely, Cs.D. Toth and G. Toth, Comput. Geom. 68 (2018), 2–6 MR3715039

Disjoint edges in topological graphs and the tangled-thrackle conjecture

by Andres J. Ruiz-Vargas, Andrew Suk and Csaba D. Toth, Graph drawing (2016) 284-293 MR3333234

Crossing numbers of complete tripartite and balanced complete multipartite graphs

by Ellen Gethner, Leslie Hogben, Bernard Lidický, Florian Pfender, Amanda Ruiz, and Michael Young, J. Graph Theory 84 (2017), no. 4, 552–565 MR3623394