 |
Discrete Mathematics & Theoretical Computer Science |
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.2088Cell-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 
1; Rodrigo I. Silveira 3,8,4; Ryuhei Uehara 9; Pavel Valtr 10,11; Birgit Vogtenhuber 1; Emo Welzl 12
- 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 Centro de Investigaçao e Desenvolvimento em Matematica e Aplicaçoes
- 9 Japan Advanced Institute of Science and Technology
- 10 Charles University [Prague]
- 11 Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic] [UK]
- 12 Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]
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: HAL:hal-01188902v1
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 644 times.
This article's PDF has been downloaded 549 times.