Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41

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. W...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Oubiña, Lía, Martínez Favini-Dubost, C.
Formato: Publicacion seriada
Lenguaje:Inglés
Publicado: 1983
Materias:
Matemática
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/167515
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-167515
record_format dspace
spelling I19-R120-10915-1675152024-06-25T20:08:18Z http://sedici.unlp.edu.ar/handle/10915/167515 Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41 Oubiña, Lía Martínez Favini-Dubost, C. 1983 2024-06-25T19:02:45Z en Matemática 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. Material digitalizado en SEDICI gracias a la colaboración de la Biblioteca del Departamento de Matemática de la Facultad de Ciencias Exactas (UNLP). Facultad de Ciencias Exactas Publicacion seriada Publicacion seriada http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Matemática
spellingShingle Matemática
Oubiña, Lía
Martínez Favini-Dubost, C.
Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41
topic_facet Matemática
description 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.
format Publicacion seriada
Publicacion seriada
author Oubiña, Lía
Martínez Favini-Dubost, C.
author_facet Oubiña, Lía
Martínez Favini-Dubost, C.
author_sort Oubiña, Lía
title Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41
title_short Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41
title_full Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41
title_fullStr Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41
title_full_unstemmed Les formules exclues dans l’algorithme de planarite de Lempel, Even et Cederbaum, I : Notas de Matemática, 41
title_sort les formules exclues dans l’algorithme de planarite de lempel, even et cederbaum, i : notas de matemática, 41
publishDate 1983
url http://sedici.unlp.edu.ar/handle/10915/167515
work_keys_str_mv AT oubinalia lesformulesexcluesdanslalgorithmedeplanaritedelempelevenetcederbauminotasdematematica41
AT martinezfavinidubostc lesformulesexcluesdanslalgorithmedeplanaritedelempelevenetcederbauminotasdematematica41
_version_ 1807223516212232192

Ejemplares similares