On Geometric Representations of Graphs


Sue Whitesides
School of Computer Science
McGill University
Montreal, Canada

Classically, graphs G = (V,E) have been drawn by choosing points in the plane for the vertices and curves (e.g., straight lines or rectilinear curves) connecting these points for the edges. However, graphs can be represented geometrically in a variety of other ways. For example, points representing vertices may be chosen so that the edges in E are represented by proximity relations among the points. As another example, vertices may be represented by sets and edges by visibiltiy relationships between these sets.

This talk considers recent results on the subject of such geometric representations.