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