Home Bookmarks Papers Blog

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