ISGCI project home  All classes  Smallgraphs

Graphclass: unit circular arc

Definition:
A unit circular arc graph is a  circular arc  graph that has an intersection model in which every arc has unit length.

Related classes:  chordal cap unit circular arc   circular arc   unit interval 

Inclusions

Minimal superclasses:  circle-polygon   proper circular arc   spider graph 
Maximal subclasses:  (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   (S3,claw,net)-free cap chordal   astral triple-free   chordal cap unit circular arc   claw-free cap interval   indifference   proper interval   unit interval 

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 [1323] [1040] [995] [1324]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from unit interval  [1177]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [O(n^2)] from circle  [1121]
Polynomial from interval filament  [1159]
Polynomial [O(ln)] from circular arc 
     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)] from circular arc  [1105] [1106] [1158]
See also : Weighted independent set

Algorithms for Domination

Linear from circular arc  [1143] [1158]
See also : Cliquewidth expression