ON TRIANGULATING PLANAR GRAPHS UNDER THE 4-CONNECTIVITY CONSTRAINT

Triangulation of planar graphs' under constraints is a fundamental pro blem in the representation of objects. Related keywords are graph augm entation from the field of graph algorithms and mesh generation from t he held of computational geometry. We consider the triangulation probl em for planar graphs under the constraint to satisfy 4-connectivity, A 4-connected planar graph has no separating triangles, i.e., cycles of length 3 which are not a face. We show that triangulating embedded pl anar graphs without introducing new separating triangles can be solved in linear time and space. If the initial graph had no separating tria ngle, the resulting triangulation is 4-connected. if the planar graph is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with at most t wice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar graph can be made 4-conne cted while maintaining planarity. Several related remarks and results are included.