NP-Hardness Results for Tension-Free Layout

A {\em tension-free layout\/} of a weighted graph $G$ is an embedding of $G$ in the plane such that the Euclidean distance between adjacent nodes is equal to the edge weight. Very few weighted graphs admit such a layout. However, any graph can be made into a tension-free graph by repeated application of an operation called {\em vertex splitting}, or by removing edges. In this paper we show that computing the minimum number of such operations that yield a tension-free graph is NP-hard.

1995