Hamiltonian Alternating Paths on Bicolored DoubleChainsCibulka, Josef and Kynčl, Jan and Meszaros, Viola and Stolar, Rudolf and Valtr, Pavel (2009) Hamiltonian Alternating Paths on Bicolored DoubleChains. In: Graph Drawing 16th International Symposium, GD 2008, September 21 24, 2008 , pp. 181192(Official URL: http://dx.doi.org/10.1007/9783642002199_18). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642002199_18
AbstractWe ﬁ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 2colored (i.e., the sizes of the two color classes differ by at most one), then there is a polygonal line consisting of straightline segments with endpoints in S , which is Hamiltonian, noncrossing, and alternating (i.e., each point of S is visited exactly once, every two nonconsecutive segments are disjoint, and every segment connects points of different colors). We show that the above property holds for socalled doublechains 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 lineartime algorithm. On the other hand, we show that the above property does not hold for doublechains in which one of the chains contains at most ≈ 1/29 of all the points.
Actions (login required)
