×

On some generalizations of outerplanar graphs: Results and open problems. (English) Zbl 0622.05020

Graph-theoretic concepts in computer science, Proc. Int. Workshop, Bernried/FRG 1986, Lect. Notes Comput. Sci. 246, 146-164 (1987).
[For the entire collection see Zbl 0619.00022.]
Outerplanar graphs have been recently generalized in many directions. Almost all generalizations have been introduced to parametrize the family of planar graphs so that in consequence some of the decision problems which are NP-complete for planar graphs and easy (or trivial) for outerplanar graphs can be solved in polynomial time for every fixed value of a parameter. In this paper, we survey some families of graphs which are known as generalizations of outerplanar graphs: tree-structured graphs (e.g., series-parallel, k-terminal and Halin graphs), W- outerplanar and k-outerplanar. We also discuss some problems which are formulated by slightly modified versions of the statements that characterize outerplanar graphs: the largest face problem and the (independent) face covers in plane graphs. Almost every (sub)section of the paper contains an open problem, a good starting point for further research. Our description of results is rather informal, the reader interested in details is referred to the original works.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C75 Structural characterization of families of graphs
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics

Citations:

Zbl 0619.00022