Colloquium Speaker

Speaker: 
Sue Whitesides, McGill University
Topic: 
Graph Embedding: Algorithmic and Geometric Perspectives
Date: Thursday, December 2, 2004
Time: 11:00AM
Place: Gould-Simpson, Room 701
Refreshments will be served in the 7th floor lobby of Gould-Simpson at 10:45 AM

Abstract

Graphs, in the sense of vertices and edges, are ubiquitous mathematical models for systems involving binary relationships. They may also represent systems that have physical reality. To visualize a graph, or to realize it as a circuit of wires or a network of pipes or highways, we must assign its vertices and edges to concrete locations: we must "draw" the graph.

The increasing complexity of our world presents new challenges for graph layout, as this talk will demonstrate. We will review the historical roots of graph layout and embedding problems, move on to computational aspects of these problems and how they may be dealt with, and describe some current challenges along the way.