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 language | English (US) |
---|---|
Pages (from-to) | 673-695 |
Number of pages | 23 |
Journal | Algorithmica |
Volume | 73 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1 2015 |
Keywords
- Crossing number
- Graph drawing
- K-planar graphs
ASJC Scopus subject areas
- Computer Science(all)
- Computer Science Applications
- Applied Mathematics