graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a ''k''-outerplanar graph is a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

that has a planar embedding in which the vertices belong to at most

k

concentric layers. The outerplanarity index of a planar graph is the minimum value of

k

for which it is

k

-outerplanar.

Definition

outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...

(or 1-outerplanar graph) has all of its vertices on the unbounded (outside) face of the graph. 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. And so on. More formally, a graph is

k

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

k

faces and

k

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.

Properties and applications

The

k

-outerplanar graphs have

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

at most

3k-1

. However, some bounded-treewidth planar graphs such as the nested triangles graph may be

k

-outerplanar only for very large

k

, linear in the number of vertices. Baker's technique covers a planar graph with a constant number of

k

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

GNRS conjecture In theoretical computer science and metric geometry, the GNRS conjecture connects the theory of graph minors, the stretch factor of embeddings, and the approximation ratio of multi-commodity flow problems. It is named after Anupam Gupta, Ilan Newma ...

on metric embedding of minor-closed graph families, the

k

-outerplanar graphs are one of the most general classes of graphs for which the conjecture has been proved. A conjectured converse of

Courcelle's theorem In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bru ...

, 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 In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that ...

, has been proven for the

k

-outerplanar graphs.

Recognition

The smallest value of

k

for which a given graph is

k

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

References

{{reflist Planar graphs