School Seminars and Colloquia

Why Study the Crossing Number of a Graph?

Discrete Structures and Algorithms (Seminar)

by David Wood


Institution: The University of Melbourne
Date: Tue 9th June 2009
Time: 2:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

Abstract: The crossing number of a given graph is the minimum number of crossings in a drawing of that graph. This seminar will be a broad introduction to this topic, aimed at an audience with little or no background in graph theory. I will describe the history of the crossing number, applications of the crossing number to other areas of mathematics, such as combinatorial geometry (the Szemeredi- Trotter theorem) and combinatorial number theory (sum-sets and product- sets), as well as applications in computer science (network visualisation). I will conclude the talk by discussing my own research that establishes connections between the crossing number and structural graph theory (graph minors).

For More Information: David Wood email woodd@unimelb.edu.au