On the Number of Edges of Fan-Crossing Free Graphs

Otfried Cheong, Sariel Har-Peled, Heuna Kim, Hyo Sil Kim

Research output: Contribution to journalArticlepeer-review

Abstract

A graph drawn in the plane with n vertices is -fan-crossing free for geqslant if there are no edges,e1,…,ek, such that ldots …,ek have a common endpoint and crosses all We prove a tight bound of on the maximum number of edges of a -fan-crossing free graph, and a tight bound for a straight-edge drawing. For geqslant we prove an upper bound of (k-1)(n-2) edges. We also discuss generalizations to monotone graph properties.

Original languageEnglish (US)
Pages (from-to)673-695
Number of pages23
JournalAlgorithmica
Volume73
Issue number4
DOIs
StatePublished - Dec 1 2015

Keywords

  • Crossing number
  • Graph drawing
  • K-planar graphs

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the Number of Edges of Fan-Crossing Free Graphs'. Together they form a unique fingerprint.

Cite this