Title: Using eigenvalues to bound the independence number of a graphSpeaker: John Sinkovic Affiliation: University of Waterloo Location: MC 6486
Finding a maximum independent set (or clique) in an arbitrary graph has been shown to be NP-hard. As any independent set gives a lower bound on the independence number, determining an upper bound is usually more useful.
Title: Geometric drawings of graphs (Part I)Speaker: Alan Arroyo Affiliation: University of Waterloo Room: MC 5479
This is the first of two talks about drawings of graphs that arise from geometry.
Part I: Understanding rectilinear drawings.