Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 '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
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 '10 at 17:30

1 Answer 1

up vote 1 down vote accepted

As S. Carnahan and Kristal Cantwell mentions it in the comments, this problem is NP-hard. See:

Rubber bands, convex embeddings and graph connectivity by N. Linial, L. Lovász and A. Wigderson

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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