Hamiltonian meander paths and cycles on bichromatic point sets
Birgit Vogtenhuber
Graz University of Technology
We show that any set of $n$ blue and $n$ red points on a line admits a plane meander path, that is, a crossing-free spanning path that passes across the line on red and blue points in alternation. For meander cycles, we derive tight bounds on the minimum number of necessary crossings which depend on the coloring of the points. Finally, we provide some relations for the number of plane meander paths.