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

    Share

    Consultation statistics

    This page has been seen 384 times.
    This article's PDF has been downloaded 395 times.