On generalized outerplanarity of line graphs. (English) Zbl 0708.05020

Sedláček, Jiří

Čas. Pěstování Mat. 115, No. 3, 273-277 (1990).

Summary: A generalized outerplanar graph is a planar graph which can be embedded in the plane in such a way that at least one-end-vertex of each edge lies on the boundary of the same face. Let \({\mathcal A}_ 1\) and \({\mathcal A}_ 2\) be the class of all outerplanar graphs and the class of all generalized outerplanar graphs, respectively. Let L(G) stand for the line graph of a graph G. In this note we show that the following three statements on G are equivalent: (1) L(G)\(\in {\mathcal A}_ 2\); (2) G has no subgraph homeomorphic from one of the seven graphs shown in Fig. 2; (3) the following two conditions hold: (i) \(G\in {\mathcal A}_ 1\), (ii) the degree of each vertex is at most four, each vertex c of degree four is a cut- vertex, for every c there are at least two bridges incident with c, and at least one of them is an end-bridge.

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C99	Graph theory

Keywords:

generalized outerplanar graph; line graph