Aichholzer, Oswin and Cardinal, Jean and Hackl, Thomas and Hurtado, Ferran and Korman, Matiaset 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 (in progress)
Cell-paths in mono- and bichromatic line arrangements in the plane

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

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.


Source : oai:HAL:hal-01188902v1
Volume: Vol. 16 no. 3 (in progress)
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

Browsing statistics

This page has been seen 31 times.
This article's PDF has been downloaded 22 times.