Trapezoid graph

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, trapezoid graphs are <a href="/facts/Intersection_graph/IehIvyR3">intersection graphs</a> of <a href="/facts/Trapezoid/nCBKsauz">trapezoids</a> between two horizontal lines. They are a class of co-comparability graphs that contain <a href="/facts/Interval_graph/oLwYI3uT">interval graphs</a> and <a href="/facts/Permutation_graph/b3rjc9NI">permutation graphs</a> as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, <a href="/facts/Martin_Charles_Golumbic/jjoIMseL">Golumbic</a>, and <a href="/facts/Ron_Pinter/pvPVUetW">Pinter</a> in 1988. There exists 
  
    
      
        
          O
        
        (
        n
        log
        ⁡
        n
        )
      
    
    {\displaystyle {O}(n\log n)}
  
 algorithms for chromatic number, weighted <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a>, clique cover, and maximum weighted clique.
</p>

Trapezoid graph open-in-new

Trapezoid graph