Our main result is an O(|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. Our 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 our algorithm, we show how to find in O(|V|x|E|) time a decomposition of a graph into prime graphs, thereby improving on a result of Cunningham.