# Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?

Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions?

1. No edge touches vertices other than its end vertices.
2. At any given point in the plane other than the vertices at most two edges will cross.
3. Any two edges will cross at most once.
• this channel can be helpful: youtube.com/channel/UCuAzKw_VngkAsQh7ummYq0A Feb 24, 2022 at 11:18
• Are there any further constraints? Otherwise, distributing the vertices along the unit circle and drawing each edge as a straight line will do the trick. Feb 24, 2022 at 12:11
• @KlausDraeger maybe I am missing something.... But take the K6 complete graph, the trivial distribution along the circle (60 degrees between vertices) will result in 3 edges crossing the same point... Violating condition 2... Right? Feb 24, 2022 at 21:55
• @AviTal Good point, but this should be fixable with a suitable perturbation. Feb 25, 2022 at 21:31
• @KlausDraeger my question is whether the perturbation you are talking about can be done in polynomial time? Mar 26, 2022 at 6:58