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.
  • $\begingroup$ this channel can be helpful: youtube.com/channel/UCuAzKw_VngkAsQh7ummYq0A $\endgroup$
    – Avi Tal
    Commented Feb 24, 2022 at 11:18
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Feb 24, 2022 at 12:11
  • $\begingroup$ @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? $\endgroup$
    – Avi Tal
    Commented Feb 24, 2022 at 21:55
  • 2
    $\begingroup$ @AviTal Good point, but this should be fixable with a suitable perturbation. $\endgroup$ Commented Feb 25, 2022 at 21:31
  • $\begingroup$ @KlausDraeger my question is whether the perturbation you are talking about can be done in polynomial time? $\endgroup$ Commented Mar 26, 2022 at 6:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.