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...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Publicacion seriada |
| Lenguaje: | Inglés |
| Publicado: |
1983
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/167515 |
| Aporte de: |
| Sumario: | 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. |
|---|