<p>Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions?</p>
<ol>
<li>No edge touches vertices other than its end vertices.</li>
<li>At any given point in the plane other than the vertices at most two edges will cross.</li>
<li>Any two edges will cross at most once.</li>
</ol>

CC BY-SA 4.0
2022-02-24T11:18:15.880Z
this channel can be helpful: https://www.youtube.com/channel/UCuAzKw_VngkAsQh7ummYq0A
Avi Tal
CC BY-SA 4.0
2022-02-24T12:11:57.597Z
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.
Klaus Draeger
CC BY-SA 4.0
2022-02-24T21:55:42.257Z
@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?
Avi Tal
CC BY-SA 4.0
2022-02-25T21:31:04.010Z
@AviTal Good point, but this should be fixable with a suitable perturbation.
Klaus Draeger
CC BY-SA 4.0
2022-03-26T06:58:27.447Z
@KlausDraeger my question is whether the perturbation you are talking about can be done in polynomial time?
Kirubakaran V K
CC BY-SA 4.0
2023-06-14T06:41:20.143Z
Yeah, if a graph violates condition 2 alone, that easy is to fix, right?
Cyriac Antony
<graph-theory><graph-algorithms><planar-graphs><polynomial-time>
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?
Kirubakaran V K
# 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?

(Asked by: username_0 on 2022-02-24)

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.

**Tags:** graph-theory, graph-algorithms, planar-graphs, polynomial-time
> **Comments:**
> **username_1**: this channel can be helpful: https://www.youtube.com/channel/UCuAzKw_VngkAsQh7ummYq0A  
> **username_2**: 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.  
> **username_1**: @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?  
> **username_2**: @AviTal Good point, but this should be fixable with a suitable perturbation.  
> **username_0**: @KlausDraeger my question is whether the perturbation you are talking about can be done in polynomial time?  
> **username_3**: Yeah, if a graph violates condition 2 alone, that easy is to fix, right?  

---

## 0 answers

