Graph drawing seeks to create a “good” visual representation of a graph. Even when a graph is planar, classical methods may construct a very unaesthetic planar embedding.

In the past twenty years, there has been a burgeoning of activity in graph drawing. A number of heuristics are now known that often produce good embedding. On the theoretical side, there have been various restrictions placed on drawings to make them “good,” and the creation of fast algorithms to produce drawings with these restrictions. The vitality of this field is attested to by the regularly held graph drawing conference, and by the recent text [1] by some of the authors of this paper.

This paper deals with planar graphs, which can be drawn so that each face in the drawing is a convex polygon. A characterization of such graphs in terms of SPQR trees produces an O(n) algorithm for testing this convex property. The authors then consider the problem of constructing a data structure that allows the insertion of edges and vertices into the graph, while permitting fast answers to such questions as: “Will the altered graph still be convex, planar, or even planar?” Their results are impressive. Determining if the graph remains convex planar is accomplished in O(1) time. Determining if the graph remains planar is accomplished in O(log n) time. Insertion of a vertex takes O(log n) time, and insertion of an edge takes O(log n) amortized time.

Although this paper won’t tell you how to draw a graph, it will give you a set of tools for maintaining a changing graph, and for deciding which kinds of drawings are possible.