## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, May 23, 2006, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Jakub Cerny (Charles Univ., Prague)

## Geometric and Topological Graphs with No Forbidden Subgraphs

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. A topological graph is defined similarly, but the edges are represented by Jordan curves. Two of these curves share at most one point and no curve passes through a vertex.

One of the main questions is to determine or estimate the maximum number of edges of a geometric or a topological graph on $n$ vertices without containing a forbidden subgraph. There are many results for various classes of forbidden subgraphs. The mostly studied classes are $k$-pairwise disjoint edges and $k$-pairwise crossing edges.

I will talk about results for these two classes, open problems and I will also show the main ideas of the proof that a geometric graph with no tree disjoint edges has at most $2.5n$ edges.

Information for students and suggested topics for student talks