Circle graphs and monadic second-order logic

This article is part of a project consisting in expressing, whenever possible, graph properties and graph transformations in monadic second-order logic or in its extensions using modulo p cardinality set predicates or auxiliary linear orders. A circle graph is the intersection graph of a set of chords of a circle. Such a set is called a chord diagram. It can also be described by a word with two occurrences of each letter, called a double occurrence word. If a circle graph is prime for the split (or join) decomposition defined by Cunnigham, it has a unique representation by a chord diagram, and this diagram can be defined by monadic second-order formulas with the even cardinality set predicate. By using the (canonical) split decomposition of a circle graph, we define in monadic second-order logic with auxiliary linear orders all its chord diagrams. This construction uses the fact that the canonical split decomposition of a graph can be constructed in monadic second-order logic with help of an arbitrary linear order. We prove that the order of first occurrences of the letters in a double occurrence word w that represents a connected circle graph determines this word in a unique way. The word w can be defined by a monadic second-order formula from the word of first occurrences of letters. We also prove that a set of circle graphs has bounded clique-width if and only if all the associated chord diagrams have bounded tree-width. © 2007 Elsevier B.V. All rights reserved.