ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
Maurizio Patrignani · International Journal of Foundations of Computer Science · 2006
We investigate the computational complexity of the following problem. Given a planar graph in which some vertices have already been placed in the plane, place the remaining vertices to form a planar straight-line drawing of the whole graph. We show that this extensibility problem, proposed in the 2003 "Selected Open Problems in Graph Drawing" [1], is NP-hard.