We say that a graph is $k$-planar if there you can the draw the graph in such a way that you can color the edges in such a way that no edge crosses an edge of the same color. For example a $1$-planar graph is just a planar graph.
My question is, how do you determine if a graph is $k$-planar?
The case for $k=1$ is already known.
This is the thickness of a graph, and determining it is NP-hard.