On infinite outerplanar graphs. (English) Zbl 0816.05025

Boza, L.; Diánez, A.; Márquez, A.

Math. Bohem. 119, No. 4, 381-384 (1994).

Outplanar graphs are those with a planar embedding where all vertices lie on the boundary of the same face. The well-known necessary and sufficient condition for finite graphs to be outplanar is that they contain no subdivision of \(K_ 4\) or \(K_{2,3}\). This result also holds for infinite graphs. However, the situation is different if the infinite graph is prohibited from having vertices or edges accumulation; such graphs are called \(p\)-outplanar. The two graphs below, \(L_ 4\) and \(L_{2,3}\), are outerplanar, but not \(p\)-outerplanar. \[ \begin{matrix} \vdots\\ \bullet\\ \rlap{\strut\hskip3em \(L_ 4\)\strut}|\\ \bullet\\ |\\ \cdots\text{---}\bullet \text{---}\bullet \text{---}\bullet \text{--- }\bullet \text{---}\bullet \text{---}\bullet \text{---}\bullet \text{--- }\cdots \end{matrix} \]
\[ \begin{matrix} \rlap{\strut\hskip3em \(L_{2,3}\)\strut}\bullet\\ \cdots\text{---}\bullet \text{---}\bullet \text{---}\bullet {\textstyle\diagup\diagdown\atop \textstyle\diagdown\diagup} \bullet\text{---}\bullet \text{---}\bullet \text{---}\cdots\\ \bullet \end{matrix} \] The main result of the paper is that a graph is \(p\)-outerplanar if and only if it has no subdivision of \(K_ 4\), \(K_{2,3}\), \(L_ 4\), or \(L_{2,3}\).

Reviewer: M.Marx (Pensacola)

MSC:

05C10	Planar graphs; geometric and topological aspects of graph theory
05C75	Structural characterization of families of graphs

Keywords:

planar embedding; outplanar graphs