ISGCI project home  All classes  Smallgraphs

Graphclass: 2-outerplanar

Definition:
A graph G is k-outerplanar if for k=1, G is  outerplanar  and for k>1, G has a planar embedding such that if all vertices on the exterior face are deleted, the connected components of the remaining graph are all (k-1) outerplanar.

References: [44]
Related classes:  outerplanar 

Inclusions

Minimal superclasses:  bounded treewidth   genus 0   partial bar visibility   partial k-tree, fixed k   planar   weak bar visibility 
Maximal subclasses:  Halin   (T2,cycle)-free   caterpillar   outerplanar 

Problems summary

Recognition:Polynomialdetails
Cliquewidth expression: Unknown to ISGCI details
Cliquewidth:Boundeddetails
Weighted independent set:Lineardetails
Independent set:Lineardetails
Domination:Lineardetails

Algorithms for Recognition

Polynomial

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Bounded from bounded treewidth 
See also : Cliquewidth expression

Algorithms for Weighted independent set

Linear from bounded treewidth 
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

See also : Weighted independent set

Algorithms for Domination

Linear from bounded treewidth 
See also : Cliquewidth expression