Point-set embeddings of plane 3-trees

A straight-line drawing of a plane graph G is a planar drawing of G, where each vertex is drawn as a point and each edge is drawn as a straight line segment. Given a set S of n points in the Euclidean plane, a point-set embedding of a plane graph G with n vertices on S is a straight-line drawing of G, where each vertex of G is mapped to a distinct point of S. The problem of deciding if G admits a point-set embedding on S is NP-complete in general and even when G   is 2-connected and 2-outerplanar. In this paper, we give an O(n2)O(n2) time algorithm to decide whether a plane 3-tree admits a point-set embedding on a given set of points or not, and find an embedding if it exists. We prove an Ω(nlogn) lower bound on the time complexity for finding a point-set embedding of a plane 3-tree. We then consider a variant of the problem, where we are given a plane 3-tree G with n vertices and a set S   of k>nk>n points, and present a dynamic programming algorithm to find a point-set embedding of G on S if it exists. Furthermore, we show that the point-set embeddability problem for planar partial 3-trees is also NP-complete.