McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

DATE: Wednesday, November 17th 2004.
TIME: 4:30 PM - 5:30 PM
PLACE: McConnel 320
TITLE: Hamiltonian Cycles in Sparse Vertex-Adjacency Duals
SPEAKER: Perouz Taslakian, School of Computer Science, McGill University

A Hamiltonian cycle is a cycle in a graph G which traverses all the vertices of G exactly once. In this paper we show that the dual graph of any triangulation of a simple polygon will always have a Hamiltonian cycle if we allow some triangles sharing a vertex to be connected with an edge. The number of edges added to the dual is linear in the worst case and the resulting graph is called the sparse vertex-adjacency dual. This is joint work with G. Toussaint.

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