Download PDFOpen PDF in browser

Hamiltonian Meander Paths and Cycles on Bichromatic Point Sets

EasyChair Preprint 3130

4 pagesDate: April 8, 2020

Abstract

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 crosses 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.

Keyphrases: bichromatic point set, meander cycles, meander paths

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:3130,
  author    = {Oswin Aichholzer and Carlos Alegrı́a and Irene Parada and Alexander Pilz and Javier Tejel and Csaba D. Tóth and Jorge Urrutia and Birgit Vogtenhuber},
  title     = {Hamiltonian Meander Paths and Cycles on Bichromatic Point Sets},
  howpublished = {EasyChair Preprint 3130},
  year      = {EasyChair, 2020}}
Download PDFOpen PDF in browser