| 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.