Home
General Announcement
Program Principal Lecturer János Pach
Subject Geometric Graph Theory
Lectures
Other Invited Speakers
Invited Talks
Participants
Local Arrangements
Computing Facilities
Application Forms
Contacts 

May 28  June 1, 2002 Gateway Center
University of North Texas, Denton
Lectures
Professor János Pach has provided the following outline of the lectures.
Geometric Graph Theory
During the past decade Geometric Graph Theory yielded some striking results that have proved to be instrumental for the solution of a variety of problems in combinatorial and computational geometry. These include the kset problem, proximity probl
ems, and bounding the number of incidences between points and lines.
The following lectures are designed to introduce a broad range of fundamental and recent results in Geometric Graph Theory to senior researchers, junior
researchers and graduate students, in combinatorial and computational geometry, graph theory, topology, theoretical computer science and graph drawing.
Lecture 1 : Planar graphs, Straightline (Fáry) embeddings and other representations of planar graphs, Koebe's theorem. Beyond planarity: RobertsonSeymour
theorems, linkless embeddings.
Lecture 2 : Conway's Thrackle Conjecture, Turán's Brick Factory Problem, Tutte's theory of crossing numbers. Applications to the complexity of the union of
geometric objects.
Lecture 3 : Turántype and Ramseytype theorems for geometric graphs. Convex geometric graphs. Perles' theorems. The use of Szemerédi's Regularity Lemma:
many pairwise crossing edges in a complete geometric graph.
Lecture 4 : Four degrees of separation: the role of partial orders. Many pairwise disjoint edges in geometric graphs. Separating convex bodies in the plane and in
space.
Lecture 5 : Unavoidable crossings: the lemma of AjtaiChvátalNewbornSzemerédi and Leighton. Applications: Quasiplanar graphs, upper bounds on the
number of unit distances, number of incidences between curves and points, number of
ksets. Strengthenings: few crossings per edge.
Lecture 6 : Bisection width and crossing number. Applications to quasiplanar graphs, to piecewise linear homeomorphisms in the plane, to polygonal drawings of
planar graphs with fixed vertices, and to disentangling polygons. Algorithms for drawing graphs with small number of crossings.
Lecture 7 : Proving and improving the Ajtai et al.Leighton lemma using the relation between bisection width and crossing number. Other crossing numbers and
how they are related to one another. The string graph problem and its resolution, NPcompleteness issues.
Lecture 8 : Crossing patterns of segments, Ramsey's theorem with forbidden subgraphs, the ErdosHajnal conjecture, the role of perfect graphs.
Lecture 9 : Towards an extremal theory of topological graphs. The HarborthMengersen graphs. Large noncrossing subconfigurations. Are topological graphs
different from geometric graphs?
Lecture 10 : Geometric hypergraphs, the AkiyamaAlon theorem, ksets in higher dimensions. Upper and Lower Bound Theorems for convex polytopes, and
their applications to planar problems, balanced lines.
