In a emph{fan-planar drawing} of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt, who proved that every $n$-vertex fan-planar drawing has at most $5n-10$ edges, and that this bound is tight for $n geq 20$. We extend their result, both from the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrain
تحميل البحث