Abstract
We find arbitrarily large finite sets S of points in general position in the plane with the following property. If the points of S are equitably 2-colored (i.e., the sizes of the two color classes differ by at most one), then there is a polygonal line consisting of straight-line segments with endpoints in S, which is Hamiltonian, non-crossing, and alternating (i.e., each point of S is visited exactly once, every two non-consecutive segments are disjoint, and every segment connects points of different colors).
We show that the above property holds for so-called double-chains with each of the two chains containing at least one fifth of all the points. Our proof is constructive and can be turned into a linear-time algorithm. On the other hand, we show that the above property does not hold for double-chains in which one of the chains contains at most ≈ 1/29 of all the points.
Work on this paper was supported by the project 1M0545 of the Ministry of Education of the Czech Republic. Work by Viola Mészáros was also partially supported by OTKA grant T049398 and by European project IST-FET AEOLUS.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abellanas, M., García, J., Hernandez, G., Noy, M., Ramos, P.: Bipartite embeddings of trees in the plane. Discrete Appl. Math. 93, 141–148 (1999)
Abellanas, M., García, J., Hurtado, F., Tejel, J.: Caminos alternantes (in Spanish). In: Proc. X Encuentros de Geometría Computacional, Sevilla, pp. 7–12 (2003) (English version available on Ferran Hurtado’s web page)
Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, Heidelberg (2005)
García, A., Noy, M., Tejel, J.: Lower bounds on the number of crossing-free subgraphs of K N . Comput. Geom. 16, 211–221 (2000)
Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane - a survey. In: Aronov, B., et al. (eds.) Discrete and computational geometry, The Goodman-Pollack Festschrift. Algorithms Comb., vol. 25, pp. 551–570. Springer, Heidelberg (2003)
Kaneko, A., Kano, M., Suzuki, K.: Path coverings of two sets of points in the plane. Pach, J. (ed.), Towards a Theory of Geometric Graphs, Contemporary Mathematics 342, 99–111 (2004)
Kynčl, J., Pach, J., Tóth, G.: Long Alternating Paths in Bicolored Point Sets. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 340–348. Springer, Heidelberg (2005); Also to appear in a special volume of Discrete Mathematics honouring the 60th birthday of M. Simonovits
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cibulka, J., Kynčl, J., Mészáros, V., Stolař, R., Valtr, P. (2009). Hamiltonian Alternating Paths on Bicolored Double-Chains. In: Tollis, I.G., Patrignani, M. (eds) Graph Drawing. GD 2008. Lecture Notes in Computer Science, vol 5417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00219-9_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-00219-9_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00218-2
Online ISBN: 978-3-642-00219-9
eBook Packages: Computer ScienceComputer Science (R0)