[comp.theory] Reference sought for graph embedding problem

snoeyink@NEON.STANFORD.EDU (Jack Snoeyink) (07/11/90)

The following graph problem should be NP-hard; does anyone have a
reference?

Define the length of an embedding of a graph in the plane with
straight-line edges (with or without crossings) to be the sum of the
Euclidean lengths of all edges.

Min Length Constrained Embedding Problem:
    Let G a graph for which a subset V' of the vertices have been
assigned coordinates,  assign coordinates to the rest of the vertices
to minimize the length of the embedding.

I am also interested in the special case that occurs when the points
of V' are in convex position.

(BTW: NP-hardness in not immediately implied by Garey, Graham, and
Johnson's result on the Euclidean minimal Steiner tree problem because
the topology of the tree is specified up to edge contractions.)

Thanks in advance.


    o					  Jack
  _/\_.
(')>-(`)			snoeyink@cs.stanford.edu