This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm.

This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm.

De nombreux problèmes appliqués peuvent être modélisés par le problème de la coloration des sommets d'un graphe, qui est NP-complet en général mais polynomial sur la classe des graphes parfaits introduite par Berge. L'algorithme de coloration des graphes parfaits, de Grötschel, Lovasz et Schrijver, n'est pas réellement efficace d'un point de vue pratique et il est toujours intéressant de trouver un algorithme ''purement'' combinatoire permettant de colorier les graphes parfaits en temps polynomial. Dans cette thèse, nous donnons plusieurs algorithmes simples et rapides permettant de colorier des sous-classes de graphes parfaits. Ces algorithmes utilisent en particulier la notion de contraction de paire d'amis, introduite par Fonlupt et Uhry, à propos de laquelle plusieurs conjectures sont encore ouvertes. Nous utilisons aussi des algorithmes de parcours comme LexBFS, de Rose, Tarjan et Lueker, pour prouver des résultats structuraux sur les graphes considérés.