A graph G = (V,E) is said to be weakly triangulated if neither G nor G^c, the complement of G, contain chordless or induced cycles of length greater than four. Ryan Hayward showed that weakly triangulated graphs are perfect. Later, Hayward, Hoang and Maffray obtained O (e^.v^3) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. Performing these algorithms on the complement graph gives O (v^5) algorithms to find a maximum independent set and a minimum clique cover of such a graph.

It was shown in [13-16] that weakly triangulated graphs play a crucial role in polygon decomposition problems. Several polygon decomposition problems can be formulated as the problem of covering a weakly triangulated graph with a minimum number of cliques. Motivated by this, we now improve on the algorithms of Hayward, Hoang and Maffray by providing O (e^.v^2) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. We thus obtain an O (v^4) algorithm to find a maximum independent set and a minimum clique cover of such a graph. We also provide O (v^5) algorithms for weighted versions of these problems.