@techreport{TR-DCC-95-15,
  number = {DCC-95-15},
  author = {de Mendonça Neto, Cândido F. X. and Eades, Peter and Lucchesi, Cláudio L. and Meidanis, João},
  title = {{NP}-Hardness Results for Tension-Free Layout},
  month = {August},
  year = {1995}, 
  institution = {Department of Computer Science, University of Campinas},
  note = {In English, 11 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      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.
  }
}