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 planeArticle

Authors: Oswin Aichholzer 1; Jean Cardinal 2; Thomas Hackl 1; Ferran Hurtado 3,4; Matias Korman 5,6,7; Alexander Pilz ORCID1; Rodrigo I. Silveira ORCID3,8,4; Ryuhei Uehara ORCID9; Pavel Valtr 10,11; Birgit Vogtenhuber ORCID1; Emo Welzl 12

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]
Funding:
    Source : OpenAIRE Graph
  • ALGORITHMS FOR MULTIPLE-OBSERVER TERRAIN VISIBILITY; Code: SFRH/BPD/88455/2012
  • Combinatorial problems on geometric graphs; Code: P 23629
  • Strategic Project - UI 4106 - 2014; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: PEst-OE/MAT/UI4106/2014
  • EuroGIGA_Erdös-Szekeres type problems for colored point sets and compatible graphs; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: I 648

Consultation statistics

This page has been seen 630 times.
This article's PDF has been downloaded 540 times.