Characterization of Circular-arc Graphs: II McConnell Flipping
<|reference_start|>Characterization of Circular-arc Graphs: II McConnell Flipping: 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.<|reference_end|>
@article{cao2024characterization,
    title={Characterization of Circular-arc Graphs: II. McConnell Flipping},
    author={Yixin Cao and Tomasz Krawczyk},
    journal={arXiv preprint arXiv:2408.10892},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.10892},
    primaryClass={math.CO cs.DS}
}