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.
Improve this question
$\endgroup$
6
  • $\begingroup$ this channel can be helpful: youtube.com/channel/UCuAzKw_VngkAsQh7ummYq0A $\endgroup$
    – Avi Tal
    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$
    – Klaus Draeger
    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
    Feb 24, 2022 at 21:55
  • 2
    $\begingroup$ @AviTal Good point, but this should be fixable with a suitable perturbation. $\endgroup$
    – Klaus Draeger
    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$
    – Kirubakaran V K
    Mar 26, 2022 at 6:58

0

Reset to default

Your Answer

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