Hamiltonian Alternating Paths on Bicolored Double-Chains

Cibulka, Josef and Kynčl, Jan and Meszaros, Viola and Stolar, Rudolf and Valtr, Pavel (2009) Hamiltonian Alternating Paths on Bicolored Double-Chains. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 181-192 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_18).

Full text not available from this repository.


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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_18
Classifications:Z Theory > Z.250 Geometry
ID Code:907

Repository Staff Only: item control page


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 (2005)

García, A., Noy, M., Tejel, J.: Lower bounds on the number of crossing-free subgraphs of ı KN . 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, Springer, Algorithms Comb. 25, pp. 551–570 (2003)

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

Kyncl, J., Pach, J., Toth, G.: Long alternating paths in bicolored point sets. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 340–348. Springer (2005). Also to appear in a special volume of Discrete Mathematics honouring the 60th birthday of M. Simonovits.