ISGCI project home  All classes  Smallgraphs

Graphclass: trapezoid

Definition:
A graph is a trapezoid graph if it is the intersection graph of trapezoids between two parallel lines.

References: [277] [248]
Equivalent classes:  bounded multitolerance   co-comparability graphs of posets of interval dimension 2 
Complement classes:  co-trapezoid   comparability graphs of posets of interval dimension 2 
Related classes:  PI   PI*   intersection graphs of parallelograms (squares) 

Inclusions

Minimal superclasses:  AT-free   C6-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,X40,X41,XF2n+1,XF3n,XF4n)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   (T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,anti-hole,co-XF12n+3,co-XF52n+3,co-XF62n+2,hole)-free   (anti-hole,hole)-free   circle-polygon   co-comparability   co-comparability cup comparability   co-perfectly orderable   domination   multitolerance   probe co-comparability   spider graph   weakly chordal 
Maximal subclasses:  PI*   alternately orientable cap co-comparability   bounded tolerance   circular arc cap co-bipartite   co-comparability graphs of posets of interval dimension 2, height 1   intersection graphs of parallelograms (squares) 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Polynomialdetails
Independent set:Lineardetails
Domination:Polynomialdetails

Algorithms for Recognition

Polynomial [O(V^2)] [751] [233] [495] [496]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]

Unbounded from co-comparability graphs of posets of interval dimension 2, height 1 
     See  comparability graphs of posets of interval dimension 2, height 1  .

Unbounded from permutation  [1177]

Unbounded from unit interval  [1177]



Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free 
     From the complement .



See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [O(n logn logn)]
     Timebound valid only when given the model [1120] ; otherwise O(n^2).

Polynomial [O(n^4)] from AT-free  [160]
Polynomial from interval filament  [1159]
Polynomial from perfect  [476]
Polynomial [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from co-comparability  [1100]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
See also : Weighted independent set

Algorithms for Domination

Polynomial from co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
Polynomial [1155]
See also : Cliquewidth expression