Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**
Turán-Type Problems for Geometric Graphs
**

**
Pavel Valtr, Charles University**

Geometric graphs are graphs drawn in the plane so that vertices are
represented by distinct points in general position and edges
are represented by segments connecting corresponding pairs of points.
We will discuss Turán-type questions for geometric graphs.
E.g., what is the maximum number of edges in
a geometric graph on *n* vertices with no *k* pairwise crossing
(pairwise disjoint, resp.) edges? Recently, Dilworth's
theorem and so-called generalized Davenport-Schinzel sequences
were used to prove new upper bounds on this number.

Back