Processing math: 100%
Hamil­ton­ian me­an­der paths and cy­cles on bichro­matic point sets
Bir­git Vogten­hu­ber
Graz Uni­ver­sity of Tech­nol­ogy

We show that any set of n blue and n red points on a line ad­mits a plane me­an­der path, that is, a cross­ing-free span­ning path that passes across the line on red and blue points in al­ter­na­tion. For me­an­der cy­cles, we de­rive tight bounds on the min­i­mum num­ber of nec­es­sary cross­ings which de­pend on the col­or­ing of the points. Fi­nally, we pro­vide some re­la­tions for the num­ber of plane me­an­der paths.