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.