There are linear time algorithms that take a planar graph and find an embedding where all the edges are straight lines. However, I believe the problem of start

There are linear time algorithms that take a planar graph and find an embedding where all the edges are straight lines. However, I believe the problem of starting with a general graph and finding an embedding with the minimum number of edge crossings is NP-Hard.