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 increase. 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 triangulation is at most+8, whereis the maximum degree of the input graph. Generalizing this result yields a triangulation algorithm for general planar graphs with maximum degree at most an additional constant larger than existing lower bounds.