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 ﬁnd arbitrarily large ﬁnite 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 ﬁfth 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.
Repository Staff Only: item control page