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

Workshop 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    Crossing numbers for random graphs
             Joel Spencer, Courant Institute, NYU
  
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    Cutting cycles of lines in space
             Vladlen Koltun, UC Berkeley

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    Simple spanning forests in 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    The majority rule and geometry
             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   On conflict free coloring of discs in the plane
             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 

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage