Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
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
