Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 07, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Viola Mészáros (Univ. of Szeged, Charles Univ. Prague)
It is a basic problem in geometric graph theory to decide which graphs can be drawn on a given point set with noncrossing straight-line edges. Eg. it is known that every outerplanar graph of n vertices can be drawn on any set of n points in general position in the plane. If the graph is a rooted tree, even the image of the root can be specified in advance and one can still find a proper embedding. We obtain new questions by considering colored point sets.
Problem (posed by Erdős around 1989): Determine or estimate the largest number l=l(n) such that, for every set of n red and n blue points on a circle, there exists a noncrossing alternating path consisting of l vertices. He showed that l(n)<=3/2*n+2. He conjectured that his configuration had been asymptotically extremal. Later this was disproved by Jan Kyncl, Janos Pach and Geza Toth. They conjecture that |l(n)-4/3*n|=o(n).
I'm going to present some of the previous results and my results related to the topic.
Automatic MiSe System Software Version 1.4803M | admin login