ISGCI project home  All classes  Smallgraphs

Graphclass: circle

Definition:
A graph is a circle if it is the intersection graph of chords in a circle.

Let the local complement G*v result from G by complementing G[N(v)]. Two graphs are said to be locally equivalent if one results from the other by a series of local complements. Note that this is an equivalence relation. A graph G is a circle iff no graph locally equivalent to G has an induced subgraph isomorphic to W5 ,BW3 or W7 [140] .
References: [991] [137] [138] [139] [140] [412] [807]
Related classes:  Bouchet   circle graph with equator   circle-polygon   circular arc   k-polygon   permutation 

Inclusions

Minimal superclasses:  (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   BW3-free   Bouchet   circle-polygon   spider graph 
Maximal subclasses:  (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   (5,2)-crossing-chordal   (C5,P,P5,S3,co-(P),co-fork,fork,house,net)-free   (Cn+4,P5,bull)-free   Dilworth 2   HHDG-free   P4-extendible cap P4-sparse   P4-reducible   (P5,bull)-free cap interval   (co-(Cn+4),bull,house)-free   biconvex   distance-hereditary   (domino,gem,house)-free cap pseudo-modular   homogeneously representable   k-polygon   outerplanar   proper circular arc   thick tree   threshold signed 

Problems summary

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

Algorithms for Recognition

Polynomial [O(V^2)] [991] [412] [138] [807]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from bipartite permutation  [1182]

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^2)] [1121]
Polynomial from interval filament  [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 [1154]
See also : Cliquewidth expression