Jerusalem Mathematics Colloquium

â"ñùú ,èáùá â'é ,éùéîç íåé
Thursday, 16th January 2003, 4:00 pm
Mathematics Building, Lecture Hall 2

Janos Pach

Courant Institute (New York University) and Renyi Institute (Hungarian Academy)

"Beyond Planarity"

Abstract: A geometric graph is a graph drawn in the plane so that its vertices are represented by points in general position (i.e., no three are collinear) and its edges by straight-line segments connecting the corresponding points. Topological graphs are defined similarly, except that now each edge can be represented by any simple (non-selfintersecting) Jordan arc passing through no vertices other than its endpoints.

Every topological graph with n vertices and more than 3n-6 edges has a pair of crossing edges. What happens if, instead of a crossing pair of edges, we want to guarantee the existence of some larger configurations involving several crossings? What kind of unavoidable subarrangements must occur in every geometric (or topological) graph G having n vertices and more than Cn edges, for an appropriate large constant C>0?

The prototype of such a result is the following theorem of Agarwal et al. (1997): every topological graph of n vertices, containing no three pairwise crossing edges, has at most O(n) edges. We do not know whether this statement remains true if the forbidden pattern consists of four (rather than three) pairwise crossing edges.

We survey many open problems and results in this field (partly joint with R. Pinchasi, M. Sharir, G. Toth).

Light refreshments will be served in the faculty lounge at 3:30.

List of talks, 2002-03
List of talks, 2001-02
List of talks, 2000-01
List of talks, 1998-99
List of talks, 1997-98