Characterization of Circular-arc Graphs: II. McConnell Flipping

2024/08/20 by Yixin Cao, Cao, Yixin, Tomasz Krawczyk +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2408.10892

openalex publication_date 2024/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₄-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.

Related

• Characterization of Circular-arc Graphs: III. Chordal Graphs
• Characterization of Chordal Circular-arc Graphs: I. Split Graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• On circular-arc graphs having a model with no three arcs covering the circle
• Circularly compatible ones, D-circularity, and proper circular-arc\n bigraphs