Title: Geometric Embedding of Path and Cycle Graphs in Pseudo-convex Polygons,
Abstract: 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.