### DIMACS Workshop on Geometric Graph Theory

#### September 30 - October 4, 2002

DIMACS Center, Rutgers University, Piscataway, New Jersey

**Organizer:**
**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.