McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

DATE: Wednesday, November 22nd 2004.
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Colouring Visibility Graphs
SPEAKER: David Wood, School of Computer Science, McGill University

Let P be a set of points in the plane. The visibility graph of P has vertex set P, such that two points v and w are adjacent whenever there is no other point in P on the line segment between v and w. The chromatic number of visibility graphs is the focus of this talk. Firstly, we characterise the 2- and 3-chromatic visibility graphs. It is an open problem whether the chromatic number of a visibility graph is bounded by its clique number. Our main result is a super-polynomial lower bound on the chromatic number in terms of the clique number. This is joint work with Jan Kara and Attila Por.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at