# Drawing graphs on circles

Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices.

Task: place equidistantly the vertices of $G$ on a circle of unit radius and draw the edges of $G$ in such a way that their total length is minimized.

What is the complexity of this problem?

What is the relevant literature?

• I have heard that this problem is NP-hard, because it has a fairly quick reduction to the max-cut problem. Lovasz had some result with a name like "rubber bands and springs", which approximated solutions using a sphere in $n$-dimensional space. – S. Carnahan Nov 14 '10 at 0:41
• you probably mean "from" MAX CUT ? – Suresh Venkat Nov 14 '10 at 6:52
• @Suresh: Yes. – S. Carnahan Nov 14 '10 at 12:07
• Rubber bands, convex embeddings and graph connectivity by N. Linial, L. Lovász and A. Wigderson may be the Lovasz paper mentioned above. – Kristal Cantwell Nov 14 '10 at 17:30