Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, II - Data structures and implementation

Abstract

Esta edición de <i>Notas de Matemática</i> trae dos trabajos complementarios, cuyos resúmenes se ofrecen a continuación:

1) L'algorithme de réductibilité, présenté ici, est basé sur les formules exclues, obtenues dans la première partie de cet article, et détermine si un arbuste est réductible. En complétant cet algorithme on obtient l'algorithme de réduction aui est la boucle principale de l'algorithme de planarité de Lempel, Even et Cederbaum, et l'algorithme de S-réduction qui est une nouvelle version de l'alaorithme de réduction des PQ-arbres de Booth et Lueker.

2) It is presented an analysis of the usual data structures in problems related to the planarity test of graphs together with the implemen— tation of the algebraic algorithm for planarity testing given in the first article of the fascicle. The structures used for the implementation of this algorithm in Fortran of a PDP 11/60 are described. These structures of hierarchic relational type, allow to perform in an efficient way operations over algebraic formulae which are used during the test obtaining a remarkable improvement in the computation's time respect to the original algorithm of Lempel, Even and Cederbaum.