Abstract
First, we show that MINMOVED-VERTICES is NP-hard and hard to approximate. Second, we establish a connection to the graph-drawing problem 1BENDPOINTSETEMBED-DABILITY, which yields similar results for that problem.
Third, we give bounds for the behavior of MINMOVED VERTICES on trees and general planar graphs.