DRAWING PLANE GRAPHS NICELY

This paper presents two efficient algorithms for drawing plane graphs nicely. Both draw all edges of a graph as straight line segments without crossing lines. The first draws a plane graph 'convex' if possible, that is, in a way that every inner face and the complement of the outer face are convex polygons. The second, using the first, produces a pleasing drawing of a given plane graph that satisfies the following property as far as possible: the complements of 3-connected components, together with inner faces and the complement of the outer face, are convex polygons. The running time and storage space of both algorithms are linear in the number of vertices of the graph.