City College, CUNY and Renyi Institute, Budapest
- DIMACS Center - Rutgers University
- CoRE Building Lecture Hall - Busch Campus
- Piscataway, New Jersey
- Wednesday October 2, 2002 at 4:30 PM.
Crossroads in Flatland -- Toward a theory of geometric graphs
In the traditional areas of graph theory (Ramsey theory, extremal graph
theory, random graphs, etc.), graphs are regarded as abstract binary
relations. The relevant methods are often incapable of providing
satisfactory answers to questions arising in geometric applications.
Geometric Graph Theory focuses on combinatorial and geometric properties
of graphs drawn in the plane by straight-line edges (or, more generally,
by edges represented by simple Jordan arcs). It is a fairly new discipline
abounding in open problems, but it has already yielded some striking
results that have proved to be instrumental for the solution of several
important problems in combinatorial and computational geometry. These
include the k-set problem, proximity questions, bounding the number of
incidences between points and lines, designing various efficient graph
drawing algorithms, etc. In this lecture we try to give a taste of some of
the basic questions and results of this emerging theory.
Document last modified on October 2, 2002