DIMACS Center, Rutgers University, Piscataway, New Jersey

**Organizer:****Janos Pach**, City College and Courant Institute, New York, pach@cims.nyu.edu

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

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

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

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

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

Contacting the Center

Document last modified on September 19, 2002.