k-outerplanar graph

In graph theory, a k-outerplanar graph is a planar graph that has a planar embedding in which the vertices belong to at most

The outerplanarity index of a planar graph is the minimum value of

A 2-outerplanar graph is a planar graph with the property that, when the vertices on the unbounded face are removed, the remaining vertices all lie on the newly formed unbounded face.

-outerplanar if it has a planar embedding such that, for every vertex, there is an alternating sequence of at most

vertices of the embedding, starting with the unbounded face and ending with the vertex, in which each consecutive face and vertex are incident to each other.

, linear in the number of vertices.

Baker's technique covers a planar graph with a constant number of

-outerplanar graphs and uses their low treewidth in order to quickly approximate several hard graph optimization problems.

[2] In connection with the GNRS conjecture on metric embedding of minor-closed graph families, the

[3] A conjectured converse of Courcelle's theorem, according to which every graph property recognizable on graphs of bounded treewidth by finite state tree automata is definable in the monadic second-order logic of graphs, has been proven for the

-outerplanar (its outerplanarity index) can be computed in quadratic time.

A 3-outerplanar graph, the graph of a rhombic dodecahedron . There are four vertices on the outside face, eight vertices on the second layer (light yellow), and two vertices on the third layer (darker yellow). Because of the symmetries of the graph, no other embedding has fewer layers.