Circle Graphs

Candidate: Buckingham,Mark Alan

Abstract

From a circle with chords we may derive a graph whose nodes correspond to chords and whose edges correspond to intersecting chords. Such a graph is called a circle graph. After numbering the endpoints of the chords such that two endpoints are numbered the same iff the endpoints belong to the same chord, we form a circle graph sequence by reading off these numbers going around the outside of the circle. Circle graph sequences are often used to prove properties of circle graphs. In this dissertation we discuss many mathematical and algorithmic aspects of circle graphs. The number of different circle with chords representations that yield a chordless path is given. The property that a circle with chords is connected (that is, its derived circle graph is connected) and the property that a circle with chords has two separated chords (that is, two chords that cannot both be intersected by a third chord without the third intersecting a fourth chord) are described in terms of circle graph sequences. They are found to be dual to one another. An incomplete forbidden subgraph characterization of circle graphs is also presented. An important result of this dissertation is that the Berge Strong Perfect Graph Conjecture is shown to hold for the class of circle graphs. Many properties of p-critical graphs and partitionable graphs are given, most with simplified proofs. Some new results are presented and a new, very simple proof of the Berge Conjecture for K(,1,3)-free graphs is put forward. Very efficient algorithms for finding maximum (weighted) cliques and maximum (weighted) stable sets of the derived circle graph of a circle graph sequence are given. We find an O(e*log(,2)(omega)) algorithm for the unweighted clique problem, an O((delta)e) algorithm for the weighted clique problem and an O(c) algorithm for the weighted stable set problem; where e is the number of edges in the graph, the maximum clique size, (delta) the maximum degree and c the number of occurrences of an interval being completely contained in another interval in the circle graph sequence. Some open problems for further research are listed.