The paper presents several characterizations of outerp:anar graphs, some of them are counterparts of the well-known characterizations of planar graphs and the other provide very efficient tools for outerplanarity testing, coding (i.e. isomorphism testing), and counting such graphs. Finally, we attempt to generalize these results for k-outerplanar graphs.
MTOdUCtiOll
The main purpose of this paper is to provide some further characterizations of outerplanar graphs.
A graph G = (V, E) consists of a set V of n vertices and a set E of m edges. Only simple graphs, i.e. without loops and multiple edges are considered in this paper.
A simple path p : v + w in G is a sequence of distinct vertices and edges leading from v to w. A closed simple path is a cycle. If all interior vertices of a simple path p are of degree 2 in G then p is a series of edges, and it is a maximal series of edges if each of its ends is of degree not equal to 2 in G.
A planar graph is outerplanar if it can be embedded in the plane so that all its vertices lie on the same face, hereafter we assume this face to be the exterior. Without loss of generality we may consider only biconnected graphs, since a graph G is outerplanar if and only if all its biconnected components are outerplanar.
With every graph G we can associate the cycle space of G consisting of all cycles and unions of edge-disjoint cycles of G. The cycle space is a vector space over the field of integers modulo 2 with addition of elements defined as the ring sum of sets. A cycle basis of G is defined as a basis for the cycle space of G which consists entirely of cycles. There are special cycle bases of a graph which c;l.n be derived from spanning trees of a graph. Let 'I' be a spanning tree of G. Then, the set of cycles obtained by inserting each of the remaining edges of G into T is a fundamental cycle set of G with respect to T.
Consider a biconnected planar graph G. The set of the interior faces of a plane graph G we shall call a planar cycle basis of G. Planar cycle bases of G are well defined, since every face of a planar embedding of a biconnected planar graph is a 47 '33eorem 2. A graph G is outerplanar if and only if it can be embedded in the plane so that for arbitrary four vertices ~1, 1, v2, v3 and v4 in G there exists a face F such that vi ( 1 s i s 4) iie on the face F.