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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
If you already know the two edges that cross, you can use standard techniques to draw the augmented (planar) graph with straight-line edges. This gives a drawing of the original graph whose non-crossing edges are straight, but the two crossing edges may bend at their point of intersection. The result is a piecewise straight-line drawing, but it isn't straightforward to obtain a straight-line drawing. The paper Straight-line Drawings of 1-planar Graphs highlights some subtleties regarding the straightening of crossing edges.
