5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – S. Carnahan Nov 14 '10 at 0:41
  • $\begingroup$ you probably mean "from" MAX CUT ? $\endgroup$ – Suresh Venkat Nov 14 '10 at 6:52
  • $\begingroup$ @Suresh: Yes.$ $ $\endgroup$ – S. Carnahan Nov 14 '10 at 12:07
  • 3
    $\begingroup$ Rubber bands, convex embeddings and graph connectivity by N. Linial, L. Lovász and A. Wigderson may be the Lovasz paper mentioned above. $\endgroup$ – Kristal Cantwell Nov 14 '10 at 17:30
0
$\begingroup$

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

$\endgroup$

Your Answer

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