Characterization of Circular-arc Graphs: II. McConnell Flipping

Abstract

McConnell [FOCS 2001] presented a flipping transformation from circular-arc graphs to interval graphs with certain patterns of representations. Beyond its algorithmic implications, this transformation is instrumental in identifying all minimal graphs that are not circular-arc graphs. We conduct a structural study of this transformation, and for $C_4$-free graphs, we achieve a complete characterization of these patterns. This characterization allows us, among other things, to identify all minimal chordal graphs that are not circular-arc graphs in a companion paper.