A Linear Algorithm for Convex Drawing of a Planar Graph
A straight line drawing of a planar graph is called a convex drawing if the boundaries of all faces of that graph are drawn as convex polygon. A graph is planar if it has at least one embedding in the plane such that no two edges intersect at any point except at their common end vertex. Not all planar graphs have convex drawing. In this thesis, we study the characteristics of convex drawing of a planar graph. We develop a method for examining whether a face is drawn as a convex polygon or not. Finally, using that method we develop a linear algorithm for examining whether a planar graph has a convex drawing or not.
