MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
5

2

Please consider the following problem:

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?

flag
1 
 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 2010 at 0:41
you probably mean "from" MAX CUT ? – Suresh Venkat Nov 14 2010 at 6:52
@Suresh: Yes.$ $ – S. Carnahan♦ Nov 14 2010 at 12:07
3 
 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 2010 at 17:30

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.