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, 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. ************************************************************ 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 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** ************************************************************