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, Limerick, Ireland , 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
ID Code:706

Repository Staff Only: item control page

References

F. Brandenburg, D. Eppstein, M.T. Goodrich, S. Kobourov, G. Liotta, and P. Mutzel.: Selected open problems in graph drawing. G. Liotta, editor, Graph Drawing (Proc. GD 2003), volume 2912 of Lecture Notes Comput. Sci., pages 515-539. Springer-Verlag, 2004.

S. Cabello.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. Proc. 20th European Workshop on Computational Geometry, 2004.

I. Fary.: On straight lines representation of planar graphs. Acta Sci. Math. Szeged, 11:229-233, 1948.

L.A. Freitag and P.E. Plassman.:Local optimization-based untangling algorithms for quadrilateral meshes. Proc. 10th int. Meshing Roundtable, pages 397-406, 2001.

D. Lichtenstein.: Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982.

S. K. Stein.: Convex maps. Proc. Amer. Math. Soc., 2(3):464-466, 1951.

E. Steinitz and H. Rademacher.:Vorlesungen über die Theorie der Polyeder. Julius Springer, Berlin, 1934.

W. T. Tutte.: How to draw a graph. Proceedings London Mathematical Society, 13(52):743-768, 1963.

K. Wagner.: Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26-32, 1936.