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