Long Alternating Paths in Bicolored Point Sets

Kynčl, Jan and Pach, János and Tóth, Géza (2004) Long Alternating Paths in Bicolored Point Sets. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 340-348(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_34).

Full text not available from this repository.


Given n red and n blue points in convex position in the plane, we show that there exists a noncrossing alternating path of length $n+c\sqrt{n\over \log n}$. We disprove a conjecture of Erdodblacs by constructing an example without any such path of length greater than ${4\over 3}n+c'\sqrt{n}$.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_34
Classifications: A General Literature > A.001 Introductory and Survey
URI: http://gdea.informatik.uni-koeln.de/id/eprint/600

Actions (login required)

View Item View Item