On the Number of Edges of Fan-Crossing Free Graphs

Otfried Cheong,
Sariel Har-Peled,
Heuna Kim, and
Hyo-Sil Kim.
A graph drawn in the plane with $n$ vertices is
$k$-fan-crossing free for $k \geq 2$ if there are no $k+1$
edges $g,e_1,\dots, e_k$, such that $e_1,e_2,\dots,e_k$ have a
common endpoint and $g$ crosses all~$e_i$. We prove a tight bound
of $4n-8$ on the maximum number of edges of a $2$-fan-crossing
free graph, and a tight $4n-9$ bound for a straight-edge drawing.
For $k \geq 3$, we prove an upper bound of $3(k-1)(n-2)$ edges. We
also discuss generalizations to monotone graph properties.
PDF.
Last modified: Mon Dec 2 13:31:34 CST 2013