Circular-arc graph

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a circular-arc graph is the <a href="/facts/Intersection_graph/IehIvyR3">intersection graph</a> of a set of <a href="/facts/Arc_(geometry)/xBQ0pTBW">arcs</a> on the circle. It has one <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> for each arc in the set, and an <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edge</a> between every pair of vertices corresponding to arcs that intersect.
Formally, let

I
          
            1
          
        
        ,
        
          I
          
            2
          
        
        ,
        …
        ,
        
          I
          
            n
          
        
        ⊂
        
          C
          
            1
          
        
      
    
    {\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}

be a set of arcs. Then the corresponding circular-arc graph is G = (V, E) where

V
        =
        {
        
          I
          
            1
          
        
        ,
        
          I
          
            2
          
        
        ,
        …
        ,
        
          I
          
            n
          
        
        }
      
    
    {\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}}

and

{
        
          I
          
            α
          
        
        ,
        
          I
          
            β
          
        
        }
        ∈
        E
        
        ⟺
        
        
          I
          
            α
          
        
        ∩
        
          I
          
            β
          
        
        ≠
        ∅
        .
      
    
    {\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .}

A family of arcs that corresponds to G is called an arc model.

Circular-arc graph open-in-new

Circular-arc graph