Our promising results of branch and cut algorithms for the maximum planar subgraph problem provide new chances for solving the planar augmentation problem. Here, a minimum number of edges shall be added to a planar graph, so that the resulting graph is bi- or triconnected and still planar. In a first step, we investigate the structure of the polytope defined as the convex hull over all characteristic vectors of planar and biconnected graphs on n nodes. Then, this theoretical knowledge can be put into practice. Various algorithms are known that use the special structure of planar graphs.
Some algorithms can bound the area of the drawing, or the number of bends.
Classical algorithms are the straightline drawing algorithms given by de Fraysseix, Pach, Pollack, and by Kant for triconnected or triangulated graphs.