Prof. Emo Welzl and Prof. Bernd Gärtner
|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)
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.
Automatic MiSe System Software Version 1.4803M | admin login