### 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

Abstract:

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.