AUGMENTING OUTERPLANAR GRAPHS

In this paper, we show that for outerplanar graphs G the problem of au gmenting 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 augment ing a biconnected outerplanar graph to a maximal outerplanar graph whi le minimizing the maximum degree can be achieved in polynomial time. T hese augmentation problems arise in the area of drawing outerplanar gr aphs. (C) 1996 Academic Press, Inc.