DIMACS Workshop on Geometric Graph Theory

September 30 - October 4, 2002
DIMACS Center, Rutgers University, Piscataway, New Jersey

Janos Pach, City College and Courant Institute, New York, pach@cims.nyu.edu
Presented under the auspices of the Special Focus on Computational Geometry and Applications.

The rapid development of computational geometry in the past two decades presented a powerful new source of inspiration for combinatorial geometry, the theory of geometric arrangements. Many curious extremal problems in recreational mathematics turned out to be crucially important for the analysis of a wide range of geometric algorithms. Perhaps the best example of this is the so-called k-set problem of Erdos, Lovasz, Simmons, and Straus, which is more than thirty years old. Given n points in general position in the plane, what is the maximum number of k-tuples that can be separated from the remaining n-k points by a straight line? After almost twenty years of stagnation and ten years of slow progress, in the past two years Dey and Toth achieved two breakthroughs by substantially improving the best known upper and lower bounds, respectively.

The k-set problem belongs to a newly emerging discipline, geometric graph theory. A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are straight-line segments. The first result on geometric graphs was proved almost seventy years ago by Hopf and Pannwitz: if a geometric graph has no two disjoint edges, then its number of edges cannot exceed its number of vertices. According to Conway's famous Thrackle Conjecture, the same assertion remains true for graphs drawn by (not necessarily straight) continuous arcs with the property that any two of them have at most one point in common. Many recent results in this area are relevant to proximity questions, bounding the number of incidences between points and curves, designing various graph drawing algorithms, etc.

The aim of this workshop is to explore the consequences of the new results, and to discuss their extensions and some related questions. We will bring together many of the researchers who contributed to the development of this area.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on March 7, 2002.