# Algorithms for Weakly Triangulated Graphs

### Arvind Raghunathan

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-89-503

April 1989

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-503.pdf

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.

BibTeX citation:

@techreport{Raghunathan:CSD-89-503, Author = {Raghunathan, Arvind}, Title = {Algorithms for Weakly Triangulated Graphs}, Institution = {EECS Department, University of California, Berkeley}, Year = {1989}, Month = {Apr}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5196.html}, Number = {UCB/CSD-89-503}, Abstract = {A graph <i>G</i> = (<i>V</i>,<i>E</i>) is said to be weakly triangulated if neither <i>G</i> nor <i>G^c</i>, the complement of <i>G</i>, 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 <i>O</i> (<i>e</i>^.<i>v^3</i>) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. Performing these algorithms on the complement graph gives <i>O</i> (<i>v^5</i>) algorithms to find a maximum independent set and a minimum clique cover of such a graph. <p>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 <i>O</i> (<i>e</i>^.<i>v^2</i>) algorithms to find a maximum clique and a minimum coloring of a weakly triangulated graph. We thus obtain an <i>O</i> (<i>v^4</i>) algorithm to find a maximum independent set and a minimum clique cover of such a graph. We also provide <i>O</i> (<i>v^5</i>) algorithms for weighted versions of these problems.} }

EndNote citation:

%0 Report %A Raghunathan, Arvind %T Algorithms for Weakly Triangulated Graphs %I EECS Department, University of California, Berkeley %D 1989 %@ UCB/CSD-89-503 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1989/5196.html %F Raghunathan:CSD-89-503