Show icon Show search tips...
Hide icon Hide search tips...

[Sy-cg-global] DIMACS Workshop on Geometric Graph Theory

Sarah Donnelly sarahd at
Mon Sep 9 14:54:21 EDT 2002

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, pach at 

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.


The following speakers have been confirmed: 

-- Pankaj K. Agarwal (Duke University)
       Title: TBA
-- Jin Akiyama (Tokai University, Tokyo) 
       Title: TBA
-- Helmut Alt (Freie Universitat, Berlin), 
       Title:  The complexity of (un)folding 
-- Boris Aronov (Polytechnic University, Brooklyn) 
       Title: TBA
-- Imre Barany (Renyi Institute and Univ. College London)
       Title: The minimum area convex lattice n-gon 
-- Peter Brass (City College, New York) 
       Title: TBA 
-- Timothy M. Chan (University of Waterloo) 
       Title: TBA
-- Tamal K. Dey (Ohio State University, Columbus)
       Title: Counting triangulations using crossings in 
              geometric graphs  
-- Adrian Dumitrescu (University of Wisconsin, Milwaukee)
       Title: On the Maximum Multiplicity of Some Extreme 
              Geometric Configurations in the Plane  
-- Hubert de Fraysseix (EHESS, Paris)
       Title: Automorphisms and Isometries of Graphs 
-- Zoltan Furedi (Renyi Institute and University of Illinois, Urbana) 
       Title: TBA    
-- Dan Ismailescu (Hofstra University) 
       Title: TBA    
-- Martin Juvan (University of Ljubljana)
       Title: Planar graphs without cycles of specific lengths 
-- Mikio Kano (Ibaraki University, Hitachi), 
       Title: Alternating no-crossing geometric paths that cover 
              red and blue points in the plane  
-- Gyula Karolyi (Eotvos University, Budapest) 
       Title: TBA
-- Alexander Kostochka (University of Illinois, Urbana
       Title: Coloring intersection graphs of geometric figures 
              with no large cliques  
-- Jan Kratochvil (Charles University, Prague) 
       Title: TBA   
-- Yaakov Kupitz (Hebrew University, Jerusalem)
       Title: Extremal problems on the diameter graph of a 
              finite set in $R^d$ 
-- Vadim V. Lozin (RUTCOR, Rutgers University) 
       Title: TBA
-- Hiroshi Maehara (University of the Ryukyus, Okinawa)
       Title: A condition for the union of spherical caps to 
              be connected  
-- Jiri Matousek (Charles University, Prague) 
       Title: TBA
-- Sean McGuinness (Umea Universitet)
       Title: Bounding the chromatic number of intersection graphs  
              of arcwise connected sets in the plane 
-- Bojan Mohar (University of Ljubljana) 
       Title: TBA
-- Janos Pach (Renyi Institute and City College, New York) 
       Title: TBA
--  Micha Perles (Hebrew University, Jerusalem) 
       Title: TBA
-- Rom Pinchasi (MIT, Cambridge) 
       Title: TBA
-- Richard Pollack (Courant Institute, NYU)
       Title: On the Betti numbers of semi-algebraic sets 
-- Rados Radoicic (MIT, Cambridge) 
       Title: TBA
-- Paul Seymour (Princeton University) 
       Title: TBA
-- Farhad Shahrokhi (University of North Texas, Denton) 
       Title: TBA
-- Micha Sharir (Tel Aviv University and Courant Institute)
       Title: New bounds on incidences and related problems 
-- Shakhar Smorodinsky (Tel Aviv University)
       Title: Ramsey type results for pseudo-circles and spheres 
              spanned by a finite set of points 
-- Jozsef Solymosi (University of British Columbia, Vancouver) 
       Title: TBA
-- Joel Spencer (Courant Institute, NYU)
       Title: Crossing numbers for random graphs 
-- Daniel Stefankovic (University of Chicago)
       Title: Deciding string graphs in NP 
-- William Steiger (Rutgers University, New Brunswick) 
       Title: TBA
-- Mario Szegedy (Rutgers University, New Brunswick) 
       Title: TBA
-- Laszlo Szekely (University of South Carolina, Columbia) 
       Title: TBA
-- Endre Szemeredi (Rutgers University, New Brunswick) 
       Title: TBA
-- Gabor Tardos (Renyi Institute, Budapest) 
       Title: TBA
-- Takeshi Tokuyama (Tohoku University, Sendai)
       Title: How to reform a terrain into a pyramid 
-- Geza Toth (Renyi Institute, Budapest) 
       Title: TBA
-- Jorge Urrutia (UNAM, Mexico)
       Title: Paths of trains with two wheeled cars 
-- Pavel Valtr (Charles University, Prague)
       Title: Turan-type Results for Convex Geometric Graphs 


Registration: (Preregistration deadline: September 23, 2002) 

Regular rate (1 day/2 days/3 days/4 days/5 days)
Preregister before deadline $120/$240/$360/$420/$480
After preregistration deadline $140/$280/$420/$490/$560

Academic/nonprofit rate*
Preregister before deadline $60/$120/$180/$210/$240
After preregistration deadline $70/$140/$210/$245/$280

Preregister before deadline $10/day
After preregistration deadline $15/day

DIMACS Postdocs $0

Non-Local Graduate & Undergraduate students
Preregister before deadline $5/day
After preregistration deadline $10/day

Local Graduate & Undergraduate students $0
(Rutgers & Princeton)

DIMACS partner institution employees** $0

DIMACS long-term visitors*** $0

Registration fee to be collected on site, cash, check, VISA/Mastercard

Our funding agencies require that we charge a registration fee during
the course of the workshop. Registration fees include participation in
the workshop, all workshop materials, breakfast, lunch, breaks and any
scheduled social events (if applicable).

* College/University faculty and employees of non-profit organizations
will automatically receive the reduced rate. Other participants may
apply for a reduction of fees. They should email their request for the
reduced fee to the Workshop Coordinator at
workshop at Include your name, the Institution you
work for, your job title and a brief explanation of your
situtation. All requests for reduced rates must be received before the
preregistration deadline. You will promptly be notified as to the
decision about it.

** Fees for employees of DIMACS partner institutions are
waived. DIMACS partner institutions are: Rutgers University, Princeton
University, AT&T Labs - Research, Bell Labs, NEC Research Institute
and Telcordia Technologies. Fees for employees of DIMACS affiliate
members Avaya Labs and Microsoft Research are also waived. Fees are
not waived for IBM Watson Research Center employees (the terms of the
IBM membership are different from the Avaya and Microsoft agreements).
***DIMACS long-term visitors who are in residence at DIMACS for two or
more weeks inclusive of dates of workshop.


Information on participation, registration, accomodations, and travel can be
found at:



More information about the Dimacs-sy-cg-global mailing list