ISGCI project home  All classes  Smallgraphs

Graphclass: circular arc

Definition:
A circular arc is the intersection graph of arcs of a circle.

References: [453] [777] [1037] [1038] [1043]
Related classes:  Helly circular arc   circle   circular arc cap co-bipartite   circular arc cap comparability   concave-round   interval   proper circular arc   unit circular arc 

Inclusions

Minimal superclasses:  2-interval   circle-polygon   spider graph   upper domination perfect 
Maximal subclasses:  (C4,P4,dart)-free   Helly circular arc   circular arc cap comparability   concave-round   superfragile 

Problems summary

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

Algorithms for Recognition

Linear [1219]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth


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]



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 from interval filament  [1159]
Polynomial [O(ln)]
     Where l is the minimum number of arcs passing through a given point on the circle. [995]

Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear [O(n)] [1105] [1106] [1158]
See also : Weighted independent set

Algorithms for Domination

Linear [1143] [1158]
See also : Cliquewidth expression