Geometric Embedding of Path and Cycle Graphs in Pseudo-convex Polygons

Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S . A straight-line point-set embedding is a point-set embedding with no edge bends or curves. The point-set embeddability problem is NP-complete, even when G is 2 -connected and 2 -outerplanar. It has been solved polynomially only for a few classes of planar graphs. Suppose that S is the set of vertices of a simple polygon. A straight-line polygon embedding of a graph is a straight-line point-set embedding of the graph onto the vertices of the polygon with no crossing between edges of graph and the edges of polygon. In this paper, we present O(n) -time algorithms for polygon embedding of path and cycle graphs in simple convex polygon and same time algorithms for polygon embedding of path and cycle graphs in a large type of simple polygons where n is the number of vertices of the polygon.