# Finding the single-crossing embedding of a single-crossing graph

Is it known how to find a (piecewise) straight-line embedding of a single-crossing graph on the plane with exactly one crossing in polynomial time? We are currently trying to come up with a method for this, but our approach seems to be getting overly complicated and we wonder if a known simple method already exists.

You can in cubic time figure out which pair of edges to let cross. For this, try all $$O(n^2)$$ pairs, augment the graph by replacing the two edges by a degree 4 vertex (representing the crossing), and test for planarity in linear time.