Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane

• Aichholzer, Oswin

• Cardinal, Jean

• Hackl, Thomas

• Hurtado, Ferran

• Korman, Matias

• Pilz, Alexander

• Silveira, Rodrigo

• Uehara, Ryuhei

• Valtr, Pavl

• 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 atleast n^2/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.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/12843

収録刊行物

• Discrete Mathematics and Theoretical Computer Science

  Discrete Mathematics and Theoretical Computer Science 16 (3), 317-332, 2014

  Discrete Mathematics and Theoretical Computer Science

キーワード

• Discrete geometry
• Line arrangement
• Planar graphs
• Hamiltonicity

詳細情報

• CRID: 1050001337538460928
• NII論文ID: 120005624451
• ISSN: 13658050
• Web Site: http://hdl.handle.net/10119/12843
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN