<p>You can in cubic time figure out which pair of edges to let cross. For this, try all <span class="math-container">$O(n^2)$</span> pairs, augment the graph by replacing the two edges by a degree 4 vertex (representing the crossing), and test for planarity in linear time.</p>
<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.225.2568&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Straight-line Drawings of 1-planar Graphs</a> highlights some subtleties regarding the straightening of crossing edges.</p>

CC BY-SA 4.0
2021-07-29T15:05:40.197Z
2021-07-29T15:05:40.197Z
Tim
<p>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.</p>

<graph-theory><graph-algorithms>
Finding the single-crossing embedding of a single-crossing graph
VRS
# Finding the single-crossing embedding of a single-crossing graph

(Asked by: username_0 on 2021-07-29)

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.

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2021-07-29. Score: 6

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.225.2568&rep=rep1&type=pdf) highlights some subtleties regarding the straightening of crossing edges.


---

