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 mostd+8, wheredis 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.

Authors

• Goos Kant
• Hans L. Bodlaender

Keywords

No keywords are indexed for this paper.