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

[Sarah Donnelly]

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 at 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.

*********************************************************

PROGRAM:


MONDAY September 30


8:15-9:00    Breakfast and registration

9:00-9:05    Opening remarks
             Fred Roberts, Director of DIMACS

9:05-9:45    Geometric graphs without short
               self-intersecting paths
             Gabor Tardos, Renyi Institute, Budapest

9:45-10:25   Turan-type results for convex geometric graphs
             Pavel Valtr, Charles University, Prague

10:25-10:45  break

10:45-11:15  Non-crossing geometric paths covering red and
               blue points in the plane
             Mikio Kano, Ibaraki University, Hitachi
  
11:15-11:45  Extremal problems on the diameter graph of a
               finite set in R^d
             Yaakov Kupitz, Hebrew University, Jerusalem
  
11:45-12:30  The complexity of (un)folding
             Helmut Alt, Freie Universitat, Berlin

12:30-2:00   lunch

2:00-2:40    NYU Crossing numbers for random graphs
             Joel Spencer, Courant Institute
  
2:40-3:20    Problems and results on pair crossing number
             Jiri Matousek, Charles University, Prague
  
3:20-4:00    Deciding string graphs in NP
             Daniel Stefankovic, University of Chicago

4:00-4:20    break

4:20-4:50    The minimum area convex lattice n-gon
             Imre Barany, Renyi Institute and Univ. College London
  
4:50-5:20    On cycles in arrangements of lines in space
             V. Koltun  

5:20-5:50    Rectilinear crossing number of complete graphs
             Uli Wagner, ETH Zurich


TUESDAY October 1


8:15-9:00:   Breakfast and registration 

9:00-9:40    The genus of graphs on a fixed nonorientable
               surface
             Bojan Mohar, University of Ljubljana

9:40-10:20   The geometry of random objects
             Van Vu Ha, University of California, Davis

10:20-10:40  break
  
10:40-11:10  A condition for the union of spherical caps 
               to be connected
             Hiroshi Maehara, University of the Ryukyus, Okinawa

11:10-11:40  How to reform a terrain into a pyramid
             Takeshi Tokuyama, Tohoku University, Sendai

11:40-12:10  Simultaneous embedding of planar graphs
             Stephen Kobourov, University of Arizona, Tucson
           
12:30-2:00   lunch

2:00-2:40    Almost planar geometric graphs
             Rom Pinchasi, MIT, Cambridge

2:40-3:20    Convex geometric hypergraphs
             Peter Brass, City College, New York

3:20-3:50    Geometric graphs with no self-intersecting
               cycle of length 4
             Rados Radoicic, MIT, Cambridge

3:50-4:10    break
  
4:10-4:50    Minimum weight Euclidean bipartite matching
             Pankaj Agarwal, Duke University
  
4:50-5:30    Geometric graph Ramsey numbers
             Gyula Karolyi, Eotvos University, Budapest


WEDNESDAY, October 2


8:15-9:00    Breakfast and registration 

9:00-9:50    Turan type problems for geometric graphs
             Micha Perles, Hebrew University, Jerusalem

9:50-10:30   Bigraceful labelings of trees
             Robert Jamison, Clemson University

10:30-10:50  break

10:50-11:30  How many drawings are there?
             Geza Toth, Renyi Institute, Budapest

11:30-11:50  Counting triangulations using crossings in
               geometric graphs
             Tamal Dey, Ohio State University, Columbus

11:50-12:10  Planar graphs without cycles of specific lengths
             Martin Juvan, University of Ljubljana

12:10-12:40  Gearing optimization
             Vadim Lozin, RUTCOR, Rutgers University

12:40-2:30   lunch

2:30-3:30    Strong perfect graph theorem
             Paul Seymour, Princeton University

3:30-4:15    An elementary method in combinatorics and number theory
             Endre Szemeredi, Rutgers University

4:15-4:30    break 

4:30-5:30    Crossroads in Flatland - Toward a theory of 
               geometric graph
             Janos Pach, Renyi Institute and City College, New York

6:30         conference dinner


THURSDAY October 3


8:15-9:00    Breakfast and registration 

9:00-9:40    Crossing numbers and biplanar crossing numbers
             Laszlo Szekely, University of South Carolina, Columbia
  
9:40-10:10   A survey of new results and old problems in
               geometric intersection graphs 
             Jan Kratochvil, Charles University, Prague
          
10:10-10:30  break

10:30-11:10  On the Betti numbers of semi-algebraic sets 
             Richard Pollack, Courant Institute, NYU

11:10-11:45  Long x-monotone paths in line arrangements
             William Steiger/Mario Szegedy, Rutgers University
  
11:45-12:20  Automorphisms and isometries of graphs
             Hubert de Fraysseix, EHESS, Paris

12:30-2:00   lunch

2:00-2:40    Coloring intersection graphs of geometric figures
               with no large cliques 
             Alexander Kostochka, University of Illinois, Urbana

2:40-3:15    On pseudo-transitive graphs
             Farhad Shahrokhi, University of North Texas, Denton

3:15-3:35    break

3:35-4:15    Bounding the chromatic number of intersection
               graphs of arcwise connected sets
             Sean McGuinness, Umea Universitet

4:15-4:40    Recognizing visibility graphs of simple polygons
             Subir Kumar Ghosh, Tata Institute of Fundamental Research

4:40-5:20    Visibility graphs
             James Abello, AT&T and DIMACS


FRIDAY October 4


8:15-9:00:   Breakfast and registration 

9:00-9:40    Incidences problems: some history and new 
               developments
             Boris Aronov, Polytechnic University, Brooklyn
  
9:40-10:15   Ramsey type results for pseudo-circles and
               spheres spanned by a finite set of points
             Shakhar Smorodinsky, Tel Aviv University
        
10:15-10:40  break

10:40-11:20  New bounds on incidences and related problems
             Micha Sharir, Tel Aviv University and Courant Institute

11:20-12:00  An algorithmic application of the concave-chain 
               decomposition
             Timothy M. Chan, University of Waterloo

12:00-12:20  On the maximum multiplicity of some extreme
               geometric configurations in the plane
             Adrian Dumitrescu, University of Wisconsin, Milwaukee
        
12:30        lunch 


***************************************************


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

Postdocs
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
accepted.


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 dimacs.rutgers.edu. 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:

http://dimacs.rutgers.edu/Workshops/GeometricGraph/

**PLEASE BE SURE TO PRE-REGISTER EARLY**


************************************************************