An Algorithm for Constructing a Planar Layout of a Graph with a Regular Polygon as Outer Face
William Lawrence Kocay, Christian Pantel · 1995
Read’s algorithm for constructing a planar layout of a graph G produces a straight-line embedding of G, by using a sequence of triangulations. Let F denote any face of G. In this paper, Read’s algorithm is modified. A straight-line embedding is constructed in which F forms the outer face, such that its vertices lie on a convex regular polygon. It is proved that the method always works. Usually F is taken as the face of largest degree. The complexity of the algorithm is linear in the number of vertices of G. 1. Read’s Algorithm