# Planar embeddings of planar graph

Let $G=(V,E)$ be a planar graph, only specified by its set of vertices and edges. Suppose $|V|=n$. According to Fary's theorem, there exists a planar embedding of $G$ with straight line segments. Then this embedding can be represented by a set of points in the plane (each $v\in V$ is represented by a unique point $p_v$ and there is a line segment between $p_u$ and $p_v$ iff $(u,v)\in E$)

Questions :

1. Is it possible to find this set of points in polynomial time (i.e. $n^{O(1)}$) ?
2. What if we force the points to have integer coordinates ?
3. Can we force the maximum (euclidian) distance between any two points to be $n^{O(1)}$ ?

Such statements could be very useful for proving lower bounds for some geometrical problems

• All three of your questions are answered in the page you link. – Peter Taylor Jun 20 '18 at 14:50
• I'm not sure, in this article they never mention the complexity of computing this planar embedding in polynomial time. My questions are not about existence but time complexity – Mathieu Mari Jun 25 '18 at 12:48
• In 'Related Results' they do mention being able to solve in linear time for a particular case. – koverman47 Jul 25 '18 at 15:08