Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I

Abstract

Lempel, Even et Cederbaum have presented an algorithm for testing graph planarity which is based on t-graphs and their formulas. We replace the t-grarhs by graphs called bushes with the following property : they can be embedded in the plane so that all articulation points lie on the exterior face. We define reducible bushes as reducible t-graphs and characterize them by forbidden formulas.

Lempel, Even et Cederbaum ont présenté, comne test de planarité, un algorithme basé sur les t-graphes et leurs formules. On remplace ici les t-graphes par des graphes appelés arbustes qui ont la propriété suivante: ils admettent une representation plane où tons les point d’articulation sont sur la face extérieure. On définit les arbustes réductibles comme les t-graphes réductibles et on les caractérise par des formules exclues.