  For all $k \geq 1$, we show that deciding whether a graph is $k$-planar is
NP-complete, extending the well-known fact that deciding 1-planarity is
NP-complete. Furthermore, we show that the gap version of this decision problem
is NP-complete. In particular, given a graph with local crossing number either
at most $k\ge 1$ or at least $2k$, we show that it is NP-complete to decide
whether the local crossing number is at most $k$ or at least $2k$. This
algorithmic lower bound proves the non-existence of a
$(2-\epsilon)$-approximation algorithm for any fixed $k \ge 1$. In addition, we
analyze the sometimes competing relationship between the local crossing number
(maximum number of crossings per edge) and crossing number (total number of
crossings) of a drawing. We present results regarding the non-existence of
drawings that simultaneously approximately minimize both the local crossing
number and crossing number of a graph.
