Authors: Oswin Aichholzer ¹; Jean Cardinal ²; Thomas Hackl ¹; Ferran Hurtado ^3,4; Matias Korman ^5,6,7,8; Alexander Pilz ¹; Rodrigo I. Silveira ^3,9,4; Ryuhei Uehara ¹⁰; Pavel Valtr ^11,12; Birgit Vogtenhuber ¹; Emo Welzl ¹³

• 1 Graz University of Technology [Graz]
• 2 Université libre de Bruxelles
• 3 Universitat Politècnica de Catalunya [Barcelona]
• 4 Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona] [UPC]
• 5 National Institute of Informatics
• 6 Japan Science and Technology Agency
• 7 IRATO / Kawarabayashi Large Graph Project [Japan]
• 8 IRATO / Kawarabayashi Large Graph Project
• 9 Centro de Investigaçao e Desenvolvimento em Matematica e Aplicaçoes
• 10 Japan Advanced Institute of Science and Technology
• 11 Charles University [Prague]
• 12 Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic] [UK]
• 13 Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]

Combinatorics

[en]
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.