This page is a nicer version of this one.
ISGCI project home  All classes  Smallgraphs

Graphclass: 2-interval

Definition:
A graph is a 2-interval iff it has an intersection model whose objects consist of 2 intervals on a real line.

References: [1031] [472] [some other references]
Related classes:  interval 

Inclusions

Minimal superclasses:  3-interval 
Maximal subclasses:  Halin     XC12-free     block (equivalent to (Cn+4,diamond)-free, chordal cap diamond-free, ptolemaic cap weakly geodetic)     caterpillar arboricity <= 2     circular arc     interval (equivalent to AT-free cap chordal, C4-free cap co-comparability, (Cn+4,T2,X31,XF2n+1,XF3n)-free, boxicity 1, chordal cap co-comparability)     line (equivalent to (K5 - e,W5,co-(A),co-(C4 cup 2K1),co-(P2 cup P3),co-(R),claw,co-twin-C5,co-twin-house)-free)     outerplanar     partial grid     planar of degree 3     tree (equivalent to (0,2)-colorable cap chordal, bipartite cap bridged, cycle-free)
Other subclasses:  co-interval cap interval (equivalent to (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free, chordal cap co-chordal cap co-comparability cap comparability, permutation cap split, split cap threshold signed)     circular arc cap co-bipartite (equivalent to co-comparability graphs of posets of interval dimension 2, height 1)     domino (equivalent to (W4,claw,gem)-free, line graphs of multigraphs without triangles)     gridline (equivalent to line graphs of bipartite graphs, (claw,diamond,odd-hole)-free)     unit circular arc

Problems summary

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

Algorithms for Recognition

NP-complete [1079]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from grid  [1177]
Unbounded from Fn grid  [1176]
Unbounded from Hn,q grid  [1176]
Unbounded from (C4,K4,claw,diamond)-free  [1183]
Unbounded from (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-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 unit interval  [1177]
See also : Cliquewidth expression

Algorithms for Weighted independent set

NP-complete from planar of degree 3  [421]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

NP-complete from 2-subdivision cap planar 
      2-subdivision cap planar  are precisely the  2-subdivision  graphs of  planar graphs.
NP-complete from 2-subdivision
      From Poljak's [1111] construction (which is a 2-subdivision). See also [453]
NP-complete from (C4,C5,C6,C7,C8,H,X85,triangle)-free cap K1,4-free 
      Contains the  2-subdivision of graphs of max. degree 3. See also planar of degree 3.
See also : Weighted independent set

Algorithms for Domination

NP-complete from partial grid  [1162] [630]
NP-complete from line  [1129]
NP-complete from planar of degree 3  [420]
See also : Cliquewidth expression