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; Matias Korman 4,5,6; Alexander Pilz ORCID1; Rodrigo I. Silveira ORCID3,7; Ryuhei Uehara ORCID8; Pavel Valtr 9,10; Birgit Vogtenhuber ORCID1; Emo Welzl 11

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]
    Source : OpenAIRE Graph
  • EuroGIGA_Erdös-Szekeres type problems for colored point sets and compatible graphs; Funder: Austrian Science Fund (FWF); Code: I 648
  • Combinatorial problems on geometric graphs; Funder: Austrian Science Fund (FWF); 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

Consultation statistics

This page has been seen 565 times.
This article's PDF has been downloaded 501 times.