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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/907

Actions (login required)

View Item View Item