2
$\begingroup$

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.