Recognizing circle graphs in polynomial time

Abstract

The main result of this paper is an 0 ([ V ] x [ E ]) time algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. The algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices. Furthermore, as a substep of the algorithm, it is shown how to find in 0 ([ V ] x [ E ]) time a decomposition of a graph into prime graphs, thereby improving on a result of Cunningham.