On Extending a Partial Straight-Line Drawing

Patrignani, Maurizio (2006) On Extending a Partial Straight-Line Drawing. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 380-385(Official URL: http://dx.doi.org/10.1007/11618058_34).

Full text not available from this repository.

Abstract

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", is NP-complete.

Item Type:	Conference Paper
Additional Information:	10.1007/11618058_34
Classifications:	P Styles > P.720 Straight-line G Algorithms and Complexity > G.999 Others
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/706

Actions (login required)

View Item