  Circle graphs are the intersection graphs of chords in a circle. This paper
presents the first sub-quadratic recognition algorithm for the class of circle
graphs. Our algorithm is O(n + m) times the inverse Ackermann function,
{\alpha}(n + m), whose value is smaller than 4 for any practical graph. The
algorithm is based on a new incremental Lexicographic Breadth-First Search
characterization of circle graphs, and a new efficient data-structure for
circle graphs, both developed in the paper. The algorithm is an extension of a
Split Decomposition algorithm with the same running time developed by the
authors in a companion paper.
