Augmenting outerplanar graphs

In this paper, we show that for outerplanar graphs G the problem of augmenting G by adding a minimum number of edges such that the augmented graph G' is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space. It is also shown that augmenting a biconnected outerplanar graph to a maximal outerplanar graph while minimizing the maximum degree can be achieved in polynomial time. These augmentation problems arise in the area of drawing outerplanar graphs. (C) 1996 Academic Press, Inc.