ISGCI project home  All classes  Smallgraphs

Graphclass: interval filament

Definition:
A graph is an interval filament if it is the intersection graph of curves in the 2-dimensional plane, with bounded minimal and maximal x-coordinate.

References: [1159]
Related classes:  subtree filament 

Inclusions

Minimal superclasses:  subtree filament   subtree overlap 
Maximal subclasses:  (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   circle-polygon   co-comparability   spider graph 

Problems summary

Recognition: Unknown to ISGCI details
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Polynomialdetails
Independent set:Polynomialdetails
Domination:NP-completedetails

Algorithms for Recognition

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]
Unbounded from (2K2,co-(C6),odd anti-cycle)-free 
     From the complement .


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 split  [1176]




Unbounded from co-bipartite 
     See  bipartite  .


Unbounded from chordal  [1174]
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 [1159]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

See also : Weighted independent set

Algorithms for Domination

NP-complete from chordal  [1146]
NP-complete from circle  [1154]
NP-complete from undirected path  [1146]
NP-complete from split  [1144] [1145]
See also : Cliquewidth expression