TRIANGULATING PLANAR GRAPHS WHILE MINIMIZING THE MAXIMUM DEGREE

In this paper we consider the problem how to augment a planar graph to a triangulated planar graph while minimizing the maximum degree incre ase. We show that the general problem is NP-complete for bi-connected planar graphs, An approximation algorithm is presented to triangulate triconnected planar graphs such that the maximum degree of the triangu lation is at most d + 8, where d is the maximum degree of the input gr aph, Generalizing this result yields a triangulation algorithm for gen eral planar graphs with maximum degree at most an additional constant larger than existing lower bounds. (C) 1997 Academic Press.