MITACS Seminar Series on Mathematics of Computer Algebra and Analysis

How to draw with a small number of crossings.

Bojan Mohar, Simon Fraser University

3:30pm, Wednesday March 4th, 2009, in K9509.

Abstract:

The problem of drawing graphs with the number of crossings
of edges minimized has many applications. In addition to its
mathematical importance, this concept is relevant in the design of
integrated circuits, for the aesthetics of data visualization, and has
recently found beautiful applications in combinatorial geometry and in
number theory. Although the problems about crossing numbers are easily
understood, they lead to challenging and notoriously hard mathematical
problems. The history of crossing number problems along with the main
theoretical milestones will be presented. The talk will conclude with
the presentation of some recent advances in this area. The exposition
will mostly be accessible for general audience with little or no
mathematical background.