On crossing numbers of complete and complete bipartite graphs
In the area of crossing numbers we ask for minimizing the number of edge
intersections in a drawing of a graph. There is a rich variety of crossing
number problems: Which graphs do we consider, what exactly is a drawing of a
graph and on which surface is it drawn, and how are intersections counted?
In this course we will concentrate on the crossing numbers of complete and
complete bipartite graphs drawn in the plane, including their rich history
around Zarankiewicz's and Hill's conjectures.
For both graph classes, we will have a look at geometric drawings (vertices
are points in the plane and edges of the graph are straight line segments),
and simple drawings (edges are simple Jordan arcs with at most one pairwise
intersection). We will present basic properties as well as recent
developements, all with a strong emphasis on (old and new) open questions.