## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, February 07, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Viola Mészáros (Univ. of Szeged, Charles Univ. Prague)

## Alternating Paths in Bicolored Point Sets

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.

Information for students and suggested topics for student talks