Crossing Numbers and Graphs with Rotation Systems

Graph drawing considers ways to nicely embed graphs on the plane or other surfaces. The first thing that one tries to avoid is having two edges cross. When that is impossible, one tries to minimize the number of crossings in a drawing. Our approach to this problem has been through rotation systems, that is, the clockwise ordering of edges at each vertex.

During this talk, everything will be introduced from scratch; no knowledge of graph theory will be assumed. The talk will include some remarkably easy algorithmic proofs of classic theorems, such as the Hanani-Tutte Theorem:

If a graph can be drawn in the plane such that every two edges cross an even number of times, then it can be redrawn with no crossings at all.

Joint work with Marcus Schaefer and Daniel Stefankovic.