Graphes W-exterieurs

Abstract

Soient G un graphe planaire et fl un ensemble de sommets, on dit que G est W—extérieur s'il peut être représenté par un graphe plan ayant tous les sommets de W à la frontière de la face extérieure. On caractérise les graphes W-extérieurs par "sous-graphes exclus".On signale une application de cette notion à l’algorithme de Lempel, Even et Oederbaum,qui sera développée dans un article postérieur.

Let G a planar graph and W a set of vertices; G is W-outerplanar if it can be embedded in the plane so that all vertices in W lie on the face exterior.A characterization of W-outerplanar graphs by "subgraphs excluded" is stated.lt is indicated how the result car be¡applied to the Lempel,Even and Cederbaum planarity algorithm.