The Crossing Number of Graphs
Host
Department of Applied Mathematics
Speaker
Marcus Schaefer
School of Computing, Depaul University
http://ovid.cs.depaul.edu/
Description
When drawing a graph in the plane, we may have to allow edges to cross each other. The crossing number of a graph is the smallest number of crossings required to draw the graph. The crossing number is a measure of the non-planarity of a graph, and it has become a central tool in graph drawing. In this talk, we will survey some famous results and open problems related to the graph crossing number, including Turan’s Brickyard Problem (which started it all), the Crossing Lemma, Sylvester’s Problem, Conway’s Thrackle Conjecture, and the Hanani-Tutte theorem.
Event Topic
Discrete Applied Math Seminar