ISGCI project home  All classes  Smallgraphs

Graphclass: permutation

Definition:
A graph is a permutation graph iff it has an intersection model consisting of straight lines (one per vertex) between two parallels.

References: [874] [363]
Equivalent classes:  (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X36,XF12n+3,XF2n+1,XF3n,XF4n,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X36),co-XF12n+3,co-XF2n+1,co-XF3n,co-XF4n,co-XF52n+3,co-XF62n+2,odd-hole)-free   circle graph with equator   co-comparability cap comparability   co-permutation   comparability graphs of dimension 2 posets   containment graph of intervals 
Complement classes: self-complementary
Related classes:  bipartite permutation   bounded tolerance   circle   circular permutation   permutation cap split   probe permutation 

Inclusions

Minimal superclasses:  AT-free   (BW3,W5,W7,X103,X104,X105,X106,X107,X108,X109,X110,X111,X112,X113,X114,X115,X116,X117,X118,X119,X120,X121,X122,X123,X124,X125,X126,X53,X88,co-(C6),co-(C8),co-(T2),co-(X3))-free   Bouchet   (C6,C8,T2,X3,co-(BW3),co-(W5),co-(W7),co-(X103),co-(X105),co-(X106),co-(X107),co-(X108),co-(X109),co-(X110),co-(X111),co-(X112),co-(X113),co-(X114),co-(X115),co-(X116),co-(X117),co-(X118),co-(X119),co-(X120),co-(X121),co-(X122),co-(X123),co-(X124),co-(X125),co-(X126),co-(X53),co-(X88),co-X104)-free   (C6,co-(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   PI   (S3,S4,net)-free   (S3,net)-free   (S3,net)-free cap sun-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   (XF12n+3,XF52n+3,XF62n+2,co-(Cn+6),co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),co-XF2n+1,co-XF3n,co-XF4n,odd-hole)-free   (XF12n+3,XF52n+3,XF62n+2,co-(T2),co-(X2),co-(X3),co-(X30),co-(X31),co-(X32),co-(X33),co-(X34),co-(X35),co-(X36),anti-hole,co-XF2n+1,co-XF3n,co-XF4n,hole)-free   (anti-hole,hole,sun)-free   (anti-hole,hole)-free   bounded tolerance   circular permutation   co-bounded tolerance   co-comparability   comparability   comparability cap weakly chordal   comparability graphs of dimension 3 posets   containment graph of circles   containment graphs   containment graphs of circular arcs   intersection graphs of parallelograms (squares)   k-polygon   odd-hole-free   probe permutation   sun-free   sun-free cap weakly chordal   weakly chordal 
Maximal subclasses:  (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free   (3K1,co-(T2),co-(X2),co-(X3),anti-hole)-free   (3K2,C4 cup P2,C5,P2 cup P4,P5,S3,X1,X46,X70,co-(3K2),co-(C4 cup P2),co-(P2 cup P4),co-(X1),co-(X46),co-(X70),co-fish,co-rising sun,fish,house,net,rising sun)-free   AT-free cap bipartite   (C5,P,P5,S3,co-(P),co-fork,fork,house,net)-free   (Cn+4,P5,bull)-free   Dilworth 2   P4-extendible cap P4-sparse   P4-reducible   (P5,bull)-free cap interval   (T2,X2,X3,hole,triangle)-free   (co-(Cn+4),bull,house)-free   bipartite permutation   bipartite tolerance   chordal cap co-chordal cap co-comparability cap comparability   co-interval cap interval   homogeneously representable   permutation cap split   split cap threshold signed   threshold signed 

Problems summary

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

Algorithms for Recognition

Linear [774] [990] [806]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]

Unbounded [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

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

Polynomial [O(n^4)] from AT-free  [160]
Polynomial [O(n^2)] from circle  [1121]
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 from comparability  [453]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
See also : Weighted independent set

Algorithms for Domination

Linear [O(V)] [1342] [1147] [1148] [1149] [1165]
Polynomial from k-polygon  [352]
Polynomial from co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
Polynomial [O(n^2 log^5 n)] from co-bounded tolerance  [1172]
     Assuming a square embedding of the graph is given; finding this is an open problem.

Polynomial from trapezoid  [1155]
See also : Cliquewidth expression