Split the vertices into two sides so every edge crosses, by two-coloring with a search, or find the odd cycle that makes it impossible.
This interactive visualization needs JavaScript.