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

  • $\begingroup$ All three of your questions are answered in the page you link. $\endgroup$ – Peter Taylor Jun 20 '18 at 14:50
  • $\begingroup$ 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 $\endgroup$ – Mathieu Mari Jun 25 '18 at 12:48
  • $\begingroup$ In 'Related Results' they do mention being able to solve in linear time for a particular case. $\endgroup$ – koverman47 Jul 25 '18 at 15:08

Quoting directly from the Wikipedia article linked in the question:

De Fraysseix, Pach and Pollack showed how to find in linear time a straight-line drawing in a grid with dimensions linear in the size of the graph

As I commented earlier, this answers all three questions.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.