McGill University - School of Computer Science

Algorithms Seminar 2003

Everybody is welcome!

DATE: Wednesday, November 19th
TIME: 4:45 PM - 5:45 PM
PLACE: McConnell 320
TITLE: Computational Geometry for World Peace: some open problems
SPEAKER: David Bryant, School of Computer Science, McGill University.

A split is a bipartition of a finite set into two non-empty parts. Any collection of splits may be represented using a splits graph: a bipartite, edge coloured graph, partially labelled by X. The colour classes correspond to the splits. Removing the edges associated with a split A|B partitions the graph into two convex connected parts, one containing all the vertices labelled by A, the other containing all the vertices labelled by B. These graphs are drawn with straight edges so that edges of the same colour are parallel with the same length.

Splits graphs provide an elegant visual representation of groupings within a data set. They have been applied to a wide variety of different domains: from plant evolution to African drumming to UN votings patterns (hence the title) to viral and bacterial identification to comparative linguistics to English literature. I'll talk about some of these applications on Wednesday. However my main emphasis will be on the mathematics of splits graphs and the computational problem of constructing and drawing them. This is work in progress... there are many open problems.

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