# 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