Oswin Aichholzer ; Jean Cardinal ; Thomas Hackl ; Ferran Hurtado ; Matias Korman et al. - Cell-paths in mono- and bichromatic line arrangements in the plane

dmtcs:2088 - Discrete Mathematics & Theoretical Computer Science, December 18, 2014, Vol. 16 no. 3 - https://doi.org/10.46298/dmtcs.2088
Cell-paths in mono- and bichromatic line arrangements in the plane

Authors: Oswin Aichholzer ; Jean Cardinal ; Thomas Hackl ; Ferran Hurtado ; Matias Korman ; Alexander Pilz ; Rodrigo I. Silveira ; Ryuhei Uehara ; Pavel Valtr ; Birgit Vogtenhuber ; Emo Welzl

We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n2/4. Further, we show that in every arrangement of n red and blue lines — in general position and not all of the same color — there is a simple path through at least n cells where red and blue lines are crossed alternatingly.


Volume: Vol. 16 no. 3
Section: Combinatorics
Published on: December 18, 2014
Submitted on: May 21, 2014
Keywords: Discrete geometry,Line arrangement,Planar graphs,Hamiltonicity,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 254 times.
This article's PDF has been downloaded 298 times.