Long Alternating Paths in Bicolored Point Sets

Kyncl, 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, New York, NY, USA , pp. 340-348 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_34).

Full text not available from this repository.

Abstract

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
ID Code:600

Repository Staff Only: item control page

References

M. Abellanas, J. Garcia, G. Hernández, M. Noy, and P. Ramos: Bipartite embeddings of trees in the plane, in: Graph Drawing (S. North, ed.), Lecture Notes in Computer Science 1190, Springer-Verlag, Berlin, 1997, 1-10. Also in: Discrete Appl. Math. 93 (1999), 141-148.

M. Abellanas, A. Garcia, F. Hurtado, and J. JTejel: Caminos alternantes in: X Encuentros de Geometría Computacional (in Spanish), Sevilla, 2003, 7-12.

I. Bárány and J. Matousek: Simultaneous partitions of measures by k-fans, Discrete Comput. Geom. 25 (2001), 317-334.

S. Bespamyatnikh, D. Kirkpatrick, and J. Snoeyink: Generalizing ham sandwich cuts to equitable subdivisions, Disrete Comput. Geom. 24 (2000), 605-622.

H. de Fraysseix, J. Pach, and R. Pollack: How to draw a planar graph on a grid, Combinatorica 10 (1990=, 41-51.

M. Chrobak and H. Karloff: A lower bound on the size of universal sets for planar graphs, SIGACUT News 20/4 (1989), 63-86.

P. Gritzmann, B. Mohar, J. Pach, and R. Pollack: Embedding a planar triangulation with vertices at specified points (solution to Problem E3341), Amer. Math. Monthly 98 (1991), 165-166.

Y. Ikeba, M. Perles, A. Tamura, and S. Tokunaga: The rooted tree embedding problem into points on the plane, Discrete Comput. Geom. 11 (1994), 51-63.

A. Kaneko and M. Kano: Discrete geometry on red and blue points in the plane - a survey, in: Discrete and Computational Geometry (B. Aronov et al., eds.), Springer-Verlag, Berlin, 2004, 551-570.

A. Kaneko and M. Kano, and K. Suzuki: Path coverings of two sets of points in the plane, in: Towards a Theory of Geometric Graphs (J. Pach, ed.), Contemporary Mathematics 342 (2004), 99-111.

A. Kaneko, M. Kano, and K. Yoshimoto: Alternating Hamiltonian cycles with minimum number of crossings in the plane, Internat. J. Comput. Geom. Appl. 10 (2000), 73-78.

Gy. Károlyi, J. Pach, G. Tóth, and P. Valtr: Ramsey-type results for geometric graphs II, Discrete Comput. Geom. 20 (1998), 375-388.

C. Merino, G. Salazar, and J. Urrutia: On the length of longest alternating paths for multicolored point sets in convex position, manuscript.

T. Sakai: Balanced convex partitions of measures in R^2, Graphs and Combinatorics 18 (2002), 169-192.

S. Tokunaga: On a straight-line embedding problem of graphs. Discrete Math. 150 (1996), 371-378.