DIMACS Distinguished Lecture Series

Title: Crossroads in Flatland -- Toward a theory of geometric graphs

Speaker: Janos Pach, City College, CUNY and Renyi Institute, Budapest

Date: Wednesday, October 2, 2002

Location: 1st Floor Lecture Hall, CoRE Bldg., Rutgers University, Busch Campus, Piscataway, NJ


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.