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

arXiv: https://arxiv.org/abs/1708.01457 · HTML: https://mlsanity.com/paper/1708.01457/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2017.

## Built on by (most cited first, 2 of 2)

- [Minimizing Turns in Watchman Robot Navigation: Strategies and Solutions](https://mlsanity.com/paper/2308.10090/) (2023)
- [Securing Pathways with Orthogonal Robots](https://mlsanity.com/paper/2308.10093/) (2023)

## Abstract (arXiv)

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.