DIMACS Workshop on Geometric Graph Theory, New Brunswick (NJ)

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 Erdős, Lovász, 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 Tóth 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 straigh-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 plan to bring together many of the researchers who contributed to the development of this area.

	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 Erdős, Lovász, 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 Tóth 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 straigh-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 plan to bring together many of the researchers who contributed to the development of this area.
For further information please visit the web-sites: http://dimacs.rutgers.edu/Workshops/index-compgeom.html http://dimacs.rutgers.edu/SpecialYears/2002_CompGeom/ or contact János Pach at pach@cims.nyu.edu